2013年03月07日

PPSimになぞぷよの解探索機能を載せました

PPSimでなぞぷよが遊べるとともに別解の探索も可能になりました。
まだ4色とおじゃま以外の設置要素に対応していないのと、まれにバグる問題もあるようですが(たとえばこの問題(※ver1.08bでこのバグは解消しました)、よほどの手数の問題で無い限りはかなり快適に別解を洗い出せるのでなぞぷよ作者に役立つツールになっていると思います。
http://muumu.whyi.org/puyolab/ppsim.html

今後、5色と鉄ぷよへの対応を考えています。
posted by むうむ at 21:34 | Comment(0) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする

2013年01月27日

13段目だとツモは16種類

今までぷよぷよのツモは10種類だと思っていて、確率計算でもツモ10種類についてそれぞれ置き方を探索して〜のようなことを以前に書いてしまいましたが、ぷよぷよ通では14段目に軸ぷよを持って来れないので、13段目に子ぷよだけ置く(軸ぷよを14段目で消す)、ということはできないんですね。
すると、13段目に置く場合はハチイチのツモのたとえば赤緑と緑赤を区別しなければならなくなって、4*4=16通りのツモを考えなくてはならない、ということに今更気づいてしまいました。
一瞬、今まで作ってきた確率計算シミュレータの根幹を揺るがす問題だと思ってしまったくらいで(幸い小手先の修正でなんとかなりそうですが)、少々面倒なことになりました。
前回の記事で告知したシミュレータ、サブウィンドウについては今日だいたい実装できたのですが、公開は今回出てきた問題を解決してからになりそうです。

2月2日追記:上記の問題は、13段目に縦置が最善手となる場合のみ、次善手との平均を取ることで解決しました。現在、ひっそりと開発版を(前回の記事のURLにて)公開中です。正式バージョンが間もなくできると思うので、告知はその時に改めてしたいと思います。今はたまたまここ見て興味のある人のみ使って下さい、ということで。

2月4日追記:13段目の問題はまだバグが残っているようです。ネクストに欲しい色が軸ぷよにあるかどうかを見て置き方を変えられることを見逃していたのが1つの原因のようです。13段目の問題に限らず他にもちょこちょこバグが残っているようで、完全に回収するには時間がかかるかもしれません。

2月6日追記:先日のmomoken効果でアクセスが増加しているみたいです。上ではひっそりと書きましたがそのような状況でもないので、上記のバグは残っていますが、現在開発版を公開中ということで、皆さん是非使ってみて下さい。近日中にツイッターでも告知を行う予定です。

2月9日追記:ツイッターでの告知を始めました。https://twitter.com/puyolab
posted by むうむ at 23:39 | 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) | ぷよぷよ | このブログの読者になる | 更新情報をチェックする


×

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