オセロAIの教科書 5 【探索】 alphabeta法

にゃにゃん(山名琢翔)

2021年12月7日 00:00

こんにちは、にゃにゃんです。

この記事集「オセロAIの教科書」は私の世界1位AIの技術を中心に、オセロAI(オセロの相手をしてくれるプログラム)を初歩から段階を踏んで作っていく記事集です。全編無料でこちらから読めます。

この記事について、わかりにくい点や疑問点、おかしな点がありましたら気楽にコメントとかTwitterとかで教えて下さい。みなさんの力で記事を洗練したいです。

この記事を読むのに必要な知識

この記事を読むのに必要な(ある程度前提とする)知識を列挙します。これらの知識がない状態で読んでもある程度理解できるとは思いますが、途中でわからなくなったらキーワードとして使ってください。

オセロのルール
基礎的なプログラミングの知識・経験
C++
データ構造(ハッシュテーブル)

minimax法は遅い

前回の記事でminimax法を学びました。4手読みのサンプルプログラムでも結構強かったと思います。しかし、実はminimax法は非常に非効率的な探索です。

試しにサンプルコードの読み手数を7手にしてみてください。少し遅いなーと思うと思います。

int main() {
    init();
    int arr[64];
    board b;
    int ai_player, policy;
    cin >> ai_player;
    while (true) {
        input_board(arr);
        b.translate_from_arr(arr, ai_player);
        cerr << evaluate(b) << endl;
        b.print();
        policy = search(b, 4); // ここを4から7にする
        cout << policy / hw << " " << policy % hw << endl;
    }
    return 0;
}

minimax法を効率化するアイデア

高速化できる例として、こんなゲーム木を考えてみましょう。

これを、同じ深さのノードは左から順に見ていくとして探索します。

まずノードA->B->Dと辿って、ノードDで評価値を得ます。それをノードBに伝播して、ノードBのminimax値は10とわかりました。

ここで、ノードCについて、「興味がある範囲」を考えましょう。ノードCのminimax値がノードBのそれである10よりも大きければノードCに向かう手を次の着手として選びますが、そうでない場合、つまりノードCのminimax値が10以下である場合にはノードCのminimax値が何であれ探索結果は変わりません。つまり、ノードCについてはminimax値が10より大きいことにしか興味がありません。

さて、ではノードA->C->Eと見ていってノードEで評価値を得ましょう。結果は-7です。この手番は相手なので、ノードCのminimax値はmin(ノードEの評価値=-7, ノードFの評価値)となります。ノードFの評価値を調べなくても、この時点でノードCのminimax値は-7以下になることが確定しています。

ノードCのminimax値がノードBのそれである10以下であることがすでに確定している、つまりこの時点でノードCの興味の範囲を逸脱しているので、ノードFを辿って評価値を得る必要はありません。

少し難しいですが、指差し辿って確認してみてください。

alphabeta法とnegaalpha法

minimax法を上のアイデアで枝刈り(無駄な探索をカットすること)したのがalphabeta法です。

alphabeta法では、上で「興味がある範囲」と書いた範囲を、alphaとbetaという変数を使って[alpha, beta]の範囲で表します。ご察しの通り、alphabeta法の名前はこの範囲を決める変数名から来ています。

実装上は、negamax法のように、手番変更を-1を乗ずることで表して常にmax関数を使う方法を主に使います。これをnegaalpha法と言います。

実装を見てみましょう。サンプルコードは以下です。

// negaalpha法
int nega_alpha(board b, int depth, bool passed, int alpha, int beta) {
    // 葉ノードでは評価関数を実行する
    if (depth == 0)
        return evaluate(b);
    // 葉ノードでなければ子ノード全部に対して再帰する
    int coord, g, max_score = -inf;
    for (coord = 0; coord < hw2; ++coord) {
        if (b.legal(coord)) {
            g = -nega_alpha(b.move(coord), depth - 1, false, -beta, -alpha);
            if (g >= beta) // 興味の範囲よりもminimax値が上のときは枝刈り
                return g;
            alpha = max(alpha, g);
            max_score = max(max_score, g);
        }
    }
    // パスの処理 手番を交代して同じ深さで再帰する
    if (max_score == -inf) {
        // 2回連続パスなら評価関数を実行
        if (passed)
            return evaluate(b);
        b.player = 1 - b.player;
        return -nega_alpha(b, depth, true, -beta, -alpha);
    }
    return max_score;
}

// depth手読みの探索
int search(board b, int depth) {
    int coord, res = -1, score, alpha = -inf, beta = inf;
    for (coord = 0; coord < hw2; ++coord) {
        if (b.legal(coord)) {
            score = -nega_alpha(b.move(coord), depth, false, -beta, -alpha);
            if (alpha < score) {
                alpha = score;
                res = coord;
            }
        }
    }
    return res;
}

少し複雑になってきましたが、negamax法のアルゴリズムを改良しただけです。

サンプルコードはnegamax法では時間が結構かかっていた7手読みで書いてあります。実行して計算時間を体感してみましょう。

$ g++ -O3 ai3_negaalpha.cpp -o ai.out
$ python3 main.py

どうでしたか？私の環境では一瞬で計算が終わりました。

move ordering

alphabeta法やnegaalpha法は、枝刈りをなるべく増やすと高速になります。

例として出したこちらの木を見ると、

もし、最初に悪い手であるノードCを探索して、その後に良い手であるノードBを探索していたらどうでしょう。なんと枝刈りは起きないのです。

結論を言えば、alphabeta法には良さそうな手から探索すると枝刈りが多く起きるという特徴があります。良さそうな手から探索するために手を並べ替えることをmove orderingと言います。

move orderingを実現する方法はいくつかあります。

マスの重みを使う方法

今回、評価関数にマスの重みを使いましたが、それを同じものを手の並べ替えに使うことも可能です。この方法は高速でそれなりに良い方法だと言えます。

開放度を使う方法

オセロの中盤に良い手を見つける方法として、開放度という考え方があります。これは、石を置いたところとそれによってひっくり返った石について、その8近傍を調べて空マスの数を数えるというものです。

自分の石の周りに空マスが多いと、相手の着手可能位置が増えて自分に不利なので、なるべく開放度の小さい手を選ぶと良いと言われています。

これをオセロAIにも使えます。しかし、開放度の計算は厳密にやるには時間がかかったり、近似値を高速に求めるにも前計算が必要で、少しだるいです。

実は過去に私はmove orderingに開放度を使っていたことがあって、かなり性能は良かったです。

浅い探索を使う方法

これが世界1位AIにも使っているおすすめの方法です。

これまでの探索では、根ノード(入力された局面)から深さDの探索をするなら最初から深さDの探索をしていましたが、この方法では例えばまず最初にD-3の浅い探索をして、その後にD-2、D-1、D、と、深さを1ずつ増やして探索を行います。

浅い探索の結果を有効に活用するため、浅い探索の結果として訪問したノードのminimax値をハッシュテーブル(C++だとunordered_map)に入れておきます。深さDの探索では、ハッシュテーブルを参照して、前回の探索で良かった手から順番に探索をしていきます。

前回枝刈りをせずに探索された手は、枝刈りをされていない時点で良い手である可能性が高いので、前回の探索結果にボーナス点を加えておきます。前回枝刈りされてしまった手は評価関数にかけて順番を決めます。注意点ですが、ここで評価関数を使うのはあくまでもmove orderingのためであって、直接探索に関係するわけではありません。ですので評価関数ではなくて、何か別の速く計算できる指標を使うことも可能です。

先読みの時間に制限がある場合も、時間いっぱい深さを増やしながら読んでみて、最後に読めた深さでの手を出力することができ、便利です。

さらに、このハッシュテーブルを使うことで、「違う手筋だが同じ盤面になる状態」に遭遇した時に無駄な探索をせずに済むことがあります。この使い方をするハッシュテーブルを「置換表」と言います。

浅い探索を使ったnegaalpha法の高速化、および置換表を使って同じ盤面に出くわしたときの対策を施したサンプルコードは以下です。

// move orderingと置換表つきnegaalpha法
int nega_alpha_transpose(board b, int depth, bool passed, int alpha, int beta) {
    ++visited_nodes;
    // 葉ノードでは評価関数を実行する
    if (depth == 0)
        return evaluate(b);
    // 同じ局面に遭遇したらハッシュテーブルの値を返す
    if (transpose_table.find(b) != transpose_table.end())
        return transpose_table[b];
    // 葉ノードでなければ子ノードを列挙
    int coord, g, max_score = -inf, canput = 0;
    vector<board> child_nodes;
    for (coord = 0; coord < hw2; ++coord) {
        if (b.legal(coord)) {
            child_nodes.push_back(b.move(coord));
            child_nodes[canput].value = calc_move_ordering_value(child_nodes[canput]);
            ++canput;
        }
    }
    // パスの処理 手番を交代して同じ深さで再帰する
    if (canput == 0) {
        // 2回連続パスなら評価関数を実行
        if (passed)
            return evaluate(b);
        b.player = 1 - b.player;
        return -nega_alpha_transpose(b, depth, true, -beta, -alpha);
    }
    // move ordering実行
    if (canput >= 2)
        sort(child_nodes.begin(), child_nodes.end());
    for (const board& nb: child_nodes) {
        g = -nega_alpha_transpose(nb, depth - 1, false, -beta, -alpha);
        if (g >= beta) // 興味の範囲よりもminimax値が上のときは枝刈り
            return g;
        alpha = max(alpha, g);
        max_score = max(max_score, g);
    }
    // 置換表に登録
    transpose_table[b] = max_score;
    return max_score;
}

少しコードが長くなってきましたね。

置換表であるtranspose_tableには必ずminimax値を入れるようにしていますが、次回の記事ではもう少し凝った置換表の使い方をします。あくまでもこの使い方は暫定的なものだと思ってください。

実行してみる

まずは置換表のない普通のalphabeta法から実行してみましょう。

$ g++ -O3 ai3_negaalpha.cpp -o ai.out  
$ python3 main.py

実行すると、コンソールに色々な情報が表示されますが、このような行に注目してください。

searched nodes 164266

このような表示があると思います。数字は探索時に訪問したノードの数です。

次に、置換表つきの方を実行してみましょう。

$ g++ -O3 ai4_negaalpha_fast.cpp -o ai.out
$ python3 main.py

実行してみると、同じように探索時の情報が表示されます。

searched depth 5 policy 42 visited nodes 2516
searched depth 6 policy 42 visited nodes 7643
searched depth 7 policy 42 visited nodes 37759
searched depth 8 policy 42 visited nodes 94209

デフォルトでは置換表なしの方は7手読み、置換表ありの方は8手読みになっています。また、上で例として出した出力はどちらも同じ盤面における探索の情報です。

置換表なしでは、訪問ノード数が7手読みで16万程度でしたが、置換表とmove orderingありでは7手読みのところ(depth 7の行)を見ると4万程度まで少なくなっています。

上の解説はきちんとした評価ではありませんが、一般的に置換表とmove orderingの効果は凄まじいです。

まとめ

今回はminimax法を効率化したalphabeta法を解説しました。

alphabeta法では、その特性上move orderingがとても重要で、これによってどれほど枝刈りが起きるかが決定されます。

今回の記事は枝刈りの仕組みとmove orderingが難しかったと思います。わからない点はお気軽に質問をください。記事をわかりやすく洗練したいです。

次回予告

次回は置換表とmove orderingつきalphabeta法をさらに発展させた、negascout法を紹介します。negascout法では今回よりもアップグレードされた置換表が登場して頭がこんがらがりがちになるので、丁寧に解説します。

スキと投げ銭で喜びます

noteではログインなしでスキできます！役に立ったぞ、面白かったぞ、という方はぜひハートマークをポチッと押してください！

この記事は全編無料ですが、投げ銭してくれたら私が喜びます。喜ぶだけです。何も見返りはありません。「役に立ったし投げ銭してやっても良いぞ」という方はポチっとしてくださると嬉しいです。

ここから先は

0字

¥ 100

ログイン

この記事が気に入ったらサポートをしてみませんか？