Let's write β

プログラミング中にできたことか、思ったこととか

三目並べのMinMax AIをLipsで

三目並べのMinMaxAIを書くという課題が出まして、
言語は不問ということだったのでとりあえずLispで書きました。


探索空間のサイズ

三目並べは最初がAIの手番だとすると、最大9! = 362880のパターンが有るのでしょうか?
最初に9マスの内にどこを打つのか?次にプレイヤーが残り8箇所のどこをうつのか...というのをゲームの決着の最後まで読むとそのようになるとおもいます。

このサイズの探索空間ならば全探索していても問題ないので今回はそのようにしています。

アルゴリズム

minmaxの要は各段階のスコアをどのように計算するかです。
まずはじめにトライしたのは単純に、

  • プレイヤーの勝利ならば +10
  • AIの勝利ならば -10
  • それ以外ならば 0

というスコア基準にしました。
このように実装しても正常にプレイすることは出来ました。

ですが、何度かプレイしている内にどうもAIが十分に賢くないように感じました。もう少し早く詰めてこられるはずなのに詰めてこないなというようなことがありました。

そこで気がついたのは、この状態ではすべてのゲーム終了時が均等に扱われているということです。実際にプレイしていて早く詰めてこないということを感じるということは、この「早く」という基準を評価に含めてやればいいはずだと考えました。そこでminmaxに探索の深さを渡してやるようにし、評価時に探索が深くなった時の評価が低くなるようにしました。

  • プレイヤーの勝利ならば: 10 - <探索の深さ>
  • AIの勝利ならば: <探索の深さ> - 10
  • それいがいならば: 0

これがうまく言ったようで、AIはこちらが愚かな手を打つやいなや詰めてくるようになりました。
探索が深くならずに早く決着がつくような手を優先するようになったのです。
とりあえず,これで僕には十分に強くなったように感じたので、ここで実装を終えました。

実行結果

今回のコードではまずCUIに対応しました。
ファイルをインタプリターにロードして

(main)

とmain関数を実行すると

* (main)

+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
Moves:[0,1,2,3,4,5,6,7,8]:
0
+-+-+-+
|O| | |
+-+-+-+
| |X| |
+-+-+-+
| | | |
+-+-+-+
Moves:[1,2,3,5,6,7,8]:
1
+-+-+-+
|O|O|X|
+-+-+-+
| |X| |
+-+-+-+
| | | |
+-+-+-+
Moves:[3,5,6,7,8]:
6
+-+-+-+
|O|O|X|
+-+-+-+
|X|X| |
+-+-+-+
|O| | |
+-+-+-+
Moves:[5,7,8]:
5
+-+-+-+
|O|O|X|
+-+-+-+
|X|X|O|
+-+-+-+
|O|X| |
+-+-+-+
Moves:[8]:
8
+-+-+-+
|O|O|X|
+-+-+-+
|X|X|O|
+-+-+-+
|O|X|O|
+-+-+-+
Draw..
* NIL

というふうにボードが表示されて、可能な手のリストが表示されるので、入力すると、
ゲームが進行するというふうになっています。