人工知能に関する断創録

このブログでは人工知能のさまざまな分野について調査したことをまとめています(更新停止: 2019年12月31日)

AIの実装/ミニマックス法

コンピュータと対戦できるようにAIを実装します。ここでは思考ゲームのもっとも基本的なアルゴリズムであるミニマックス法について解説します。

othello06.jar

プレイヤーとAIが交互に打つ

AIとは人工知能(Artificial Intelligence)のことです。人工知能って言うと大げさですけどね。簡単に言うと対戦相手のコンピュータのことです。前回は黒石も白石も全部プレイヤーが打っていました。そこで今回は白石をAIに任せてプレイヤーと対戦できるようにしていきます。プレイヤーは黒石です。AIの詳細を説明する前に実装の全体を示します。

    // AI
    private AI ai;

    public MainPanel(InfoPanel infoPanel) {
        ・・・
        // AIを作成
        ai = new AI(this);
        ・・・
    }

AIクラスのオブジェクトを作っています。このAIクラスに思考ルーチン(AIがどのように石を打つかの考え方)を実装していきます。次にプレイヤーとAIが交互に打てるようにmouseClicked()を変更します。

    /**
     * マウスをクリックしたとき。石を打つ。
     */
    public void mouseClicked(MouseEvent e) {
        switch (gameState) {
            ・・・
            case PLAY :
                // どこのマスかを調べる
                int x = e.getX() / GS;
                int y = e.getY() / GS;

                // (x, y)に石が打てる場合だけ打つ
                if (canPutDown(x, y)) {
                    // 戻せるように記録しておく
                    Undo undo = new Undo(x, y);
                    // その場所に石を打つ
                    putDownStone(x, y, false);
                    // ひっくり返す
                    reverse(undo, false);
                    // 手番を変える
                    nextTurn();
                    // 終了したか調べる
                    endGame();
                    // AIが石を打つ
                    ai.compute();
                }
                break;
            ・・・
        }
    }

プレイヤーが石を打った後、AIが石を打つ処理compute()を挿入しています。compute()ではミニマックス法で石を打つ位置を決め、実際に白石を打つ処理です。こうするとmouseClicked()でプレイヤーが石を打ったあとAIが石を打つようになります。

Undoクラス

Undoは盤面を戻すために必要なクラスです。Undoを使うと石を打ってひっくり返したあとでも石を打つ前の盤面に戻すことができます。Undo で管理する情報は

  • 石を打った場所
  • 打った石によってひっくり返された石の数
  • ひっくり返された石の座標

です。ひっくり返された石の座標を覚えておけば、もう一度ひっくり返して元通りになります。また石を打った場所を覚えておけばその石を取り除いてもとの盤面に戻せます。

    public class Undo {
        // 石を打つ場所
        public int x;
        public int y;
        // ひっくり返った石の数
        public int count;
        // ひっくり返った石の場所
        public Point[] pos;
    
        public Undo(int x, int y) {
            this.x = x;
            this.y = y;
            count = 0;
            pos = new Point[64];
        }
    }

Undoがなぜ必要かというとそれは「待った!」の機能を入れるため・・・というのは嘘です(がUndoを使えば簡単に追加できます)。実はミニマックス法を実装する上で盤面を戻す機能が必要だからです。ミニマックス法はAIが「あーでもないこーでもない」というふうにいろいろなところに石を打っていい場所を探す処理なんです。AIは盤面に石を打ってひっくり返してを繰り返していい場所を探していきます。そのとき盤面を元に戻す必要があるわけです。人が頭の中で盤面を先読みする場合と同じですね。Undoの具体的な使い方を見てみます。

    // (x, y)に石が打てる場合だけ打つ
    if (canPutDown(x, y)) {
        // 戻せるように記録しておく
        Undo undo = new Undo(x, y);
        // その場所に石を打つ
        putDownStone(x, y, false);
        // ひっくり返す
        reverse(undo, false);
    }

まずcanPutDown(x,y)で石が(x,y)に打てることを確かめています。そしてnew Undo(x,y)でUndoオブジェクトを作っています。Undoの引数の(x,y)は(x,y)に石を打ったことを表しています。そして実際に石を putDownStone()で打ち、reverse()でひっくり返しています。ここでreverse()にundoを与えているのがミソです。ひっくり返すときにundoにひっくり返した石の場所を記録しています。

    // ひっくり返した場所を記録しておく
    undo.pos[undo.count++] = new Point(x, y);

こうすれば石を打った場所、ひっくり返した石の場所がundoに記録されます。盤面を元に戻したいときはundoBoard()を使います。

    /**
     * オセロ盤を1手手前の状態に戻す。 AIは石を打ったり戻したりして盤面を評価できる。
     * 
     * @param undo ひっくり返した石の情報。
     */
    public void undoBoard(Undo undo) {
        int c = 0;

        while (undo.pos[c] != null) {
            // ひっくり返した位置を取得
            int x = undo.pos[c].x;
            int y = undo.pos[c].y;
            // 元に戻すには-1をかければよい
            // 黒(1)は白(-1)に白は黒になる
            board[y][x] *= -1;
            c++;
        }
        // 石を打つ前に戻す
        board[undo.y][undo.x] = BLANK;
        // 手番も元に戻す
        nextTurn();
    }

undoに記録されているひっくり返した石の場所を1つずつ調べ、-1をかけて元に戻しています。黒は1、白は-1なので-1をかければひっくり返したことになります。最後に石を打った場所を空白に戻し、手順を戻せば完全に盤面が元通りになります。注意ですがundoは1手前にしか戻せません。待った!を実装したいときはundoBoard()を呼び出せるようにすればいいわけです。真剣勝負に待ったは卑怯ですけどね。

AIクラス

いよいよこの章の最大の山場AIを実装する処理です。AIが使う機能は全部AIクラスにまとめて実装します。まずAIのコンストラクタです。

    /**
     * コンストラクタ。メインパネルへの参照を保存。
     * 
     * @param panel メインパネルへの参照。
     */
    public AI(MainPanel panel) {
        this.panel = panel;
    }

コンストラクタでメインパネル(盤面)への参照を渡しています。panelはAIクラスから盤面を操作したり、盤面の情報を得るために必要となります。次にAIが打つ場所を決定して実際に白石を打つcompute()を見てみます。

    /**
     * コンピュータの手を決定する。
     *  
     */
    public void compute() {
        // ミニマックス法で石を打つ場所を決める
        // 戻ってくる値は bestX+bestY*MASU
        int temp = minMax(true, SEARCH_LEVEL);

        // 場所を求める
        int x = temp % MainPanel.MASU;
        int y = temp / MainPanel.MASU;

        // 打った場所、ひっくり返した石の位置を記録
        Undo undo = new Undo(x, y);
        // その場所に実際に石を打つ
        panel.putDownStone(x, y, false);
        // 実際にひっくり返す
        panel.reverse(undo, false);
        // 手番を変える
        panel.nextTurn();
    }

最初にminMaxで打つ場所(x,y)を決めます(どう決めるかはあとで説明します)。あとはプレイヤーと同じですね。undoオブジェクトを作ってから実際に石を打ち、石をひっくり返しています。プレイヤーの場合と比較してみてください。AIの場合はcanPutDown()、石を打てるか調べる処理がぬけてます。これはminMax()で決定した打つ場所(x,y)には必ず石が打てることが保証されているからです。必ず打てるのでcanPutDown()でわざわざチェックする必要はないわけです。次はミニマックス法でAIが石を打つ場所(x,y)をどう決めるかを見ていきます。

ミニマックス法とは

ミニマックス法を説明する前にゲーム木の説明から始めます。オセロ、チェス、将棋、碁、バックギャモン、チェッカーといった思考ゲームと呼ばれるゲームではゲーム木を使ってゲームを表現します。ゲーム木はゲームの最初の状態からの局面を表現したものです。下にオセロのゲーム木の一部を示します。

f:id:aidiary:20100518105930g:plain

ゲームの最初は黒の手番です。黒が打てるところは4箇所あります。そのそれぞれに対して打った場合の盤面が2段目です(4つ描くの大変なので3つに省略してあります)。次は白の手番です。黒の打った盤面それぞれに対して白はいくつか打てる場所があります。そのそれぞれに対して打った場合が3段目です(全部描くと大変なので2つに省略してあります)。このようにゲームのすべての可能性を木構造で表したのがゲーム木です。ゲーム木を描くのに上のようにオセロ盤をいちいち描いていたら非常に大変なので次のように省略して描くことにします。

f:id:aidiary:20100518105931g:plain

局面を□で囲んであります。□のことをノード(節)と呼び、ノードをつないでいる線を枝と呼びます。ノードは局面を表し、枝は着手(実際に石を打つこと)を表します。薄く塗られているノードのは黒の局面です。太い枝は黒の着手です。ノードの中の番号は参照しやすくするためにふった番号です。[N0] のことをルートノードと呼びます。また[N1][N2][N3]は[N0]の下にあるので[N0]の子ノードと呼び、[N0]は[N1][N2][N3] の親ノードと呼びます。

人がオセロをするときにはある手を打ったらどのような局面になるかを予想してその着手がよいか悪いか判断しています。へぼでも1手先くらい読みますよね?ここに打ったら相手に大量にひっくり返されちゃうからやめようとか考えるはずです。このような何手か先を予想して着手を決めることを「先読み」と呼びます。ここでは人ではなくAIに「先読み」をやらせたいわけです。AIが先読みをするにはゲーム木の探索を行います。

ゲーム木を説明したので次はミニマックス法(ゲーム木の探索手法)の説明に入ります。ミニマックス法は先読みを行って最適な手を探索するアルゴリズムです。ここでは2手先読みの例でミニマックス法を説明します。AIは白なので白をルートノードにします。[N1]で[N2]へ行く手と[N3]へ行く手のどっちを打てば最適かを探すわけです。

f:id:aidiary:20100518105932g:plain

まず[N1]で白(AI)は[N2]と[N3]のどっちがよいか調べます(1手先読み)。2手先読みするのでまだどっちか決めません。さらに先を読みます。次に[N2]で黒が打ってくるすべての手を調べ、その先の局面[N4]と[N5]を求めます。2手先読みですのでここで[N4]と[N5]の盤面評価値を求めます。盤面評価値とは白(AI)にとってその盤面がどれだけ望ましいかを表す値です。ここでは[N4]が8、[N5]が10としましょう。えっ、8と10はどっから出てきたかって?これは次回の盤面評価で取り上げます。

[N4]と[N5]を調べたので[N2]に戻ります。[N2]の評価値はいくつでしょうか?ここがミニマックス法の真髄です。[N2]は黒(プレイヤー)の手番です。白(AI)が手を選択することはできません。あなたなら[N4]へ行く手と[N5]へ行く手のどっちを選びますか?普通、黒(プレイヤー)は白(AI)に不利な方を選択するはずです。つまり[N4]と[N5]の評価値の低い方(MIN)[N4]を選択します。よって黒の手番[N2]の評価値は8です。

[N2]の方は2手先読みが終了したので次に[N3]の方を先読みします。[N3]はとりあえず2手先読みするまで評価を保留します。[N6]と [N7]の評価値が2と15だとしましょう。[N3]は黒の手番なので必ず評価値の低い方[N6]を選択します。よって、[N3]の評価値は2です。黒は [N7]を白に選ばせてはくれないのです。

[N3]の方も2手先読みが終了したので[N1]に戻ります。さて、白は[N1]で[N2]と[N3]のどちらを選びましょう?もちろん評価値の高い方(MAX)[N2]を選びます。[N3]を選んでしまうと次の黒で[N6]を選ばれて評価値が2になってしまうからです。8の方が得ですよね?

これで白(AI)の手が決まりました。お気づきだとは思いますがミニマックス法はMIN-MAX法です。まとめると

  • 白(AI)の手番では子ノードのうち最大(MAX)の評価値を持つ局面へ行く手を選ぶ
  • 黒(対戦相手)の手番では子ノードのうち最小(MIN)の評価値を持つ局面へ行く手を選ぶと予想する

となります。

ミニマックス法の実装

ミニマックス法はAIクラスのminiMax()です。

    /**
     * ミニマックス法。最善手を探索する。打つ場所を探すだけで実際には打たない。
     * 
     * @param flag AIの手番のときtrue、プレイヤーの手番のときfalse。
     * @param level 先読みの手数。
     * @return 子ノードでは盤面の評価値。ルートノードでは最大評価値を持つ場所(bestX + bestY * MAS)。
     */
    private int minMax(boolean flag, int level) {
        // ノードの評価値
        int value;
        // 子ノードから伝播してきた評価値
        int childValue;
        // ミニマックス法で求めた最大の評価値を持つ場所
        int bestX = 0;
        int bestY = 0;

        // ゲーム木の末端では盤面評価
        // その他のノードはMIN or MAXで伝播する
        if (level == 0) {
            // 実際は盤面を評価して評価値を決める
            // ここではとりあえず0にしておく
            return 0;
        }

        if (flag) {
            // AIの手番では最大の評価値を見つけたいので最初に最小値をセットしておく
            value = Integer.MIN_VALUE;
        } else {
            // プレイヤーの手番では最小の評価値を見つけたいので最初に最大値をセットしておく
            value = Integer.MAX_VALUE;
        }

        // 打てるところはすべて試す(試すだけで実際には打たない)
        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 = minMax(!flag, level - 1);
                    // 子ノードとこのノードの評価値を比較する
                    if (flag) {
                        // AIのノードなら子ノードの中で最大の評価値を選ぶ
                        if (childValue > value) {
                            value = childValue;
                            bestX = x;
                            bestY = y;
                        }
                    } else {
                        // プレイヤーのノードなら子ノードの中で最小の評価値を選ぶ
                        if (childValue < value) {
                            value = childValue;
                            bestX = x;
                            bestY = y;
                        }
                    }
                    // 打つ前に戻す
                    panel.undoBoard(undo);
                }
            }
        }

        if (level == SEARCH_LEVEL) {
            // ルートノードなら最大評価値を持つ場所を返す
            return bestX + bestY * MainPanel.MASU;
        } else {
            // 子ノードならノードの評価値を返す
            return value;
        }
    }

けっこうでかいメソッドです。順番に説明していきます。まずminMax()を呼び出しているcompute()を見てみます。

    public void compute() {
        // ミニマックス法で石を打つ場所を決める
        // 戻ってくる値は bestX+bestY*MASU
        int temp = minMax(true, SEARCH_LEVEL);
        ・・・
    }

trueとSEARCH_LEVELを引数としています。trueはAIの手番(白)であることを意味します。falseの場合はプレイヤーの手番(黒)です。SEARCH_LEVELは先読みの深さです。先の図では2手先読みしていたので2となります。今回は5に設定して5手先まで先読みするようにしてあります。5手ですので図を描くのは結構大変ですが基本は2手先読みの場合と同じです。

minMax()は再帰的に呼び出されます。再帰はなれるまで理解しにくいのですがminMax()の中でさらにminMax()を呼び出すって意味です。図で描くと下のようなイメージです。

f:id:aidiary:20100518112439g:plain

minMax()が呼ばれる順序は赤[N1]、青左[N2]、緑左[N4]、緑右[N5]、青右[N3]、緑左[N6]、緑右[N7]の順序です。緑の場合はlevel=0で呼び出されるので盤面の評価値を求めて返します。今回はとりあえず0にしちゃってます。正しい盤面評価は次回取り上げます。

    // ゲーム木の末端では盤面評価
    // その他のノードはMIN or MAXで伝播する
    if (level == 0) {
        // 実際は盤面を評価して評価値を決める
        // ここではとりあえず0にしておく
        return 0;
    }

[N4]と[N5]が求まったら[N2]のvalueを計算します。[N2]は黒(プレイヤー)の手番なのでMINを見つけます。

    // プレイヤーのノードなら子ノードの中で最小の評価値を選ぶ
    if (childValue < value) {
        value = childValue;
        bestX = x;
        bestY = y;
    }

[N6]と[N7]も緑なので盤面評価値を返します。[N3]でも[N2]と同様に黒の手番ですのでMINを見つけます。[N2]と[N3]の valueが見つかったら[N1]に戻ります。[N1]は白(AI)の手番なのでMAXを見つけます。

    // AIのノードなら子ノードの中で最大の評価値を選ぶ
    if (childValue > value) {
        value = childValue;
        bestX = x;
        bestY = y;
    }

こうして[N1]のvalueは8になります。[N1]はルートノードなので最後のif文によってミニマックス法で求めた最適な打つ場所が返されます。

    if (level == SEARCH_LEVEL) {
        // ルートノードなら最大評価値を持つ場所を返す
        return bestX + bestY * MainPanel.MASU;
    }

メソッドの戻り値として1つしか返せません。なので(bestX,bestY)を上の式で計算して1つの数値として返しています。この数値から元の (bestX,bestY)を求めたい場合は下のようになります。

    // 場所を求める
    int x = temp % MainPanel.MASU;
    int y = temp / MainPanel.MASU;

minMax()の途中にある

    Undo undo = new Undo(x, y);
    // 試しに打ってみる(盤面描画はしないのでtrue指定)
    panel.putDownStone(x, y, true);
    // ひっくり返す(盤面描画はしないのでtrue指定)
    panel.reverse(undo, true);
    // 手番を変える
    panel.nextTurn();

は盤面を変化させます。先読みするために盤面を変化させていかないとだめだからです。ただし、putDownStone()やreverse()の引数にundoとtrueを与えています。trueにすると盤面が描画されなくなります。AIの先読みによる盤面評価は画面には反映されません。 falseにするとAIの先読み過程が見られます。AIの先読みで盤面は変化してしまいますが、変化した後、undoBoard()を呼び出しているので元に戻ります。

    // 打つ前に戻す
    panel.undoBoard(undo);

AIは打って戻して、打って戻してを繰り返して先読みしているわけです。結構複雑ですね・・・ちなみに次回はもっと簡単です。