【CodinGameオセロ】GreedyなAIと自己対局

前回は、盤面の情報を格納し、合法手を列挙してくれる盤面クラスを作りました。まずは、機械学習なしに簡単に作れるAIを作っていきます。これを作る理由は、機械学習で作ったAIを評価する際の対戦相手とするためです。機械学習を用いたAIは、学習データを用意し、学習を行い、学習したモデルを用いた局面評価を行うという大量の実装を要するため、バグが混入しやすいです。一連のステップが正しく動作したことを確認できる、挙動がはっきりした相手を先に作っておくのが賢明です。

今回の時点のコードは以下のものになります。

https://github.com/select766/codingame-othello/tree/83c4e648aaf34041a4eb3096baf9337cf02be1a7

プレイヤークラスの抽象化

これから作るいくつかのAIは、適当な組み合わせで対戦させてどちらがどの程度強いのか評価できるようにしておきたいです。そのためには、インターフェースを統一することが必要です。そこで、以下のように抽象クラスを定義します。

// AIのインターフェース
class SearchBase
{
public:
    Board board; // searchを呼び出す前に、手を考えたい局面をここにセットする
    virtual int search() = 0; // 思考して手を返す
    virtual string name() = 0; // AIの名前を返す
};

そして、main関数で、以下のようにSearchBaseクラスへのポインタを用いて異なるAIを対局させる実装を行います。このような実装を行うことで、AIのアルゴリズムが変わっても、初期化部分を差し替えるだけで自己対局が可能になります。マクロ定義 MODE_RANDOM_MATCH により他の機能とmain関数を分離しています。

#if defined(MODE_INTERACTIVE)
// 手動で局面を進める機能のmain関数
#elif defined(MODE_RANDOM_MATCH)
int main()
{
    const int n_games = 1000;
    SearchBase *ais[] = {new SearchRandom(), new SearchGreedy()}; // AIの具象クラスを生成
    int player_win_count[N_PLAYER] = {0};
    int color_win_count[N_PLAYER] = {0};
    int draw_count = 0;

    // 2つのAIを対局させる
    for (int i = 0; i < n_games; i++)
    {
        cout << "game " << i << endl;
        Board board;
        board.set_hirate();

        int black_player = i % 2;

        while (!board.is_end())
        {
            int turn_player = board.turn() ^ black_player;
            SearchBase *ai = ais[turn_player];
            ai->board.set(board);
            int move = ai->search();

            UndoInfo undo_info;
            board.do_move(move, undo_info);
        }

        int diff = board.count_stone_diff();
        if (diff < 0)
        {
            // white wins
            player_win_count[1 - black_player]++;
            color_win_count[WHITE]++;
        }
        else if (diff > 0)
        {
            // black wins
            player_win_count[black_player]++;
            color_win_count[BLACK]++;
        }
        else
        {
            draw_count++;
        }
    }

    cout << "Summary" << endl;
    cout << ais[0]->name() << " - " << ais[1]->name() << " : " << player_win_count[0] << " - " << draw_count << " - " << player_win_count[1] << endl;
    cout << "black - white : " << color_win_count[0] << " - " << color_win_count[1] << endl;

    return 0;
}
#else
// CodinGame用main関数
#endif

ランダムプレイヤー

もっとも単純なAIです。このAIに確実に勝てるようにすることが当面の目標になります。

// ベースラインとなるランダムAI
class SearchRandom : public SearchBase
{
    std::random_device seed_gen;
    mt19937 engine;

public:
    SearchRandom() : seed_gen(), engine(seed_gen())
    {
    }

    string name()
    {
        return "Random";
    }

    int search()
    {
        // 合法手を列挙
        vector<int> move_list;
        board.legal_moves(move_list);
        if (move_list.empty())
        {
            return MOVE_PASS;
        }
        else
        {
            // 合法手から、乱数で1つ選ぶ
            uniform_int_distribution<> dist(0, move_list.size() - 1);
            int move_idx = dist(engine);
            return move_list[move_idx];
        }
    }
};

Greedyプレイヤー

ランダムではさすがに思考しているとは言い難いので、何らかの形で自分に有利な手を打つ最低限のAIを作ります。オセロであれば、石を打った時に最も多くの石をひっくりかえせるような打ち方をするというアルゴリズムが考えられます。目の前の利益を最大化する、貪欲(Greedy)なAIです。これも、前回作った盤面クラスがあれば容易に実装できます。盤面クラスは、仮に決めた手で一手進めたあと、前に戻して別の手を試す、という機能を持つことが思考アルゴリズムを実装するために必要です。

// 最も多くの石をひっくりかえすAI
class SearchGreedy : public SearchBase
{
public:
    SearchGreedy()
    {
    }

    string name()
    {
        return "Greedy";
    }

    int search()
    {
        vector<int> move_list;
        // 合法手を列挙
        board.legal_moves(move_list);
        if (move_list.empty())
        {
            return MOVE_PASS;
        }
        else
        {
            int bestmove = 0;
            int bestcount = -1;
            int player = board.turn();
            for (auto move : move_list)
            {
                UndoInfo undo_info;
                // 仮に決めた手で一手進める
                board.do_move(move, undo_info);
                // 自分の石の数を数える
                int count = board.count_stone(player);
                // 自分の石の数が最大となるような手を判定する
                if (count > bestcount)
                {
                    bestmove = move;
                    bestcount = count;
                }
                // 仮に進めた局面を戻す
                board.undo_move(undo_info);
            }

            return bestmove;
        }
    }
};

このアルゴリズムは、どの程度強いのでしょうか？自己対戦プログラムが実装されているので評価することが可能です。評価結果は以下のようになります。

Random - Greedy : 334 - 33 - 633
black - white : 491 - 476

Random - Greedy : 334 - 33 - 633は、ランダムが334勝、引き分けが33回、Greedyが633勝だったことを示します。また、black - white : 491 - 476は、黒（先手）が491勝、白（後手）が476勝ということを示します。先手と後手は対局ごとに毎回入れ替えます。Greedyは、ランダムよりも若干強いということが確認できました。ごく単純ではありますが、思考能力を持ったAIが作れたといえます。

AIが実装できたので、CodinGameに投入してみます。CodinGameのオセロ部門では、プレイヤーがWood 1 LeagueかWood 2 Leagueかどちらかに所属します。参加したばかりのプレイヤーはWood 2 Leagueに所属し、そこにいるBOSSより強い戦績を残すとWood 1 Leagueに昇格できます。投稿方法の確認のためランダムAIを投入した結果、Wood 2 League全体で321名の中で、235位になりました。これが基準の順位となります。そしてGreedy AIを投入した結果、144位を獲得できました。手元のパソコンでランダムより強いと判定したAIが、実際のサーバ上でも機能することを確認できました。明確な正解・不正解を判断しづらいゲームAIにおいて、対外的な順位が上がるのはモチベーションを維持しやすいため、小刻みに投稿していくことが良いと感じました。