Shougi

本将棋のサブセットである「５五将棋」のAIを ちょろちょろ書いている， 気づいたことをメモしておく． データ構造 それぞれの駒をビットボードで管理している． 例えば先手の歩が7番目の位置に存在すれば，bitboard[B_PAWN] = 0x40 のように表す． 飛車および角の効きはAVX2の_pext_u32命令を使い導出する[5]． 探索方針 基本はアルファベータ法で探索する． それに加えて，合法手をソーティングしつつ，反復深化させる． また，同一局面が現れた場合は，置換表を用いてalpha-betaのウィンドウ幅を狭める． Null-Window（PVS）探索も試してみたが，対して速くならなかった．むしろ遅い場合もある． 多分ソーティング方法が悪い． 評価関数 単純に駒の損得だけで評価している． 改善が必須． USI（Universal Shogi Interface）プロトコル 将棋GUIソフト[8]とAIを接続するプロトコルの1つがUSIである[6,7]． AIは，GUIソフトから局面や持ち時間を受け取り，決定した指し手を返す． とりあえず対応させた． OpenMPによる並列化 探索はOpenMPを使って並列化している． 与えられた局面の合法手をそれぞれ並列に探索する． 出来るだけ静的にリンクしたいので，ちょっと調べてみた． visual c++ 構成プロパティ - C/C++ - 言語 - OpenMPのサポートを「はい」にする 構成プロパティ - C/C++ - コード生成 - ランタイムライブラリを「マルチスレッド（/MT）」にする VCOMP{90,100,110,120}.dllに依存する VCOMP{90,100,110,120}.dllは，/MTを設定しても動的にリンクされるため， どこかで配布されているものを使ってみようかな[1,2]． gcc libcompに依存するが，静的リンクする方法はあるみたい[4]． intel compiler libiomp5m.libを静的リンクすることができるらしい[2]． 静的リンクは非推奨らしいが，-openmp-link staticオプションを付けると良いみたい（icpc -openmp -openmp-link static hello.cpp）[3]． 参考 [1] Stack Overflow, Is there a way to load in omp.h at compile time, therefore a machine never needs to fetch it at run time? [2] Visual Studio UserVoice site, Statically link openmp (vcomp*.dll) [3] Intel® C++ Compiler XE 13.1 User and Reference Guide - Using the OpenMP* Libraries [4] Stack Overflow, How to link libgomp statically when linking other libraries dynamically? [5] インテル C++ コンパイラー 14.0 ユーザー・リファレンス・ガイド - _pext_u32/64 [6] 将棋所 [7] The Universal Shogi Interface [8] プチ将棋の使い方

（7/10追記） 完全解析の結果を利用するAIをdobutsu-shogi.jar（17MB）に置いておきます．対戦してみてください． 今更な感じですが，どうぶつしょうぎの完全解析をしてみました． やり方はすでに公開されてますので，不明点はそちらを参考にしてください（「どうぶつしょうぎの完全解析」, 田中哲朗）． 私の実装もそちらを参考にしています． 解析のゴールは，後手の場合は78手で確実に勝ち，先手の場合は出来るだけ負けにくい手（負けまでの手数が最も長い手）を指すAIを完成させることです． 以下２つのステップにより，完全解析を目指します． 1つ目は，初期局面から開始し，ありうる全ての局面を展開することです． やり方は単純で，ある局面の合法手を全て展開していくだけです． 計算時間は数十分程度ですか，メモリを多く使います． そこで，駒を左右入れ替えて配置し直しても同じ局面と見なし（全ての駒の動きは左右対称であるから），局面数を減らします． 解析結果all-stateは，今後の利用のためソーティングしておくと良いです． all-stateは，1局面64bit x 246,803,167 = 1.9 GBくらいになります． コードはこちら． // // q: 未解析局面のキュー，初期値は初期局面のみが格納されたキュー // h: 解析済み局面のマップ，初期値は空マップ // all_state: 解析済み局面のベクタ，初期値は空ベクタ // while(!q.empty()) { if (i>=MAX_BOARD_NUM) { break; } b = q.front(); q.pop_front(); iter = h.find(b); if (iter == h.end()) { all_state.push_back(b); h.insert(b); i++; // 終わった盤面からは解析しない if (!is_win_state(b) && !is_lose_state(b)) { next_boards.clear(); get_next_board(next_boards, b); n = next_boards.size(); for (j=0; j<n; j++) { // ちゃんと正規化して，手番を合わせて保存 b = get_reverse(next_boards[j]); b = regulate(b); q.push_back(b); } } } } 2つ目は，全ての局面all-stateを勝ち/負け/引き分けのどれかに分類することです． まず，勝ち確定局面（次の一手で確実に相手のライオンが取れる），負け確定局面(勝ち局面ではなく，相手のライオンが自陣に位置しトライが決まった)，それ以外の局面の3種類に分類します． あとは，以下の方針で，勝ち局面/負け局面を解析していきます． どちらも増えなくなれば，残りを引き分け局面とし，プログラムを終了します． 次の局面の内少なくとも一つが負け局面であれば，その局面は勝ち局面 次の局面が負け局面に移行するように打てば勝てる 次の局面が全て勝ち局面であれば，その局面は負け局面 どのような手を打っても，次の局面は勝ち確定だから相手が勝つことになる コードはこちら． for(;;) { unsigned int win_add_num = 0; unsigned int lose_add_num = 0; for (size_t i=0; i<STATE_NUM; i++) { board b = all_state[i]; if (judge[i] == UNKNOWN) { // 一手先の局面から現在の局面の勝敗を判定 unsigned char winorlose = get_winorlose(b, all_state, judge); if (winorlose == WIN) { judge[i] = WIN; judge_count[i] = iter_num; win_add_num++; } else if(winorlose == LOSE) { judge[i] = LOSE; judge_count[i] = iter_num; lose_add_num++; } } } // これ以上勝ち確定も負け局面も増えなければ， // 残りは全て引き分け局面 if (win_add_num == 0 && lose_add_num == 0) { break; } } 結果として，カンペキな計算で作られたこのAI？は，後手の場合確実に勝てるものになりました． 先手の場合でも，ほとんど負けないでしょう． ...