マンカラ (mancala)というゲームについて4 【αβ法】

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

前前回の記事でミニマックス法を紹介しました。

今回はこのミニマックス法を改良したαβ法について、書いていこうと思います。

αβ法

黄色の丸を自分、青色の丸を相手の手番とします。
ミニマックスで見たように、自分は評価値を最大化するように行動し、相手は評価値を最小化しようと行動します。

◆βカット◆

相手が1という選択をとった場合、すなわち一番左の自分のノードを考えます。
一番左の自分のノードでは、1, 3, 0のうち最大値である3を取るとして、評価値が3(赤字)となります。

次に、相手が2という選択をとった場合、すなわち真ん中の自分のノードを考えます。自分が1をとった場合に、そこで得られる評価値は4となり, 自分は最大化をすることを考えてるので、4以上が保証されたことになります。

さて、先ほど「相手が1という選択をとった場合の評価値は3(赤字)となる」といいました。相手の立場からして最小化を考えているので、3以下の評価(この3という上限をβと呼びます)となる選択を取りたいと考えています。ということは、相手にとって、2を選択することは4以上の評価値を取ることになります。これは相手は選びません。

したがって、選択2や3の評価値の計算する必要はありません。これをβカットと呼びます。

◆ αカット◆

同様にαカットがあります。
αという下限値を都度更新してそれを下回る場合にカットします。図で確認してみましょう。

ちょっと複雑に見えますが、説明します。
左側赤字で書かれてる相手のノードでは評価値が2となっています。
ということは、この画像の一番上にある自分ノードでは、1を選択することで、少なくとも2以上の評価値が保証されてます。この下限2をαと言います。

では、自分が2を選択した場合（赤四角の選択）の相手のノードを見てみます。
このとき、1を選択すれば3の評価値、2を選択すれば1となります。
この時点で3の選択を調べる必要はなくなりました（αカットと呼ぶ）。
なぜなら、
自分が2を選択した場合に、相手は最小となる評価値を取るため、1以下となることが保証されてしまいます。
そして、自分が1を選択したときは評価値2以上が保証されてます。つまり、少なくともこの時点で自分は2を選択する意味はなくなるからです。

＊＊＊＊＊

上記のような形で、
α、βを使って不必要なノード、選択肢を削除していきます。
当然、計算量は少なくなります。
また、結果はミニマックス法と同じになります。なので普通、αβ法を使った方が良いでしょう。
ちなみにαβ法は分枝限定法の一種です。

＊＊＊＊＊

いかがでしたでしょうか。
自分の整理のための記事です。近いうちにもう少し手直しして、動画にします。マンカラのプログラムで利用しているので、プログラムでの実装もお見せできればと思います。

では、別の記事でお会いしましょう。

マンカラ記事まとめ

マンカラ開発記｜S.K｜note