コンピュータはオセロや将棋などのゲームでどうやって最善手を計算しているのだろうか。皆さんの中には一度はそんな疑問を抱いたことがあるという方も多いでしょう。今回は、「MiniMax法」という最善に近い手を簡単に計算することができるアルゴリズムを、4×4のオセロを題材にご紹介します。

MiniMax法とは

MiniMax法とは、あり得る全ての局面に対して、両者が最善を尽くした場合の最終的な得点を計算し、それを基に次の手を選ぶ、いわゆる全探索的なアルゴリズムです。ただし、最善手は自分にとっては「最終的な得点を最大化する手」ですが、相手にとっては「最終的な得点を最小化する手」であることに注意しなければなりません。

例として、下図の局面の最善手を求める場合について、MiniMax法の動きを観察してみましょう。次のターンは白で、（最終的な白石の数）-（最終的な黒石の数）を最大化したいとします。

まず、今後のゲーム進行としてあり得るものを全部列挙します。下図に示すように、全部で3通りの進行が考えられます（この図では、石を打った場所を明るい色で示しています）。 次に、ゲーム終了時の自分の得点、つまり石の数の差を計算します。ゲームが終了した状態としてはG、H、Iの3つがあり、Gの石の数は白と黒で9対7、Hの石の数は10対6、I の石の数は7対9です。そのため、Gの得点は9−7=2点、Hの得点は10−6=4点、Iの得点は7−9=−2点となります。

この記事は
Members+会員の方のみ御覧いただけます

ログイン／無料会員登録

会員サービスの詳細はこちら