【CodinGameオセロ】アルファベータ法による探索

前回は、局面を合法手で1手進めたときに、最も多くの石をひっくりかえせるような手を選ぶというGreedyなAIを実装しました。しかしランダムプレイヤーに対して勝率63%程度となり、あまり強いとは言えません。機械学習を導入したいのですが、最初は強化学習ではなく教師あり学習を行いたいため、挙動がわかっていて、なおかつランダムよりは強い何らかの教師データを作成したいです。なぜならAlphaZero式の強化学習の場合は初めにランダムなパラメータのモデルから学習を開始するため、強くならなかった場合に探索部(MCTS)が悪いのかモデルが悪いのかが判断できないためです。一度教師あり学習によってモデルの学習を行い、そのモデルを用いてMCTS探索を行うAIを開発することで段階を踏んで開発を進めることができます。

上記の理由により、機械学習無しでもう少しだけ強いAIの開発を進めます。GreedyなAIは、深さ1の探索を行う手法と言えます。今回は、アルファベータ法により2手以上の深さで探索を行います。評価関数の学習は行わない方針なので、最も自明な評価方法として「自分の石の数-相手の石の数」を用いることにしました。あまり賢いとは言えませんが、勝敗の判定に使うコードから直ちに算出できる値であるためオセロ固有の実装は最小限に抑えられます。

今回のコードのバージョンは以下の通りです。

https://github.com/select766/codingame-othello/tree/95f2d91204495b41fff44253653e90fbe67e1256

アルファベータ法の実装

コア部分は教科書通りです。挙動が毎回同じになってしまい強さの評価が困難なため、評価値に乱数を加えることにしました。もとの評価値は石の数の差ですが、256倍してから0~255の乱数を加算しています。つまり、石の数の差が同じ場合に、どちらの局面を優先するかに違いが生じるようになっています。また、search関数の定義を変更し、文字列msgを返す機能を追加しています。これはCodinGame上で表示する追加情報です。CodinGameで手を出力する際に、a1 MSG some_infoのように手の後ろにMSGという記号を付与し、その後ろに任意の文字列を出力可能です。これを用いることで、探索にかかった時間などを表示しパラメータ調整に役立てることができます。CodinGameでは1手の思考時間は150ms以下と決められている（オーバーすると負け）ため、探索の深さを調整することに使いました。

// 固定深さでアルファベータ法で探索するAI
class SearchAlphaBetaConstantDepth : public SearchBase
{
    std::random_device seed_gen;
    mt19937 engine;
    uniform_int_distribution<> dist;

public:
    SearchAlphaBetaConstantDepth() : seed_gen(), engine(seed_gen()), dist(0, 255)
    {
    }

    string name()
    {
        return "AlphaBetaConstantDepth";
    }

    int search(string &msg)
    {
        vector<int> move_list;
        board.legal_moves(move_list);
        if (move_list.empty())
        {
            return MOVE_PASS;
        }
        else
        {
            auto search_start_time = chrono::system_clock::now();
            int bestmove;
            int score = alphabeta(5, -100000, 100000, &bestmove) / 256; // 固定深さ5で探索
            auto search_end_time = chrono::system_clock::now();
            auto search_duration = search_end_time - search_start_time;
            stringstream ss;
            ss << "score " << score << " time " << chrono::duration_cast<chrono::milliseconds>(search_duration).count() << " ms";
            msg = ss.str();

            return bestmove;
        }
    }

    int alphabeta(int depth, int alpha, int beta, int *bestmove)
    {
        if (board.is_end() || depth == 0)
        {
            // 黒から見たスコアなので、手番から見たスコアにする
            // 乱数要素がないと強さ測定が難しいので入れている
            int score = board.count_stone_diff() * 256 + dist(engine);
            if (board.turn() != BLACK) {
                score = -score;
            }
            return score;
        }

        vector<int> move_list;
        board.legal_moves(move_list);
        if (move_list.empty())
        {
            move_list.push_back(MOVE_PASS);
        }
        for (auto move : move_list) {
            UndoInfo undo_info;
            board.do_move(move, undo_info);
            int child_score = -alphabeta(depth - 1, -beta, -alpha, nullptr);
            board.undo_move(undo_info);
            if (child_score > alpha) {
                if (bestmove != nullptr) {
                    *bestmove = move;
                }
                alpha = child_score;
            }
            if (alpha >= beta) {
                return alpha;
            }
        }
        return alpha;
    }
};

実行結果

ローカルでの自己対戦の結果は以下のようになりました。

Greedy - AlphaBetaConstantDepth : 9 - 0 - 91 
black - white : 49 - 51

Random - AlphaBetaConstantDepth : 16 - 0 - 84 
black - white : 58 - 42

Greedy相手には勝率91%ですが、Random相手には84%となり強さの関係が逆転しています。評価関数はGreedyと同じでより深く読めるようになったので、弱点を突く結果になっている可能性があります。いずれにせよ、従来より強くなったことは間違いありません。

このAIをCodinGameに投稿したところ、GreedyでのWood 2 League 142位から、69位に改善しました。なお、探索の深さを7手に増やすと時間切れで負けました。合法手生成の実装がかなり遅いことが課題なので、次回はビットボードを用いたアルゴリズムを実装して改善します。