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) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。


×

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