最善に近い手を計算するMiniMax法

コンピュータはオセロや将棋などのゲームでどうやって最善手を計算しているのだろうか。皆さんの中には一度はそんな疑問を抱いたことがあるという方も多いでしょう。今回は、「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点となります。

• 

続いて、各局面について、両者が最善を尽くした場合の最終的な得点を計算します。まずは終了1手前の局面からです。局面D、E、F全てにおいて、自分が打てる手は1通りしかないため、局面Dの最終的な得点は局面Gと同じ+2点、局面Eは局面Hと同じ+4点、局面Fは局面Iと同じ−2点となります。

次に、相手のターンである終了2手前の局面を考えます。まず局面Bについては、打てる手が局面Dに行く1通りしかないため、最終的な得点は局面Dと同じ+2点となります。問題は局面Cです。局面Cからは、相手は以下の2通りの手を打つことができます。

• 最下行の左から2番目に打ち、局面Eに行く（形勢+4点）

• 最下行の左から1番目に打ち、局面Fに行く（形勢−2点）

ここで相手にとって良い手はどちらでしょうか。「相手にとって良い」というのは「最終的な得点が低い」ということなので、後者を選んだ方が有利です。したがって、局面Cの最終的な得点は−2点となります。

• 

これで初期盤面を除く全ての局面について、最終的な得点を計算することができました。それでは、初期盤面で自分はどのような手を打つのが最適なのでしょうか。まず初期盤面では、以下の2通りの手を打つことができます。

• 最下行の左端に打ち、局面Bに行く

• 最下行の右端に打ち、局面Cに行く

ここで状態Bの形勢は+2点、状態Cの形勢は−2点であるため、前者の方が良いです。したがって、最善手は「最下行の左端に打ち、状態Bに行く」となります。このように、MiniMax法では、あり得る全ての局面をしらみつぶしに考えた上で、一番良い手を出力します。

MiniMax法の問題点

前章で紹介したMiniMax法は、全ての局面を考えているので必ず最善手を出せますが、1つ問題点があります。それは探索する局面の数が非常に多くなってしまうことです。先ほど紹介した例では9個の局面しか探索する必要がありませんでしたが、下図中央の場合は約700個、下図右側の場合は約12万個を探索する必要が出てきます。

• 

もちろん、この程度の個数であれば速いコンピュータを使えば数秒で計算が終わります。しかし、オセロの大きさが8×8になると、探索すべき局面の数が10⁵⁴個まで膨れ上がり、スパコン富岳を100年使っても計算できないレベルになってしまうのです。これでは使い物になりません。

改良版MiniMax法

そこで実際によく使われるのが、全ての局面を探索するのを諦め、何手か後の形勢を最大化する手を打つという方法です^※。

例として、下図の局面について2手先まで読む場合を考えます。ただし、オセロは角を打った方が優位だと言われているので、形勢は「角を5点、その他を1点としたときの白と黒の点差」とすることにします。

• 

まず、2手先までの局面を全て列挙します。下図に示すように、全部で3通りの進行が考えられます（この図では、石を打った場所を明るい色で示しています）。

次に、最後の局面について形勢を計算します。例えば、局面Iの場合はどうでしょうか。黒は角1個とそれ以外3個を持っているので、得点は5×1+3=8点となります。一方、白は角2個とそれ以外4個を持っているので、得点は 5×2 +4=14点となります。したがって形勢は8−14=−6点となります。

• 

続いて、1手前の局面（相手のターン）の形勢を計算します。まず局面Bについては、相手の打てる手として以下の3通りが考えられます。

• 最上列の左から4番目に打ち、局面Dに行く

• 最下列の左から2番目に打ち、局面Eに行く

• 最下列の左から4番目に打ち、局面Fに行く

ここで局面D、E、Fの形勢はそれぞれ−12、−8、−10点であり、相手は形勢を最小化する手を打つのが最適なので、局面Bの形勢は−12点となります。局面Cについても同じように考えると、形勢が−6点であることがわかります。

• 

これで初期盤面を除く全ての局面の形勢計算が終わったので、最後に初期盤面で打つべき手を考えます。初期盤面からは局面Bと局面Cに行く手がありますが、前者の形勢は−12点、後者の形勢は−6点であるため、後者を選んだ方が有利です。したがって、改良版 MiniMax法は「局面Cに行く手」を選択します。

このように改良版MiniMax法を使うと、探索すべきパターン数が抑えられるため、8×8オセロのような複雑なゲームでも打つべき手を短時間で出力することができます。一方、最後まで局面を読んでいるわけではなく、2手先や3手先の形勢に頼って打つ手を選択しているため。MiniMax法とは違って、必ず最善手を出すわけではないことに注意が必要です。

なお、より最善に近い手を出すには、読む手数を増やしたり、形勢の計算方法を工夫したりするなどの方法が考えられます。例えば、角に隣接するマスに打つと不利になることがあるので、そこに石が置かれている場合は形勢を1点減点するなどの工夫をすると、2～3手読むだけでもかなり最善に近い手を出すことができます。

※この方法のことをMiniMax法と呼ぶ場合もあります

*　*　*

本稿ではMiniMax法について解説しましたが、実はこれをより発展させた「AlphaBeta法」と いうアルゴリズムもあります。少し難しいのでここでは説明しませんが、興味のある方はぜひインターネット等で調べてみてください。