前回、アルファベータ法＋石の数による評価によってランダムよりは強いAIを実装しました。ただし、合法手生成速度が遅く、CodinGameの制限時間内では深さ5までしか読めませんでした。アルファベータ法のAIそのものは最終的に使わないため速度はあまり重要ではないですが、合法手生成は学習データ生成のための対局で極めて頻繁に呼び出す箇所ですので、高速化しておくに越したことはありません。今回は、ビットボードを用いて高速化を行います。ただし、ビットボードのアルゴリズム自体は良い記事がすでにあるので、そちらに任せます。
この記事時点のバージョンです。
https://github.com/select766/codingame-othello/tree/5891f4351a08373f2a928f3bda56b6f7b7dbd69c
合法手生成のテストを書く
合法手生成のアルゴリズムを書き替える前に、合法手生成のテストを実装します。これにより、バグの混入リスクを下げることができます。盤面と合法手の組み合わせを手入力して作ることも考えられますが、今回は手軽に、現在動いているコードを用いてランダムなテストケースを生成することにしました。書き換え前に生成したテストケースを用いて書き換え後にテストし、パスすればそれで実装成功とみなします。もし失敗するようなら盤面を目視で確認し、書き換え前と書き換え後のどちらが正しいかを確認することにします。
こちらがテストケースを生成するmain関数です。書き換え前に実行し、出力を保存しておきます。
#elif defined(MODE_MAKE_LEGAL_MOVE_TEST_DATA) int main() { const int n_games = 1000; for (int i = 0; i < n_games; i++) { Board board; board.set_hirate(); while (!board.is_end()) { // 現在局面を出力 cout << board.get_position_string_with_turn() << "/"; // 合法手を列挙 vector<int> move_list; board.legal_moves(move_list); if (move_list.empty()) { cout << "pass" << endl; UndoInfo undo_info; board.do_move(MOVE_PASS, undo_info); continue; } // 合法手リストを出力(カンマ区切り) bool first_move = true; for (auto move : move_list) { if (!first_move) { cout << ","; } else { first_move = false; } cout << move_to_str(move); } // 各合法手で1手進めた局面を出力（局面は戻す） for (auto move : move_list) { UndoInfo undo_info; board.do_move(move, undo_info); cout << "/" << board.get_position_string_with_turn(); board.undo_move(undo_info); } cout << endl; // 合法手からランダムに1つ選び、局面を進める UndoInfo undo_info; board.do_move(move_list[i % int(move_list.size())], undo_info); } } return 0; }
そしてこちらがテストの実行を行うmain関数です。
#elif defined(MODE_LEGAL_MOVE_TEST) // 合法手生成が正しいかテストする vector<string> string_split(const string &str, char sep) { /* 省略 文字列を区切って返す */ } int main() { string test_case; int i = 0; int ok = 0; while (getline(cin, test_case)) { i++; // 入力: 局面/合法手カンマ区切り/合法手1で進めた局面/合法手2で進めた局面... auto elems = string_split(test_case, '/'); Board board; // 盤面をテストケース通りにセット board.set_position_string_with_turn(elems[0]); auto legal_moves_str = string_split(elems[1], ','); vector<int> expected_legal_moves; for (auto legal_move_str : legal_moves_str) { expected_legal_moves.push_back(move_from_str(legal_move_str)); } vector<int> sorted_expected_legal_moves = expected_legal_moves; sort(sorted_expected_legal_moves.begin(), sorted_expected_legal_moves.end()); vector<int> actual_legal_moves; board.legal_moves(actual_legal_moves, true); sort(actual_legal_moves.begin(), actual_legal_moves.end()); if (sorted_expected_legal_moves != actual_legal_moves) { // テスト失敗 continue; } if (actual_legal_moves[0] != MOVE_PASS) { // 各合法手で進めてみる int elem_idx = 2; bool success = true; for (auto move : expected_legal_moves) { UndoInfo undo_info; board.do_move(move, undo_info); auto actual_board = board.get_position_string_with_turn(); if (actual_board != elems[elem_idx]) { // テスト失敗 success = false; break; } board.undo_move(undo_info); elem_idx++; } if (!success) { continue; } } ok++; } }
ビットボードの実装
ビットボードのアルゴリズムは、kinakomochi氏のこちらの記事を参考にしました。
サンプルはRustで実装されているので、C++で実装しなおしました。Rustでマクロを用いている箇所は、C++ではテンプレートとラムダ関数を用いて実装しました。これにより、合法手がビットボードの形で得られるようになりました。具体的には、uint64_t型の整数で、ビットiがi番目のマスに対応し、そこに石を打てる場合は1、打てない場合は0が代入されます。uint64_tのエイリアスとしてBoardPlane型を定義しました。新たにビットボードで合法手を返すlegal_moves_bb関数を実装し、従来のvectorで合法手を返す関数は、内部でlegal_moves_bbを呼び出し、その結果を変形するように実装しました。
// ビットボードで合法手を返す
void legal_moves_bb(BoardPlane &result) const { /* 省略 */ }
// 従来通りのインターフェースを備えた合法手生成関数
void legal_moves(vector<int> &move_list, bool with_pass = false) const
{
move_list.clear();
BoardPlane bb;
legal_moves_bb(bb);
for (int pos = 0; pos < BOARD_AREA; pos++)
{
if (bb & position_plane(pos))
{
move_list.push_back(pos);
}
}
if (with_pass && move_list.empty())
{
move_list.push_back(MOVE_PASS);
}
}
盤面クラスには、終局判定に関する追加の改良を施しました。パスの情報は、直前の手番でパスをしたかどうか黒の番と白の番について別々の変数bool last_pass[N_PLAYER];に格納していました。しかし、実際には連続でパスされた回数さえ持っていれば十分ですので、整数1つ(int _pass_count)で表現するように変更しました。また、置かれている石の数を保持する変数int total_stonesを消去しました。この値が64になった際に終局という判定をしていましたが、ビットボードを用いれば空いているマスがあるかどうかが簡単に計算できるため不要となりました。
bool is_end() const
{
// 両プレイヤーが連続でパスしたか
if (_pass_count == 2)
{
return true;
}
// 空いているマスがあるか
if (~(planes[0] | planes[1]) == 0)
{
return true;
}
return false;
}
以上の修正を施したのち合法手生成のテストを行い、正常に動作していることが確認できました。
持ち時間を探索を打ち切るAI
今まで実装したアルファベータ法による探索部は、一定の深さまで探索する仕様でした。局面によって合法手の数が異なるため、時間制限を超えないようにするには深さを控えめに設定しておく必要がありました。できるだけ制限時間いっぱいまで思考できるよう、時間を確認しながら思考する探索部を実装しました。以下が新しいAI SearchAlphaBetaIterative の実装の概要です。CodinGameでは、1手当たり150ms以内で思考する必要があります。思考開始時にあらかじめ思考終了予定時刻を決めておき、再帰的な探索の最中で時間を確認するようにしています。自分で決めた思考終了時刻が到来してから手を出力することになるため、150msよりも短い時間を設定しないと時間切れになります。今回の実装では120msに設定しておきました。
class SearchAlphaBetaIterative : public SearchBase { int time_limit_ms; // 探索時間の制限[ms]。これを超えたことを検知したら探索を終了する。ルール上の制限時間より短く設定する必要がある。 bool stop; // 探索の内部で、時間切れなどで中断すべき場合にtrueにセットする。 int check_time_skip; // 時刻取得の回数を減らすためのカウンタ chrono::system_clock::time_point time_to_stop_search; // 探索を終了すべき時刻 public: // 制限時間を指定する SearchAlphaBetaIterative(int time_limit_ms = 1000) {} int search(string &msg) { node_count = 0; stop = false; auto search_start_time = chrono::system_clock::now(); time_to_stop_search = search_start_time + chrono::milliseconds(time_limit_ms); int bestmove = 0, score = 0, valid_depth = 0; for (int depth = 1; depth < 20; depth++) { int cur_bestmove; int cur_score = alphabeta(depth, -100000, 100000, &cur_bestmove) / 256; if (stop) { // stopで終了した探索は途中で打ち切られているので使用しない break; } valid_depth = depth; bestmove = cur_bestmove; score = score; } return bestmove; } private: bool check_stop() { if (stop) { return true; } // システムコール回数を減らす。数msに1回の呼び出しになる。 if (check_time_skip == 0) { if (chrono::system_clock::now() > time_to_stop_search) { stop = true; return true; } check_time_skip = 4096; } else { check_time_skip--; } return false; } int alphabeta(int depth, int alpha, int beta, int *bestmove) { if (check_stop()) { return 0; } // 再帰的に探索する } };
また、CodinGameのサーバにおけるC++のコンパイルオプションは固定されており、最適化が有効になっていないようです。ソースコードの先頭に以下の行を入れることで最適化が効き、少し高速化します。ただし、もっと良いオプションがあるため将来紹介します。
#pragma GCC optimize("O3")
以上の工夫により、ビットボード実装前は制限時間内に5手しか読めませんでしたが、8手程度読めるようになりました。Wood 2 Leagueで69位→17位まで上がりました。ただし、実際の対局を見てみると隅を容易に取られていることがわかりました。これをなくすには評価関数を改善することが必要です。
