例のオセロにもうちょっとマトモなAIをつけてみた。
ダウンロード
(Cキーで終了、Rキーでリセット)もしかすると実行するのにGLUTをインストールする必要があるかもしれない…
上にある数字はデバッグ用なので無視してください。
(ソース)
Display
Idle
KeyboardMouseC.txt
KeyboardMouseState.txt
main.txt
MainState.txt
PositionMaps.txt
States.txt
Stones.txt
ResionMap.txt
VectorMaps.txt
Texture
EventFlags.txt
General
SetValue
ProgEnd
EventCheck
AIReversi
BoardOperater
終盤に完全読みをさせている。
これは以前別のところで考えた際に出たアイデアだけど
まず相手が最善の手を打つと仮定して自分の石と相手の石の差が最も大きくなる手を探してみる。
まず説明に入る前に
のようなツリーで下の数字の中でもっとも大きな数を選ぶ方法として次のようにできそうだ。
つまり子の頂点の中で最大の値を親の頂点の値とすることで最大値が一番上の頂点に出てくる。
これと同様にすることで自分の石と相手の石の差が最も大きくなる手を探すことが出来そうだ。
終盤は打つ石を頂点として手順のツリーの構造が出来る。
そのツリーを使えば計算することが出来る。
つまりツリーの一番下の頂点において自分の石数 - 相手の石数の値を計算する。
一番下以外の頂点において、自石ならば子の頂点のなかでもっとも数字の大きいものを選び、
敵石なら子の頂点のなかでもっとも数字の小さいものを選ぶというルールで各頂点に数字を持たせていくと、最終的に一番上の頂点現れた数字がお互い最善に行ったときもっとも自分の石数 - 相手の石数が大きくなる場合の値である。
ただこれがもっともよい選択となるかはちょっと違う気がする。
絶対に勝てる手がある場合勝ちを必ず拾うことができるのは確かだけど、相手が最善に行くと負けてしまう場合はこの方法がベストとはいえないように思える。
たとえば、
において丸が勝ち、バツが負けとし赤線が上の方法で得られた手である場合
1番上で右を選ぶより左を選んだほうが勝つ可能性が高そうな気がする。
相手が最善の手を行くとどちらを選んでも負けなんだけど、相手がミスをすれば勝てる場合、
勝てるパターンが多いほうを選んだほうがいいように思える。
もっと極端な例を挙げると
これなんかは右を選んだらその時点で必敗だ。
左はまだ勝つ可能性が残されている。
その辺を考慮してたとえば次のようにも出来る。
上の手順で得られた数字が0以上数（すなわち自石の数が敵石の数以上、ケースAと呼ぶことにする）ならば上の手順どおりに打つ。
負の数（すなわち自石が敵石より少ない、ケースBと呼ぶことにする）の場合は勝てる頂点が多いほうを選ぶ。
ケースBにおいては他にも勝ち確定(引き分けを含む)となる頂点（つまり上の方法で0以上である頂点）で
もっとも上位にあるもの（以下"深さが浅い"と表現する）を考えて
そこから深さを考慮したウエイトをつけた和の数字が大きいものを選ぶというのもある。
深さが浅いほうが読み間違いが多くなると思われるのでウエイトを大きくしてもいいかもしれない。
…と色々書いたけど今回はケースBに関してはそれとは違う形で評価した。
まぁこの手の計算と再帰関数は相性がいいのでやりやすかった。
以前、RPGツクールでオセロを作ったとき、Rubyだと上手くいかなかった再帰関数を使った完全読みも楽に書けた。Rubyでも遅延評価する方法があるのかもしれなけど、如何せん私はRubyに関してはずぶの素人でよく分からない。
あと開放度から得られる数字を最小値と比較してその差が大きいと打ちにくくなるようにしたんだけどその際に打てる場所ごとに最小値を計算してしまって
その最小値が再帰をつかった重い処理なので、結果としてものすごく重たくなってしまった。
そこであらかじめその最小値を計算しておいて
そこから打てるところを1つずつチェックさせるようにしようと考えた。
ところが最小値の計算式を始めにおいても早くなった感じがしない
おそらく遅延評価ということなので y = f x : h = g y のような式は h = g (f x) みたいな形に展開してから計算しているようなので 多分どこに計算式をおこうが関係ないようだ。
そこで正格に評価するにはどうすればいいのか調べてみたら seq という関数を使えばできるそうだ。
http://www.haskell.org/haskellwiki/Seq
それで
($!) :: (a -> b) -> a -> b
f $! x = x `seq` f x
を使って実際に実行してみると目に見えて早くなった。
PR
