この記事は、Kawaz Advent Calendar 2015の12月15日ぶんの記事です。札幌ゲーム制作者コミュニティKawazのサイト内に書いた記事 http://www.kawaz.org/blogs/h_hiro_/2015/12/17/800/ と同一のものです。
はじめに
今年10月より、Sapporo.cppの企画として「オセロAIの作成に取り組む」ということを行っています。ということで私が作ったものを紹介します。
なお、開発の際の話などは、C++ Advent Calendar 2015の12月16日ぶん（12月19日公開）「C++でコードレビューを受けて気づいたこととか」に書いています。
なおこのオセロAI企画は、Sapporo.cppのオンラインもくもく会（おおむね毎週1回実施。上記リンク先を参照）にて継続実施しています。オンラインで参加できますので、もし興味を持った方がいらっしゃったらご参加ください。
コードは https://github.com/sapporocpp/othello-shell/tree/hhiro-AdC2015 にあります。
おことわり
既存のオセロAIの戦術を勉強したわけではありません。あしからず。
基本方針
- まずは「打つ手を選ぶ条件を手で次々記述していく」ことを実装する。
- 次いで、「コンピュータに自動探索させる」ことを実装する。
方針1：打つ手を選ぶ条件を手で次々記述していく
- 最初は、盤面全体を順に見ていって、置く場所は「ルール上置いてよい場所で最初に見つかったもの」を選ぶという処理を実装（M1）。
- 次に、プログラムが簡単に書けそうな「石を打ったあと、自分の石がなるべく多くなるようにする」ものを実装（M2）。
- 続いて、自分が小さいころに教えてもらった「角に置けるなら優先的に置く」「角の隣には極力置かない」をM2に加えたものを実装（M3）。
- M3をもう少し発展させ、自分がオセロでどうやって手を選んでいるかを踏まえ、以下の判断を行うものを実装（M4）。
- 角のマスは「優先度：最高」。
- 辺上のマスは、それをもう相手に取られないことが確定するならば（注）「優先度：高」（角よりは優先しない）。
- 角のマスの隣に置くのは「優先度：低」。ただし、対応する角のマスが自分の石であれば「優先度：普通」
- それ以外は「優先度：普通」。
- 以上の評価基準により、優先度が並ぶ置き場所が複数あるならば、その石を置いた結果、自分の石で「角のマスにある石」「辺上のマスにある石」「周囲八方に他の石がある石」の数の合計が多くなるものを選ぶ（相手に取り返されにくい、という基準）。
（注）
ここでは、判定が容易な「辺上から自分の石を辿ることで、角にある自分の石に到達できる」ものに限って、「もう相手に取られないことが確定する」と扱う。例えばこの局面で、黒がAやCに石を置いた場合、左上の自分の黒石まで黒石が繋がった状態になり、AやCはもう相手に取られることはない。しかしBやDではそうとは限らない。
これらを対局させた結果はこちら。各組み合わせについて先手・後手をそれぞれ持たせて対局させている。同じAI同士の対戦結果も掲載している。
| 先手＼後手 | M1 | M2 | M3 | M4 |
|---|---|---|---|---|
| M1 | 19＼45 | 23＼41 | 7＼57 | 21＼43 |
| M2 | 30＼34 | 19＼45 | 22＼42 | 3＼60 |
| M3 | 29＼0 | 43＼21 | 20＼44 | 18＼46 |
| M4 | 49＼15 | 50＼0 | 39＼25 | 26＼38 |
- M1: 1勝5敗（自身との対局除く。以下同様）
- M2: 1勝5敗
- M3: 4勝2敗
- M4: 6勝0敗
私自身が打つつもりで組んだM4が最高の成績であった。とはいえ、対局結果を見ていると疑問な手もあった。例として、これはM4同士を対戦させたものなのだが、下の図で白がAに石を置いていた。これは直後にBが石を置くとすべて取り返されてしまうので、必ずではないとはいえ無駄な手のことが多い。今後（打つ手を選ぶ条件を手で次々記述していくという条件のもとでは）こういった状況を試しながら見つけていくことになるだろう。
方針2：コンピュータに先読みさせる
ここで「コンピュータに先読みさせる」とは、相手の手の先読みを行うことで、最善の結果が出そうな自分の手を見つける、ということである。いわゆるゲーム木の探索である。
今回用いているのは、一番シンプルなミニマックス法というもので、自分の手と相手の手をシミュレーションする際に、自分の手はなるべく自分にとって評価値が高くなるものを、相手の手は自分にとってなるべく評価値が低くなるものを選ぶことを所定の手数（あるいは別の打ち切り条件）まで続ける。この処理は再帰を用いるとかなりシンプルにかける（ソースコード AI_M*_D*.hpp 中のtry_placeメソッド）。
なおミニマックス法を用いるには、評価値を用意しておく必要がある。これらは上記のM2～M4に合わせ、以下のように定める。
- M2：盤面上の石の個数の両プレイヤー間の差（自分－相手）を評価値とする。
- M3：角に石を置いた回数の両プレイヤー間の差（自分－相手）を評価値とする。それが一緒であれば、角の隣に石を置いた回数の両プレイヤー間の差（相手－自分）を評価値とする。それも一緒なら評価値は同じとする。
- M4：「優先度最高」「優先度高」「優先度低」「優先度普通」の順で【自分の該当する石の個数－相手の該当する石の個数】を計算し（優先度低のみは自分と相手が逆）、高かったものを採用する（上位の優先度の基準で差が付いたら、下位の優先度の基準は考慮しない）。それでもすべて一致するなら、石の個数で判断する。
補足
さて先読みをする際に、今回は手数を決めて打ち切ったわけだが、もし「すべての手数まで先読みできる」とすれば（実際には計算時間上困難なのだが）、
- 自分が必ず勝てる手を指せる
- 自分がどう頑張っても勝てないとわかる（相手が必ず勝てる手を指せる）
- 引き分けになる
のどれかに行き着く。これはオセロに限らず囲碁や将棋などでもほぼ同様なのだが、自分も相手も「指せる手の可能性」「それによって起こる盤面の変化」が明確に定められている（＝自分がシミュレーションできる）ことに起因する。二人零和有限確定完全情報ゲーム - Wikipediaあたりを参照。
成績
実際に対戦させた結果は以下の通り。「D2」「D4」はそれぞれ、先読みする深さ（depth）を2手先・4手先までにしたことを意味する。
まずは先読みなしのAI。
| AI名 | 先読みなしの 相手との戦績 |
先読みありの 相手との戦績 |
合計戦績 |
|---|---|---|---|
| M1 | 1勝5敗 | 1勝11敗 | 2勝16敗 |
| M2 | 1勝5敗 | 0勝12敗 | 1勝17敗 |
| M3 | 4勝2敗 | 5勝 7敗 | 9勝 9敗 |
| M4 | 6勝0敗 | 5勝 7敗 | 11勝 7敗 |
続いて先読みありのAI。
| AI名 | 先読みなしの 相手との戦績 |
先読みありの 相手との戦績 |
合計戦績 |
|---|---|---|---|
| M2-D2 | 4勝4敗 | 0勝10敗 | 4勝14敗 |
| M2-D4 | 4勝4敗 | 3勝 7敗 | 7勝11敗 |
| M3-D2 | 8勝0敗 | 8勝 2敗 | 16勝 2敗 |
| M3-D4 | 5勝3敗 | 4勝 6敗 | 9勝 9敗 |
| M4-D2 | 8勝0敗 | 7勝 3敗 | 15勝 3敗 |
| M4-D4 | 8勝0敗 | 8勝 2敗 | 16勝 2敗 |
先読みありのAIは、先読みなしのAIと対局させた場合、M3やM4こそ強いもののM2はそこまで強くならなかった。これは、先読みを打ち切った直後に相手にいい反撃の手がある場合もあることに起因するとされている。
また、先読みなしのM3やM4は、M4-D2やM4-D4にこそ勝てていないものの、他の先読みありの方法には勝っていたりする。オセロでは、先読みの効果もあるにはあるものの、それ以上に手作業での手の構築が重要なのかな？と感じた結果であった。
まとめ
- オセロAIを、まず自分で条件を逐一書いていって手を決める方法で作り、次いでそれに先読みさせることを加えるという形で作った。
- オセロの場合、先読みで強くなるにはなるが、元となる指す手の条件がうまくできていないと先読みの効果は出てこない。
詳細な対戦戦績
| 先手＼後手 | M1 | M2 | M3 | M4 | M2-D2 | M2-D4 | M3-D2 | M3-D4 | M4-D2 | M4-D4 |
|---|---|---|---|---|---|---|---|---|---|---|
| M1 | 19＼45 | 23＼41 | 7＼57 | 21＼43 | 0＼27 | 0＼27 | 18＼46 | 14＼50 | 0＼43 | 0＼52 |
| M2 | 30＼34 | 19＼45 | 22＼42 | 3＼60 | 5＼59 | 0＼31 | 9＼55 | 18＼46 | 8＼56 | 20＼44 |
| M3 | 29＼0 | 43＼21 | 20＼44 | 18＼46 | 39＼25 | 39＼25 | 18＼46 | 33＼31 | 19＼45 | 13＼51 |
| M4 | 49＼15 | 50＼0 | 39＼25 | 26＼38 | 37＼26 | 45＼19 | 27＼37 | 36＼28 | 11＼52 | 25＼39 |
| M2-D2 | 55＼7 | 47＼17 | 20＼44 | 0＼41 | 4＼60 | 27＼37 | 21＼43 | 27＼37 | 18＼46 | 12＼52 |
| M2-D4 | 17＼47 | 48＼16 | 35＼29 | 5＼59 | 38＼26 | 36＼28 | 29＼35 | 23＼41 | 15＼49 | 3＼60 |
| M3-D2 | 35＼29 | 39＼25 | 46＼18 | 43＼21 | 56＼8 | 49＼15 | 37＼27 | 38＼26 | 29＼35 | 36＼28 |
| M3-D4 | 34＼30 | 46＼18 | 31＼33 | 39＼25 | 43＼21 | 31＼33 | 30＼34 | 42＼22 | 29＼35 | 50＼14 |
| M4-D2 | 50＼0 | 62＼2 | 47＼17 | 46＼18 | 56＼4 | 56＼8 | 27＼37 | 37＼27 | 35＼29 | 12＼52 |
| M4-D4 | 62＼2 | 55＼9 | 44＼20 | 46＼18 | 59＼1 | 54＼10 | 44＼20 | 59＼5 | 41＼23 | 37＼27 |