マンカラ (mancala)というゲームについて２ 【ミニマックス法】

みなさん、こんにちはこんばんは。S.Kと申します。

少し前にマンカラというゲームがあることを記事にしました。

この記事の中で

さて、AIでも作るかー・・・と思った次第です。

と言ってましたが、零和有限確定完全情報ゲームと相性の良いミニマックス法で実装してみました。αβ法にするのは次回にします。

ミニマックス法

ミニマックス法というのはコンピュータからみて
プレイヤーがコンピュータにとって最悪な手（＝最大の損失）をとるとし
コンピュータはその中から最善の手（＝最小の損失）をとると仮定して意思決定を行います。
つまり最大損失を最小化するわけですね。MinMax(損失)ということです。

有限のゲームなので必ず終点が存在しますが、その終点でのゲームの状況に対して評価をする必要があります。今回はプレイヤー側の石の総数が多ければ良い評価にし（プレイヤー側が不利とみなす）コンピュータ側の石が多ければ悪い評価とする、としています。つまり

評価値＝プレイヤーの石の数 - コンピュータ側の石の数

これも現時点での仮定なので、将来的に別の評価関数に変わる可能性があります。

コンピュータは自分の手番にきた時に、どの穴を選ぶとよいか、を考える必要があります。例えば0, 1, 2という３つの穴があるとして、0を選んだ場合、1を選んだ場合、2を選んだ場合のそれぞれの評価値を計算し、もっとも評価値の高い穴を選びます。
この評価値計算のときに、ミニマックスでの仮定のもとで、プレイヤーとコンピュータ自身がゲームをプレイしていくとして、評価値を計算するわけです。

C=コンピュータ
P＝プレイヤー
として以下のような樹形図がかけます。一番上のノード（点）が現時点とします。

左下側のCについて、真ん中の手を選ぶのが値が大きくなるので最適です。

左側のプレイヤーのノードでは値が最小（コンピュータにとって損失が最大）となるように手を選びます。この場合-2となるような手を選ぶとします。

現時点のコンピュータの手番に戻ってきたときに損失の一番小さいものを選びます。以下の例であれば評価値が1となる手です。

上のようなことをやるのがミニマックス法で、少ない選択肢であればいいですが、選択肢が増えると計算がかかりそうですよね？そのため、αβ法などの工夫が必要になります。

Pythonプログラム

さて、愚直にプログラム書いてみたのですが、先読みの手数を増やすと当然強いです。簡単に負けます（自分が下手すぎる）。

コンソール上でプレイしてる様子：

  3**3**3  
0*********0
 3**3**3  
数字を0 - 2の範囲から１つ選んでください
0
あなたの選択は 0 です
 3**3**3  
0*********1
 0**4**4  
CPUの選択は 6 です
 0**3**3  
1*********1
 1**5**4  
 
 ・・・（省略）・・・
 
 数字を0 - 2の範囲から１つ選んでください
0
あなたの選択は 0 です
 4**0**0  
6*********3
 0**5**0  
CPUの選択は 6 です
 0**0**0  
7*********3
 1**6**1  
You lose!

プログラムが正しく動いてそうなのですが、まだ公開するには早いです。αβ法の実装やルール変更できるように実装、およびGUIでのプレイ可能までできたら公開しようかなと思います。

ではまた。

チャンネル

SK-GameTheory

チャンネル登録よろしくお願い致します。