これからCodinGameで動くオセロAIを作っていきます。まずは、環境構築と盤面クラスの実装です。盤面クラスは、オセロの盤面をプログラム内で表現し、合法手（その時点で石を打てる場所）を列挙したり、選んだ手で局面を次に進めたりする機能を持つもので、ゲームAI開発の初手として必須の要素になります。
この記事の時点のコードは以下のものです。より新しいバージョンでは、ビルドの仕組みなどが変わりますのでご注意ください。
環境構築
開発言語ですが、速度が重要なのでC++を用います。一方で機械学習に関する部分はPythonが便利ですので、併用します。なお、後に出てくる機械学習ではフレームワークにTensorflowを用います。 開発環境はWindows10+WSL2 (Linux仮想環境)+Ubuntu 22.04+VSCodeとしました。
CodinGameへのプログラムの提出は、C++のソースファイルを1つだけ提出する形式です。そのため、まずはすべてのコードを1つのファイルに記述していきます。のちに、分割して作成したソースを1ファイルに統合する手段を用意します。
VSCodeでは、現在開いているC++ソースファイルをショートカットキー一つ(Ctrl+Shift+B)でビルドすることが可能です。これは、ワークスペースに以下のようなファイルを設置することで設定できます。
.vscode/c_cpp_properties.json
{
"configurations": [
{
"name": "WSL",
"includePath": [
"${workspaceFolder}/**"
],
"defines": [
"MODE_INTERACTIVE"
],
"compilerPath": "/usr/bin/g++",
"cStandard": "c17",
"cppStandard": "gnu++17",
"intelliSenseMode": "linux-gcc-x64"
}
],
"version": 4
}
.vscode/tasks.json
{
"version": "2.0.0",
"tasks": [
{
"type": "cppbuild",
"label": "C/C++: g++ build active file",
"command": "/usr/bin/g++",
"args": [
"-fdiagnostics-color=always",
"-g",
"${file}",
"-o",
"${fileDirname}/${fileBasenameNoExtension}",
"-DMODE_INTERACTIVE"
],
"options": {
"cwd": "${fileDirname}"
},
"problemMatcher": [
"$gcc"
],
"group": {
"kind": "build",
"isDefault": true
},
"detail": "compiler: /usr/bin/g++"
}
]
}
なお、MODE_INTERACTIVEの記述はマクロ定義で、状況により変える必要があります。.vscode/c_cpp_properties.jsonの中での定義はIntelliSense（入力補完）に与える定義、.vscode/tasks.jsonの中での定義はビルド時に使われる定義であり、使われる場面が異なります。
盤面クラスの実装
盤面クラスは、盤面の状態（どの色の石がどこに置かれているか）を保持し、その盤面における合法手を列挙する、石を打って盤面を次の状態に進める、CodinGameから与えられた盤面を表す文字列を解釈するなどの機能を持ちます。オセロに関するコード資産のない状態から開発を始めるため、いきなりCodinGameに投稿するのではなく、様々な局面で合法手が正しく計算できているかなど、目視で確認することから始めます。そのため、手を手入力して盤面の状態が正しく変化するかどうか検証するためのプログラムを実装し、ローカルで動作させます。ところで、実はCodinGameでは合法手一覧を入力として与えてくれるため、合法手生成は行わなくてもランダムプレイヤー（合法手からランダムに1手選ぶAI）の実装は可能です。しかし合法手を打った後の局面を計算できなければ探索ができないので、盤面クラスを実装します。
作ったソースファイルが以下になります。
盤面クラスは、以下のようなインターフェースとしました。
#define BOARD_SIZE 8 // 一辺の長さ #define BOARD_AREA 64 // マスの数 #define MOVE_PASS BOARD_AREA // パスを表す番号 #define N_PLAYER 2 // プレイヤーの数 #define BLACK 0 // 黒（先手番） #define WHITE 1 // 白（後手番） class Board { int board[N_PLAYER][BOARD_AREA]; // 手番、各マスの石の有無 int total_stones; // 置かれている石の総数 int _turn; // BLACK / WHITE bool last_pass[N_PLAYER]; public: Board(){set_hirate();} void set(const Board& other) { /* 省略 */ } int turn() const {return _turn;} void set_hirate() { /* 初期局面（石が4つ置かれた状態）をセット */ } void set_position_codingame(const vector<string> &lines, int turn) { /* CodinGameの書式で与えられた局面をセット */ } void do_move(int move, UndoInfo &undo_info) { /* 与えた手で盤面を進める */ } void undo_move(const UndoInfo &undo_info) { /* undo_infoの内容をセット */ } void legal_moves(vector<int> &move_list) const { /* 合法手を列挙してmove_listに挿入 */ } bool can_move(int move) const { /* 与えた手が合法かを判定する */ } bool is_end() const { /* ゲームが終局しているか判定する */ } int count_stone(int color) const { /* 与えた色の石の数を数える */ } int count_stone_diff() const { /* 石の数の差（黒の数-白の数）を数える */ } string pretty_print() const { /* 盤面を見やすい文字列で出力 /* } };
これだけのインターフェースがあれば、ランダムプレイヤーを作成すること、ゲームの終局時に勝敗を判定することが可能です。プレイヤーは黒（先手）、白（後手）の数値定数で表現します。盤上の座標は、左上がa1で、右に進むとb1, c1, ...と記述します。下に進むとa2, a3, ...となります。64マスの座標を0～63の整数で表します。手（石を置く場所）は、その座標の数値を用います。また、パスは64 (=BOARD_AREA)で表現します。盤上の石は、色と座標をインデックスとした2次元配列を用いて、石がある=1、石がない=0を代入して表現します。明らかにメモリの利用効率が悪いですが、正常に動く比較対象がない開発初期はこのような分かりやすい実装にしたほうがバグが抑えられ、実装時間の短縮になります。total_stonesは終局の判定に用います。64個の石が置かれていれば終局であると判定できるためです。last_passは、各プレイヤーの直前の手がパスだったかどうかを示します。両方のプレイヤーが連続してパスをすると、盤上に空いているマスがあっても終局になるため、それを判定することに用います。
ソースコード全体を掲載するのは長いので、合法手生成に関する核心部分だけ載せます。以下の関数は、手を与えてその座標に石が置けるかどうかを判定します。オセロのルールに忠実に判定するだけです。
#define N_DIR 8 const int dirsx[N_DIR] = {-1, 0, 1, -1, 1, -1, 0, 1}; const int dirsy[N_DIR] = {-1, -1, -1, 0, 0, 1, 1, 1}; bool can_move(int move) const { // すでに石がある場合は置けない if (board[0][move] != 0 || board[1][move] != 0) { return false; } int opp = 1 - _turn; // 相手番 // マスがただ空いているだけではなく、1個以上の石をひっくりかえせる必要がある for (int i = 0; i < N_DIR; i++) // 石を置く場所を中心とした8方向 { int dirx = dirsx[i]; int diry = dirsy[i]; int posx = move % BOARD_SIZE; int posy = move / BOARD_SIZE; int opp_len = 0; int flip_len = 0; // 相手の石が連続する数を計算。最後に自分の石があれば、相手の石の数だけひっくりかえせる while (true) { posx += dirx; posy += diry; if (posx < 0 || posx >= BOARD_SIZE || posy < 0 || posy >= BOARD_SIZE) { // 盤外に出たのでダメ break; } int p = posx + posy * BOARD_SIZE; if (board[opp][p]) { // 相手の石がある opp_len++; } else if (board[_turn][p]) { // 自分の石がある。ここまでに存在した相手の石の数だけひっくりかえせる flip_len = opp_len; break; } else { break; } } if (flip_len > 0) { return true; } } return false; }
can_moveがあれば、すべての座標に対してこの関数を実行することで合法手を列挙することができます。また、類似の実装により石を置いた際に相手の石をひっくりかえす処理も実装できます。
最後に、盤面クラスを動作させるmain関数を記述します。局面と合法手一覧が表示されるので、キーボードで手を入力すると次の局面に進みます。これによって実装が正しいかどうか、目視確認を行うことができます。CodinGameにはソースファイルを1個だけ提出する必要があるため、盤面クラスのほかにCodinGame用の入出力を記述したmain関数もこのファイル内に記述することになります。同じソースファイルでローカルとCodinGame上の動作を切り替えたいため、マクロ定義 MODE_INTERACTIVE により切り替えます。このマクロは、.vscode/tasks.jsonで定義されているため、ローカルでビルドする際だけ有効になります。
#if defined(MODE_INTERACTIVE) int main() { Board board; board.set_hirate(); while (!board.is_end()) { cout << board.pretty_print(); cout << "Your turn: " << "xo"[board.turn()] << endl; vector<int> legal_moves; board.legal_moves(legal_moves); if (legal_moves.empty()) { cout << "No legal moves." << endl; UndoInfo undo_info; board.do_move(MOVE_PASS, undo_info); continue; } cout << "Legal moves: "; for (auto legal_move : legal_moves) { cout << move_to_str(legal_move) << ", "; } cout << endl; int move = legal_moves[0]; // キーボードから手を入力(省略) UndoInfo undo_info; board.do_move(move, undo_info); } cout << board.pretty_print(); cout << "End: " << board.count_stone(BLACK) << " - " << board.count_stone(WHITE) << endl; int diff = board.count_stone_diff(); if (diff < 0) cout << "WHITE wins" << endl; else if (diff > 0) cout << "BLACK wins" << endl; else cout << "DRAW" << endl; } #else int main() { /* codingame用の実装 */ } #endif
このコードを実行すると、以下のようなインターフェースで動作確認できます。
盤面クラスが動作したようなので、次はそれを用いて思考機能を実装します。
