AIの実装/α-β法

ミニマックス法を改良したα-β法を実装してみます。α-β法は枝刈り（必要のないところは先読みしないこと）をすることによって効率的に先読みを行うアルゴリズムです。ミニマックス法より深く先読みができるためAIを強くすることができます。ゲーム木の解説はミニマックス法のページに書いてあるので先に見てください。

othello10.jar

αカット

上の図は[N2]までの評価が決まった状態を表しています。[N2]はMINなので[N4]と[N5]のうち小さいほうを選択しています。次に [N1]に戻ります。[N1]は[N2]と[N3]の評価値のうちMAXを選ぶので[N3]の評価値がわからない現状では評価できません。しかし、[N1]の評価値は8より大きいことは確定しています。この理屈はわかるでしょうか？[N3]が8より小さければ[N2]の8が選ばれますし、[N3]が8より大きければ[N3]が選ばれます。どっちにしても[N1]の評価値は8以上になります。このようにノードの評価値がX以上であることが確定したとき、そのXをα値と呼びます。

先読みを進めます。[N3]はまだ評価できないので[N6]を調べます。[N6]は末端なので盤面評価を行います。ここでは2だったとしましょう。

ここで、[N3]は[N6]と[N7]のうちMINを選ぶので[N7]の評価値がわからない現状では評価できません。しかし、[N3]の評価値は2 より小さいことは確定しています。この理屈はわかるでしょうか？[N7]が2より小さければ[N7]が選ばれますし、[N7]が2より大きければ[N6] の2が選ばれます。どっちにしても[N3]の評価値は2以下になります。このようにノードの評価値がY以下であることが確定したとき、そのYをβ値と呼びます。

ここからがα-β法の本質です。[N1]は8（α値）以上の評価値になり、で[N3]が2（β値）以下の評価値になるということは[N1]で [N3]は絶対に選ばれないことになります。つまり、[N7]を評価しなくても[N3]が選ばれないことはわかるわけです。

このように子ノードの評価値がα値より小さいために枝を切り落とすことをαカットと呼びます。実装上は[N3]が親ノードである[N1]のα値をメソッドの引数で受け継いでいます。[N3]の子ノードの評価値（2）とα値を比べて、子ノードの評価値がα値より小さいとわかったら先読みを中止して親ノードに処理を戻します。

βカット

今度は逆のパターンを考えます。ルートがMINの手番の場合です。

上の図は[N6]までの評価が決まった状態を表しています。[N6]はMAXなので[N8]と[N9]のうち大きいほうを選択しています。次に [N3]に戻ります。[N3]は[N6]と[N7]の評価値のうちMINを選ぶので[N7]の評価値がわからない現状では評価できません。しかし、[N3]の評価値は2より小さいことは確定しています。つまり、[N3]のβ値は2です。

先読みを進めます。[N7]はまだ評価できないので[N10]を調べます。[N10]は末端なので盤面評価を行います。ここでは10だったとしましょう。

ここで、[N7]は[N10]と[N11]のうちMAXを選ぶので[N11]の評価値がわからない現状では評価できません。しかし、[N7]の評価値は10より大きいことは確定しています。つまり、[N7]のα値は10です。

ここからがα-β法の本質です。[N3]は2（β値）以下の評価値になり、で[N7]が10（α値）以上の評価値になるということは[N3]で [N7]は絶対に選ばれないことになります。つまり、[N11]を評価しなくても[N7]が選ばれないことはわかるわけです。

このように子ノードの評価値がβ値より大きいために枝を切り落とすことをβカットと呼びます。実装上は[N7]が親ノードである[N3]のβ値をメソッドの引数で受け継いでいます。[N7]の子ノードの評価値（10）とβ値を比べて、子ノードの評価値がβ値より大きいとわかったら先読みを中止して親ノードに処理を戻します。

まとめると

• MINノードの評価値が親から受け継いだα値より小さかったらそれ以上の先読みは必要ない（αカット）
• MAXノードの評価値が親から受け継いだβ値より大きかったらそれ以上の先読みは必要ない（βカット）

となります。

α-β法の実装

大部分はミニマックス法と同じです。追加部分を赤字にしました。

    /**
     * α-β法。最善手を探索する。打つ場所を探すだけで実際には打たない。
     * 
     * @param flag AIの手番のときtrue、プレイヤーの手番のときfalse。
     * @param level 先読みの手数。
     * @param alpha α値。このノードの評価値は必ずα値以上となる。
     * @param beta β値。このノードの評価値は必ずβ値以下となる。
     * @return 子ノードでは盤面の評価値。ルートノードでは最大評価値を持つ場所（bestX + bestY * MAS）。
     */
    private int alphaBeta(boolean flag, int level, int alpha, int beta) {
        ・・・
        // 打てるところはすべて試す（試すだけで実際には打たない）
        for (int y = 0; y < MainPanel.MASU; y++) {
            for (int x = 0; x < MainPanel.MASU; x++) {
                if (panel.canPutDown(x, y)) {
                    Undo undo = new Undo(x, y);
                    // 試しに打ってみる（盤面描画はしないのでtrue指定）
                    panel.putDownStone(x, y, true);
                    // ひっくり返す（盤面描画はしないのでtrue指定）
                    panel.reverse(undo, true);
                    // 手番を変える
                    panel.nextTurn();
                    // 子ノードの評価値を計算（再帰）
                    // 今度は相手の番なのでflagが逆転する
                    childValue = alphaBeta(!flag, level - 1, alpha, beta);
                    // 子ノードとこのノードの評価値を比較する
                    if (flag) {
                        // AIのノードなら子ノードの中で最大の評価値を選ぶ
                        if (childValue > value) {
                            value = childValue;
                            // α値を更新
                            alpha = value;
                            bestX = x;
                            bestY = y;
                        }
                        // このノードの現在のvalueが
                        // 親から受け継いだβ値より大きかったら
                        // この枝が選ばれることはないのでこれ以上評価しない
                        // = forループをぬける
                        if (value > beta) {  // βカット
                            // 打つ前に戻す
                            panel.undoBoard(undo);
                            return value;
                        }
                    } else {
                        // プレイヤーのノードなら子ノードの中で最小の評価値を選ぶ
                        if (childValue < value) {
                            value = childValue;
                            // β値を更新
                            beta = value;
                            bestX = x;
                            bestY = y;
                        }
                        // このノードの現在のvalueが
                        // 親から受け継いだα値より小さかったら
                        // この枝が選ばれることはないのでこれ以上評価しない
                        // = forループをぬける
                        if (value < alpha) {  // αカット
                            // 打つ前に戻す
                            panel.undoBoard(undo);
                            return value;
                        }
                    }
                    // 打つ前に戻す
                    panel.undoBoard(undo);
                }
            }
        }

        ・・・
    }

上で説明したのをほとんどそのまま実装しました。コメントも書いてあるので特に説明はいらないでしょう。ミニマックス法からα-β法を使うように変えたのでcompute()ではminMax()ではなくてalphaBeta()を呼び出しています。

    public void compute() {
        // α-β法で石を打つ場所を決める
        // 戻ってくる値は bestX+bestY*MASU
        int temp = alphaBeta(true, SEARCH_LEVEL, Integer.MIN_VALUE, Integer.MAX_VALUE);
        ・・・
    }

最初に呼び出す場合はα=-∞、β=∞とします。α-β法は先読み時に枝刈りができるためミニマックス法に比べて効率がいいです。そのため、SEARCH_LEVELを少しだけあげることができます。私のコンピュータではミニマックス法では5手先読みが限界だったのですが、α-β法では7手まで先読みできるようになりました。

追記

実はalphaBeta()内でvalueを使わず、alphaとbetaだけを使って書き直すことができます。ただ、すこしわかりづらくなるのでここではvalueを使って書きました。