深さ優先探索:DepthFirstAIPlayer

DepthFirstAIPlayer は、深さ優先探索アルゴリズムにより手を先へ先へと読み進み、必勝手を探し出しすプレーヤーです。

DepthFirstAIPlayer01

原理

そもそもリバーシとはどのようなゲームなのでしょうか?
リバーシはチェスや将棋、囲碁とともに有限確定完全情報ゲームに分類され、次のような特徴を持ちます。

・手の数が有限である

ある手番のときに石を打てる位置の数は有限であり、黒白合わせて高々 60 回石を打てばゲームは終了します。従って、ゲームのパターンは有限通りしかありません。

・自分自身で手を確定できる

双六がサイコロの目に左右され麻雀が配牌に左右されるのとは対照的に、リバーシに運(偶然)の要素が入り込む余地はありません。自分の手を自分で決めることができます。

・ゲームに関する完全な情報を得ることができる

ポーカーや麻雀ではお互いにどのような手を持っているのかを知ることが出来ないのに対して、リバーシでは自分が指した手、相手が指した手、今現在のリバーシ盤の状態など、ゲームの状況に関するすべての情報がオープンにされています。

従って原理的には、すべての手を先読みし、最善な手を指すことができるはずです。
深さ優先探索はこの原理を利用しています。

思考アルゴリズム

DepthFirstAIPlayer は手を先へ先へと読み進みます。
ひとつの手を選んで次の手を、またひとつを選んで次の手を、と予測していきます。

DepthFirstAIPlayer02

手を読み進めるうちに、ゲーム終了時点まで辿り付きます。

DepthFirstAIPlayer03a

どうやらこの局面では ○(白) が優勢のようですね。

さて、上の図についてもう少しよく考えてみましょう。

ゲーム終了時点では勝ち負けが確定しているわけですが、その一つ手前の60手目では石を置ける場所が 1 つしかないため、選択の余地がありません。
そのため、実は60手目の段階ですでに勝敗が決していることになります。

DepthFirstAIPlayer04a

さらにもう一段遡れますね。59手目の c では二股に分かれていますが、どちらも ○(白) の勝ちにつながりますので、結局 ○(白) の勝ちということになります。

DepthFirstAIPlayer05a

さて、58手目はどうなるでしょうか?

58手目は ○(白) の番であり、「引分け」または「○の勝ち」に繋がる手を打てます。当然、○(白) は自分自身が勝つ 59-b または 59-c に繋がる手を打つべきでしょう。
結論としては、58手目の段階で ○(白) の勝ちが確定しており、そのためには 59-b または 59-c に繋がる手を打てば良いことになります。

DepthFirstAIPlayer06a

以上を一般化すると、ある手番のときに、自身の勝ちに繋がる手がひとつでもある場合はその時点で勝ちが確定しており、その勝ちに繋がる手を打てばよいことになります。
勝ちは無いが引き分けに繋がる手がある場合は引き分けに持ち込むことができ、いずれも無い場合は負けがその時点で確定していることになります。

DepthFirstAIPlayer07b

このアルゴリズムは「ミニマックス法」あるいは「アルファ・ベータ法」と呼ばれています。

アルファ・ベータ法を採用し必勝読みを行う DepthFirstAIPlayer は、このようにしてゲーム終了時点から順に遡ることにより、その時点での自身の勝ち負けと、勝ちに繋がる手(それが無い場合は引き分けに繋がる手)を探します。

強み

このように DepthFirstAIPlayer は以降の必要な全ての手を読んで必勝手を探すため、手を読み切れたときには盤石の強さを発揮します。
勝ちに繋がる手がひとつでもある場合はその必勝手を打ち続けるため、もはや対戦相手に勝ち目はありません。

弱み

リバーシでは手のパターン数が膨大な数にのぼるため、ゲームの終盤にならないと手を読み切ることができません。手を読み切れないとき、選択可能な手のなかでどの手が優れているのか分からないため、結局、他の方法で(例えばランダムに)手を決めるしかありません。
これが唯一にして最大の弱みです。

私のマシン(Surface Pro 3; Core i7 1.70-2.30 GHz, 8.00 GB RAM; 64bit Windows 10 Pro)では、1 分間に残り十数手分しか読むことができません。そして、対戦相手が強くなればなるほど、残り十数手の段階ではすでに勝敗が決している、つまり負けが確定していることが多いのです。

残り手数が 1 増えるごとに、読む必要のある手のパターン数は指数関数的に増えていくため、たとえ処理効率やマシンスペックを改善して処理能力を数倍に引き上げたとしても、精々もう一手分多く先読みできるようになるだけです。弱みの根本的な解決にはなりません。

チェスやリバーシ、将棋、囲碁などのゲームでコンピュータが長らく人間に勝てなかった理由はここにあります。近年、人間を打ち負かすコンピュータが出てきていますが、これらは工夫された別のアルゴリズムを採用しており、深さ優先探索アルゴリズムで全読みしているわけではありません。

深さ優先探索は比較的単純なアルゴリズムであり、実装も難しくありません。これで人間に勝ててしまっては面白みが無いというものです。膨大なパターン数が、これらのゲームをゲームたらしめ、AI プレーヤーの開発を挑戦し甲斐のある知的な問題にしていると言えるでしょう。

実装について

深さ優先探索を行うために、DepthFirstAIPlayer では再帰を利用しています。(ほかに、スタックを利用して実装する方法もあります。)
全ての手を読み切れないとき、DepthFirstAIPlayer はランダムに手を選びます。

ソースコードは「2. 題材の紹介」で公開しています。

決して難しいテクニックは必要でないため、ご自身でも実装にチャレンジしてみてください。

スポンサーリンク
reversi_main 336*280
reversi_main 336*280

シェアする

フォローする