オセロで試すMiniMax法とかAlphaBeta法とか

こんにちは。株式会社オプティマインドの伊豆原と申します。最適化チームに所属しており、また社内部活として競プロ部にも所属しています。

当社の競プロ部の活動の一環として、オセロを題材にMiniMax戦略やAlphaBeta法、ついでにNegaScout法について比較実験できればと思います。アルゴリズム詳細についてはWikipediaに丸投げしてますので悪しからず。

環境について

ローカルで動かす環境はMacBookProでプロセッサは2GHz クアッドコアIntel Core i5。メモリは16GBです。C++のコンパイラおよびコンパイルオプションはg++ -O2 ./main.cpp --std=c++20です。

オセロのプログラムは凝り始めると面倒なので簡単に実装します。詳細は最後にオマケとして書きますが、盤面の状態を64bit整数2つで管理し、先攻後攻を整数turn=(0: 先攻、1: 後攻)で管理します。次の関数nextStateOfは与えられた盤面とターンから合法手を打った結果のvectorを返します。

namespace othello{
    using btype = uint64_t;
    using Board = std::array<btype, 2>;
    std::vector<Board> nextStateOf(const Board& bw, int turn){
        ...
    }
}

プレイヤーは以下のクラスを継承するとします。関数moveは盤面とターン(0 or 1)が与えられたときに次の一手を打った結果を返す関数で、合法手がなければfalseと元の盤面をそのまま返します。

using Result = std::pair<bool, Board>;
class Player{
public:
    virtual Result move(const Board& bw, int turn) = 0;
};

RandomPlayer

まず強さを測るための基準とする乱数プレイヤーを作成します。このプレイヤーは合法手の中からランダムに1つ選んで打ちます。

std::random_device rd{};
std::mt19937 mt(rd());

class RandomPlayer : public othello::Player {
    othello::Result move(const othello::Board& bw, int turn) override {
        const auto& states = othello::nextStatesOf(bw, turn);
        if (states.empty()) return { false, bw };
        const auto& nbw = states[mt() % states.size()];
        return { true, nbw };
    }
};

特に特筆することはないのですが、とりあえずRandomPlayer同士で先攻後攻を交互にして1000回戦わせるとローカル環境で100ms程度で終わりました。戦歴は以下です(win/draw/lose)。同じプレイヤーなので当然ですが、だいたい互角ですね。

	vs RandomPlayer
RandomPlayer	481/46/473

MiniMaxPlayer

次にミニマックス戦略を試してみます。ミニマックス戦略については以下のサイトを参照します。

盤面の評価関数としては簡単のため、単純に(自分のマスの数-相手のマスの数)とします。角の評価値を高くする、などするとより賢くなると思います。

class MiniMaxPlayer : public othello::Player {
    int search_depth;
    int my_turn = 0;
    int coeff = 0;
    bool find_valid = false;
    using ScoreBoard = std::tuple<int, othello::Board>;

    ScoreBoard _move(const othello::Board& bw, int turn, int depth) {
        auto [nb, nw] = othello::count(bw);
        int score = (nb - nw) * coeff;
        if (depth == 0) {
            return { score, bw };
        }
        auto nbws = othello::nextStatesOf(bw, turn);
        if (nbws.empty()) {
            return { score, bw };
        }
        std::shuffle(nbws.begin(), nbws.end(), mt); // 乱択性のため

        find_valid = true;

        othello::Board res;
        if (turn == my_turn) {
            int max_score = -100;
            for (const auto& nbw : nbws) {
                auto [score, _] = _move(nbw, othello::next(turn), depth - 1);
                if (score > max_score) {
                    max_score = score;
                    res = nbw;
                }
            }
            return { max_score, res };
        } else {
            int min_score = 100;
            for (const auto& nbw : nbws) {
                auto [score, _] = _move(nbw, othello::next(turn), depth - 1);
                if (score < min_score) {
                    min_score = score;
                    res = nbw;
                }
            }
            return { min_score, res };
        }
    }

public:
    MiniMaxPlayer(int depth = 1) :search_depth(depth) {};

    othello::Result move(const othello::Board& bw, int turn) override {
        my_turn = turn;
        coeff = (turn == 0) ? 1 : -1; // スコアに掛ける係数
        find_valid = false;

        auto [score, result] = _move(bw, turn, search_depth);
        return { find_valid, result };
    }
};

先ほどと同様に1000回先攻後攻を交互に戦わせた結果が以下になります(括弧の中の数値は探索の深さです)。MiniMaxPlayerがRandomPlayerよりも強く、またMiniMaxPlayer同士でも探索が深いほうが強いことがわかります(しかし結構、RandomPlayerが強いですね)。

	vs RandomPlayer	vs MiniMaxPlayer(2)	vs MiniMaxPlayer(4)
RandomPlayer	481/46/473	238/23/739	154/14/832
MiniMaxPlayer(2)	739/23/238	-	255/21/724
MiniMaxPlayer(4)	832/14/154	724/21/255	-

AlphaBetaPlayer

先ほどのMiniMax法ですが、MiniMaxPlayer(4) vs RandomPlayerにおいて1000戦で27595msほど掛かっています。MiniMax法では探索木を指定された深さですべて見るため時間が掛かりますので、これを枝刈りするAlphaBeta法を使ってみます。詳細については以下を参照します。

class AlphaBetaPlayer : public othello::Player {
    int search_depth;
    int my_turn = 0;
    int coeff = 0;
    bool find_valid = false;
    using ScoreBoard = std::tuple<int, othello::Board>;

    ScoreBoard _move(const othello::Board& bw, int turn, int depth, int alpha, int beta) {
        auto [nb, nw] = othello::count(bw);
        int score = (nb - nw) * coeff;
        if (depth == 0) {
            return { score, bw };
        }
        auto nbws = othello::nextStatesOf(bw, turn);
        if (nbws.empty()) {
            return { score, bw };
        }
        find_valid = true;

        std::shuffle(nbws.begin(), nbws.end(), mt); // 乱択性のため

        othello::Board res;
        if (turn == my_turn) {
            for (const auto& nbw : nbws) {
                auto [score, _] = _move(nbw, othello::next(turn), depth - 1, alpha, beta);
                if (alpha < score) {
                    alpha = score;
                    res = nbw;
                }
                if (alpha >= beta) break;
            }
            return { alpha, res };
        } else {
            for (const auto& nbw : nbws) {
                auto [score, _] = _move(nbw, othello::next(turn), depth - 1, alpha, beta);
                beta = std::min(beta, score);
                if (score < beta) {
                    beta = score;
                    res = nbw;
                }
                if (alpha >= beta) break;
            }
            return { beta, res };
        }
    }

public:
    AlphaBetaPlayer(int depth = 1) :search_depth(depth) {};

    othello::Result move(const othello::Board& bw, int turn) override {
        my_turn = turn;
        coeff = (turn == 0) ? 1 : -1; // スコアに掛ける係数
        find_valid = false;

        auto [score, result] = _move(bw, turn, search_depth, -100, 100);
        return { find_valid, result };
    }
};

以下はMiniMaxPlayerとの1000戦の結果になります。AlphaBeta法は枝刈りしているだけなので性能は変わらないはずで、実際勝敗数に関してもほぼ同等であることが見れます。

	MiniMaxPlayer(2)	MiniMaxPlayer(4)
AlphaBetaPlayer(2)	506/26/468	-
AlphaBetaPlayer(4)	-	493/18/489

以下はRandomPlayerとの1000戦に掛かった時間になります。AlphaBeta法によって探索が高速化していることが分かります。

	depth=2	depth=4
MiniMaxPlayer	587ms	27595ms
AlphaBetaPlayer	476ms	7654ms

では実際にどのくらい枝刈りされたかを見てみます。以下は深さ6で設定したMiniMaxPlayerとAlphaBetaPlayerでそれぞれRandomPlayerと10戦し、各深さのノードに何回訪れたかを記載したものです。深くなるほど枝切りの効果が顕著になっていることが分かります。

	MiniMax	AlphaBeta
0	316	285
1	1883	1718
2	15489	5879
3	126160	28197
4	1261161	110908
5	11599165	482723
6	127908049	2049304

NegaScoutPlayer

さて、上で紹介しましたAlphaBeta法ですが実はいろいろと改良版があるみたいで、最後にその中の一つであるNegaScoutというものも試して見たいと思います。構造や実装の詳細については以下を参照します。

実装中、次の一手に関して"良さそうな"手を選ぶという処理をする必要がありますが、今回は簡単に一番評価が良い(=(自分のマスの数-相手のマスの数)が一番大きい)ものを選ぶとします。

(ただ下の実装、微妙に前述のAlphaBetaより弱いんですよね……どこかに不具合がある気がしてます)。

class NegaScoutPlayer : public othello::Player {
    int search_depth;
    int my_turn = 0;
    int coeff = 0;
    bool find_valid = false;
    using ScoreBoard = std::tuple<int, othello::Board>;

    ScoreBoard _move(const othello::Board& bw, int turn, int depth, int alpha, int beta) {
        auto [nb, nw] = othello::count(bw);
        int score = (nb - nw) * coeff;
        if (depth == 0) return { score, bw };

        auto nbws = othello::nextStatesOf(bw, turn);
        if (nbws.empty()) return { score, bw };

        find_valid = true;

        std::shuffle(nbws.begin(), nbws.end(), mt); // 乱択性のため

        // 一番評価の良い盤面を選択
        int mi;
        int tscore = -100;
        for (int i = 0; i < nbws.size(); i++) {
            const auto& [nb, nw] = othello::count(nbws[i]);
            int score = (nb - nw) * coeff;
            if (tscore < score) {
                tscore = score;
                mi = i;
            }
        }

        auto res = nbws[mi];
        auto [v, _] = _move(res, othello::next(turn), depth - 1, -beta, -alpha);
        v = -v;
        int max_score = v;
        if (beta <= v) return { v, res };
        if (alpha < v) alpha = v;

        for (int i = 0; i < nbws.size(); i++) {
            if (i == mi) continue;
            const auto& nbw = nbws[i];
            auto [v, _] = _move(nbw, othello::next(turn), depth - 1, -alpha - 1, -alpha);
            v = -v;
            if (beta <= v) return { v, res };
            if (alpha < v) {
                alpha = v;
                const auto& [nv, _] = _move(nbw, othello::next(turn), depth - 1, -beta, -alpha);
                v = -nv;
                if (beta <= v) return { v, res };
                if (alpha < v) alpha = v;
            }
            if (max_score < v) {
                max_score = v;
                res = nbw;
            }
        }
        return { max_score, res };
    }

public:
    NegaScoutPlayer(int depth = 1) :search_depth(depth) {};

    othello::Result move(const othello::Board& bw, int turn) override {
        my_turn = turn;
        coeff = (turn == 0) ? 1 : -1; // スコアに掛ける係数
        find_valid = false;

        auto [score, result] = _move(bw, turn, search_depth, -100, 100);
        return { find_valid, result };
    }
};

以下はAlphaBeta法との速度比較と各深さでのノードの訪問回数比較になります。NegaScoutのほうがAlphaBetaより高速になっていることが分かります。

• 速度比較

	depth=2	depth=4	depth=6
MiniMaxPlayer	587ms	27595ms	-
AlphaBetaPlayer	476ms	7654ms	139318ms
NegaScoutPlayer	494ms	6389ms	83569ms

• 各深さのノードの訪問回数比較

	MiniMax	AlphaBeta	NegaScout
0	316	285	313
1	1883	1718	1798
2	15489	5879	7103
3	126160	28197	23158
4	1261161	110908	98219
5	11599165	482723	249200
6	127908049	2049304	1216638

結び

以上、交互着手の二人ゲームに関して有名な手法をいくつか試してみました。ちなみに試しに戦ってみましたところ、6手先ぐらいまで読まれると私では勝てませんでした。短いソースコードで結構強いプレイヤーが作れますね。

ここまで読んで頂きありがとうございました！

オマケ

使用したオセロのソースコードです。エイヤで書いたので特に高速というわけではありません。

#include<tuple>
#include<iostream>
#include<map>
#include<vector>
#include<random>
#include<chrono>

namespace othello {
    static const int GAME_SIZE = 8;
    using btype = uint64_t;
    using Board = std::array<btype, 2>;
    using Result = std::pair<bool, Board>;
    static std::array<btype, GAME_SIZE* GAME_SIZE> buf;
    static Board null = Board{ 0,0 };

    btype getBit(int x, int y) {
        return btype(1) << (GAME_SIZE * x + y);
    }

    int next(int turn) {
        return (turn + 1) & 1;
    }

    std::tuple<int, int> count(const Board& bw) {
        int nb = std::popcount(bw[0]);
        int nw = std::popcount(bw[1]);
        return { nb,nw };
    }

    void printBoard(const Board& bw) {
        for (int x = 0; x < GAME_SIZE; x++) {
            for (int y = 0; y < GAME_SIZE; y++) {
                btype pos = getBit(x, y);
                if (bw[0] & pos) {
                    std::cout << 'B';
                } else if (bw[1] & pos) {
                    std::cout << 'W';
                } else {
                    std::cout << '-';
                }
            }
            std::cout << std::endl;
        }
        auto [nb, nw] = count(bw);
        std::cout << "b:" << nb << " w:" << nw << std::endl;
    }

    Board generate() {
        int size = GAME_SIZE;
        int half = size / 2;
        btype b = 0;
        btype w = 0;
        b |= getBit(half - 1, half);
        b |= getBit(half, half - 1);
        w |= getBit(half - 1, half - 1);
        w |= getBit(half, half);
        return { b,w };
    }

    Result move(const Board& bw, int turn, int x, int y) {
        btype pos = getBit(x, y);
        if (bw[0] & pos || bw[1] & pos) return { false, bw };
        int nturn = othello::next(turn);
        int cnt = 0;
        for (int dx = -1; dx < 2; dx++) {
            for (int dy = -1; dy < 2; dy++) {
                int temp = 0;
                int nx = x + dx;
                int ny = y + dy;
                while (0 <= nx && nx < GAME_SIZE && 0 <= ny && ny < GAME_SIZE) {
                    btype np = getBit(nx, ny);
                    if (bw[nturn] & np) {
                        buf[cnt + temp] = np;
                        temp += 1;
                    } else if (bw[turn] & np) {
                        cnt += temp;
                        break;
                    } else {
                        break;
                    }
                    nx += dx;
                    ny += dy;
                }
            }
        }
        if (cnt == 0) return { false, bw };
        Board nbw = bw;
        nbw[turn] |= pos;
        for (int i = 0; i < cnt; i++) {
            nbw[turn] |= buf[i];
            nbw[nturn] ^= buf[i];
        }
        return { true, nbw };
    }

    std::vector<Board> nextStatesOf(const Board& bw, int turn) {
        std::vector<Board> res;
        for (int x = 0; x < GAME_SIZE; x++) {
            for (int y = 0; y < GAME_SIZE; y++) {
                auto [ok, nbw] = move(bw, turn, x, y);
                if (ok) {
                    res.push_back(nbw);
                }
            }
        }
        return res;
    }
};