2012年06月27日

p(x4*-b1')の最善手の修正

また誤りがあったので、以前の計算の修正記事を挟みます。
(x4*-b1')では、ネクネクまで見て最も数の多い色を発火色にする手を最善手として計算していました。



しかし、1手目を捨てても最大数(ネクネクまで見て最も数の多いの数)が減ることは無く、むしろ次に出現するネクネク次第では最大数が増える見込みがある場合は、とりあえず1手目を捨てて4手目まで見て発火色を決めるというのが最善手となります。
たとえば、現在手・ネクスト・ネクネクがrb・gg・yyの場合、以前の計算ではbb(yyでも良い)を採用していましたが、実際にはrbは使わず(bはキー色なのでキーとして設置する)、次に出現するネクネクを見てbとyのどちらを発火色にするかを決めるのが最善手です。
rr・gg・yyという場合も、1手目を捨てて損は無いので1手目を捨て、次に出現するネクネクがrr、rb、bbのいずれかだったら、(bはキーに置くとして)gとyのどちらかを選び(どちらでも良い)、それ以外であれば、gとbのどちらか数の多い方(同数であればどちらでも良い)を選びます。
bb・rr・ggの場合は、1手目はbをキーとして置き、次に出現するネクネクがyyだったら2手目も捨ててgとyの2択、それ以外は2手目は捨てずにrとgの2択です。
このように、最大数が増える見込みがある(今までに捨てていない色でなおかつ最大数である2色以上を選択できる)場合はツモを捨ててネクネクを見て判断するのが最善手となります。

さすがにこのような場合分けは面倒だったので、コンピュータに最善手を探索させて計算しました。

左が以前(1手目〜3手目のみで発火色を決める場合)の値、右が修正後(常にネクネクまで見て発火色を決める場合)の値です。
p(x4*-b1':2) = 100.00%, 100.00%
p(x4*-b1':3) = 93.97%, 93.97%
p(x4*-b1':4) = 75.24%, 75.05%
p(x4*-b1':5) = 54.26%, 52.59%
p(x4*-b1':6) = 36.70%, 34.29%
p(x4*-b1':7) = 23.97%, 21.57%

6手、7手の場合は2.4%と(発火できない確率が)結構下がりました。
posted by むうむ at 01:01 | Comment(0) | ぷよぷよ-確率 | このブログの読者になる | 更新情報をチェックする

2012年06月18日

式の一般化と、前回記事の誤りの発見

前回記事の計算で誤りが2箇所ありました。
不注意による場合分けのミスです。


p(a2*+b2:n≧3) = q(^a^b)*p(a2*+b2:n-1) + q(bb)*p(a2*:n-1) + q(^ab1)*p(a2*+b1:n-1) + q(a1^b)*p(a1*+b2:n-1) + q(ab)*p(a2*+b2:ab:n)


p(a2*+b2:n≧3) = q(^a^b)*p(a2*+b2:n-1) + q(bb)*p(a2*:n-1) + q(^ab1)*p(a2*+b1:n-1) + q(a^b)*p(a1*+b2:n-1) + q(ab)*p(a2*+b2:ab:n)

最後から2番目の項のq(a1^b)が誤りで、正しくはq(a^b)です。(aaの場合を抜かしていました。)

もう一つは、

p(a2*+b2:ab-^a^b:n≧3) = q(a^b)*p(a1*+b1:n-3) + (q(ab) + q(^ab1)*p(a2:n-3) + q(^a^b)*p(a2*+b1:n-3) + q(bb)*a1(n-3);
# (ab|^a^b|ab)のとき、p(a2*:n) < p(a1*+b1:n) なので、(a2*)にするのが最善手
# (ab|^a^b|^a^b)のとき、p(a2*+b1:n) < p(a1*+b2:n) なので、(a2*+b1)にするのが最善手


p(a2*+b2:ab-^a^b:n≧3) = q(a^b)*p(a1*+b1:n-3) + q(ab)*p(a2*+b1:ab:n-2) + q(^ab1)*p(a2:n-3) + q(^a^b)*p(a2*+b1:n-3) + q(bb)*a1(n-3);
# (ab|^a^b|ab)のとき、p(a2*+b1:ab:n) < p(a1*+b2:ab:n) なので、(a2*+b1:ab)にするのが最善手
# (ab|^a^b|^a^b)のとき、p(a2*+b1:n) < p(a1*+b2:n) なので、(a2*+b1)にするのが最善手

修正したのは2番目の項です。(ab|^a^b|ab)のときは、ネクネクのabを置いてしまうのではなく、現在手のabを置き、^a^bを捨て、abが現在手になったところでネクネクまで見て判断するのが最善手です。

値については数%のずれだったので大きな変化はありません。
2手:98.0%
3手:88.6%
4手:73.6%
5手:57.4%
6手:42.6%
7手:30.4%

これらの誤りは、よりコンピュータに計算を任せる実装をしていく中でで見つかりました。
具体的には、再帰と最善手探索を使っています。
確率計算第1弾では書き下せる式は全部書き下すという方針でやっていましたが、これだと人間が理解しやすい代わりに求めるべき確率の種類が増えると手間がどんどん増えてしまいます。
そこで、再帰を使うとp(as*:n)(sは1, 2, 3, …)やp(as*-bt:n)(s,tは1, 2, 3, …)が以下のように簡単に求まります。(いい加減な書式なので、雰囲気だけ読み取ってくれればOKです。)

p(as*:n) =
if(s<=0) 0.0
if(n<=0) 1.0
else q(^a)*p(as*:n-1) + q(a1)*p(a(s-1)*:n-1) + q(aa)*p(a(s-2)*:n-1)

p(as*-bt:n) =
if(s<=0 && t<=0) 0.0
if(n<=0) 1.0
(s<=0 && t>=1のときはs = 1として)
else q(^a^b)*(as*-bt:n-1) + q(^ab1)*(as*-b(t-1):n-1) + q(bb)*(as*-b(t-2):n-1) + q(ab)*(a(s-1)*-b(t-1):n-1) + q(a1^b)*(a(s-1)*-bt:n-1) + q(aa)*(a(s-2)*-bt:n-1)

これだけで、p(a1*:n)、p(a2*:n)、p(a3*:n)、p(a1*-b1:n)、p(a1*-b2:n)、p(a2*-b1:n)、p(a2*-b2:n)、p(a2*-b3:n)、……などを同じ関数で求められます。
また、第1弾では無視していましたが、左下の図はp(a4*:n)の状況といえるので、p(a5*:n)や、p(a4*-b2:n)(右下図を載せていましたが、やっぱり違いました。この場合はp(b2-a2*-b2:n)と表記するべきですね。)などの確率も意味のある値になりそうです。


p(as*+bt:n)(p(a2*+b2:n)など)のように、ネクネクまで見て判断する必要のある確率は、前回の記事では人間の頭で最善手を考えて計算しましたが、以下のようにコンピュータの最善手探索に任せてしまうと機械的に計算できます。(その代わり、コードに手を入れて処理を見ないと人間側で最善手を把握できません。)
わかりやすく書き直すのが面倒なのでそのままコードの一部を載せます。
現在手がABであるときです。

p += tsumo_nxnx[i].get_q()*min(apb(n-1, s, t-1, tsumo_nx, tsumo_nxnx[i]), apb(n-1, s-1, t, tsumo_nx, tsumo_nxnx[i]));

min()という関数で最も発火しやすいツモの置き方(相手側の最善手)をコンピュータに選ばせています。min()の中は再帰関数が入っていて、ネクネクまで見た上で現在手を1手置いたときの確率をその現在手の置き方分だけ(上の計算式では、ABハチイチをaに使う場合とbに使う場合の2通り)計算させています。
その中から最善手をコンピュータに選ばせているわけですね。

最善手探索はパターンが増えると計算時間がどんどん増えていくので、できる限り人間側でのパターン化が必要です。
おじゃまの2段掘りの最善手なんかもコンピュータに丸投げしてブラックボックスにはせず、できるだけ最善手の方針を人間側が把握できるようにしたいと思っています。

なお、次の記事ではネクストまで見た場合の確率について書く予定です。
今までは相手がネクネクまで見た上で最善手を判断するとして計算してきましたが、相手がネクストまでしか見ずに判断した場合にどれほど確率に差が出るのか、という話です。
posted by むうむ at 23:11 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする

2012年06月12日

第1弾で計算できていなかった確率を計算

今回、確率計算第1弾でアップしたページで計算できていなかった部分の計算を行い、表を全部埋めて下記ページを更新しました。
http://space.geocities.jp/puyopuyo_muumu/sa_probabilities.html

相手がネクネクまで見て最善手を決定する形については計算できていませんでしたが、第2弾でネクネクまで見て判断する場合の計算をしてましたので、同じやり方で出来ます。
それから、期待値を計算した際に気づいたのですが、p(a1*-b1:n)の計算を行うコードに誤りがあったので修正しました。(式にある係数をコード化する際に一部写し忘れていました。)

例として、p(a2*+b2)の計算を示します。(第1弾の中では一番面倒でした。)



nが2以下の場合は以下のとおり。
p(a2*+b2:n≦1) = 1
p(a2*+b2:2) = 1-q(bb)*q(aa) = 1-1/256

nが3以上のとき、

p(a2*+b2:n≧3) = q(^a^b)*p(a2*+b2:n-1) + q(bb)*p(a2*:n-1) + q(^ab1)*p(a2*+b1:n-1) + q(a1^b)*p(a1*+b2:n-1) + q(ab)*p(a2*+b2:ab:n)

となります。
abハチイチが来た場合はネクストを見て判断する必要があるので、現在手がabハチイチであるときに発火されない確率p(a2*+b2:ab:n)とし、以下でこれを計算します。

p(a2*+b2:ab:n≦2) = 1
p(a2*+b2:ab:n≧3) = q(bb)*p(a1*:n-2) + q(a^b)*p(a1*+b1:n-2) + q(ab)*p(a2*+b2:ab-ab:n) + q(^ab1)*p(a2*+b2:ab-^ab1:n) + q(^a^b)*p(a2*+b2:ab-^a^b:n)

ネクストがabハチイチ、a0個b1個、aもbも0個のときはそれぞれネクネクまで見て判断する必要があるので、
それぞれp(a2*+b2:ab-ab:n)、p(a2*+b2:ab-^ab1:n)、p(a2*+b2:ab-^a^b:n)として計算します。

p(a2*+b2:ab-ab:n≦2) = 1
p(a2*+b2:ab-ab:n≧3) = q(aa)*0 + q(b)*p(a1*:n-3) + q(a1^b)*p(a1*:n-3) + q(^a^b)*p(a2*+b1:ab-^a^b:n-1)
# (ab|ab|^a^b)のとき、p(a2*+b1:n) < p(a1*+b2:n) なので、(a2*+b1)にするのが最善手

p(a2*+b2:ab-^ab1:n≦2) = 1
p(a2*+b2:ab-^ab1:n≧3) = q(aa)*0 + (q(b) + q(a1^b))*p(a1:n-3) + q(^a^b)*p(a2:n-3)
# (ab|^ab1|^a^b)のとき、p(a2*:n) < p(a1*+b1:n) なので、(a2*)にするのが最善手

p(a2*+b2:ab-^a^b:n≦2) = 1
p(a2*+b2:ab-^a^b:n≧3) = q(a^b)*p(a1*+b1:n-3) + (q(ab) + q(^ab1)*p(a2:n-3) + q(^a^b)*p(a2*+b1:n-3) + q(bb)*a1(n-3);
# (ab|^a^b|ab)のとき、p(a2*:n) < p(a1*+b1:n) なので、(a2*)にするのが最善手
# (ab|^a^b|^a^b)のとき、p(a2*+b1:n) < p(a1*+b2:n) なので、(a2*+b1)にするのが最善手

(p(a2*:n) < p(a1*+b1:n)やp(a2*+b1:n) < p(a1*+b2:n)は厳密に示されているわけではありませんが、n=1〜7の範囲で全て成立しているのでOKということにしました。)

以上、なかなか面倒でしたがやり方は決まっているので機械的にできました。
このように、ネクネクまで見た後は(相手とのツモ差によるツモ予見を使用しない限りは)現在手を置かなくてはならないので、ネクネクまでのパターンで全ての場合を尽くせます。
posted by むうむ at 01:01 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。