深さ優先探索:DepthFirstAIPlayer

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

原理

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

・手の数が有限である

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

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

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

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

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

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

思考アルゴリズム

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

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

c盤まで黒白がもつれる拮抗したゲームになったようですね。

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

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

もう一段遡ってみましょう。
b-1 は石を置ける場所一箇所だけですから、c-1 の結果が自動的に繰り上がります。

一方、b-2 はどうなるでしょうか?
石を置ける場所が二箇所あり、一方は c-2:○(白) の勝ちにつながっており、もう一方は c-3:●(黒) の勝ちにつながっています。

59手目は ●(黒) の番ですから、当然、●(黒) は自分が勝てる c-3 につながる手を打つはずです。
したがって、b-2 の時点で ●(黒) の勝ちが確定していることになります。

58手目も二股に分かれていますが、どちらに進んでも ●(黒) の勝ちが確定していますから、結局、a-1 の時点で既に ●(黒) の勝ちが確定していることになります。

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

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

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

強み

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

弱み

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

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

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

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

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

実装について

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

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

タイトルとURLをコピーしました