電王戦を振り返って
この記事はIS17erアドベントカレンダー17日目の記事として、19日目の記事にインスパイアされて書きました。
Girigiri
今年、電王戦にチームGirigiriとして初参加しました。
今年の電王戦は、わずか半年前の世界コンピュータ将棋選手権で優勝したelmoが上位5位にも入らなかったことからもわかるように、昨年度に比べて大幅にソフトが強くなりました。
大会に出場する多くのソフトがオープンソースの思考エンジンや評価関数生成プログラムを使用している中、GirigiriはC++で全プログラムを完全フルスクラッチで書きました。結果としてわりと惨敗だったのですが、同世代の優秀な人とのつながりが増えたことや、ディープラーニングの強さを学ぶことができたので、収穫は大きかったです。
実装
定石部分：なし
思考部：アルファベータ探索
盤面データ：ビットボード
思考部はパートナーが中心に実装してくれたので、ぼくはビットボードについて書きます。
ビットボードの構成
講義で出たオセロAI実装の課題で実装した人もいるとは思いますが、将棋におけるビットボードは、各駒の位置を一つの整数で保持するという考えに基づきます。イメージとしては、将棋には40種類の駒があるので、大きさ40の配列で、配列の各要素がそれぞれの駒の位置を表すと言った感じです。駒の種類ごとにビットボードを用意するケースとかもあるらしいのですが、Girigiriでは二歩判定のために歩のビットボードを用意しただけで、他の種類については種類ごとのビットボードを持っていません。ちなみにGirigiriのビットボードの仕様も完全独自なので他AIの仕様には詳しくありません。
オセロの場合は、黒と白の石について持てばいいので、uint64_tの整数2つですべてを表せますが、将棋の場合はそんな簡単に行きません。
将棋の場合は次のような困難が伴います。
- マス目が9x9なので81bit以上の整数が必要
- 相手の駒をとって自分の駒にすることができ、所有者の変更が起こる
- 持ち駒として盤面に登場しないときもある
- 成る
こんな感じでしょうか。見るだけでだるそう・・・という気分がしますが、実際かなりだるいです。
C++では、#include <bitset>をすることにより、任意長のビットを扱うことができますが、ベンチマークをとったところ、g++/clang拡張の__uint128_t型を使うほうが早かったのでやめました。
さて、ビットボードとして1駒について128bit分の情報を確保することにしたのですが、盤面情報の81bit以外にも情報が入ります。そこで、次の情報を保持することにしました。
-
id
先手歩を0~8, 香を9~10, ...といったように0から39までのidを振りました。また、40を先手の駒すべて、41を後手の駒すべて、42を先手の歩、43を後手の歩としています。6bitで表せる情報です。 -
所有者
最下位ビット（0ビット目）で所有者を表します。 -
成判定
1ビット目で成っているかを判定します。 -
評価値
上位32bitにint32_tの評価値を無理やり格納します。評価値とは、その手を打ったあとの盤面の評価値です。
結局以下のようになっています。
0: black/white
1: promoted?
2-82: position
83-88: id
96-127: eval
ちなみに、大会環境のPCで、アルファベータで枝刈りされた局面を除いても、一秒間におよそ1000万局面探索できていることがわかります（それでも10秒近く探索して5,6段の探索ですが・・・）。
ビットボードで駒を動かす
本題はこちらです。いくらうまく情報を格納するビットボードを考えても、駒を効率良く動かすことができなければビットボードを使うメリットはありません。配列でいいです。
駒を動かすという情報ですが、これは、動かす前の駒と動かしたあとの駒の位置のビットを立てた__uint128_tで表現します。こうすると、駒を動かす情報だけを見ても、AをBに動かしたのか、BをAに動かしたのかはわかりませんが、今の盤面のその駒のビットボードとのxorをとることで、駒の動きを実現できるというメリットが大きいです。ちなみにもう一度xorをとると一つ前の盤面に戻ることができます。持ち駒を打つ場合にこの形式では一つ前に戻ることができませんが、そこは別途処理を書きます。
どうやって駒を動かすかについてですが、まずはわかりやすい「金」の場合で解説します。
金は以下のように動くことができます。
OOO
OXO
XOX
実際に動けるのは、このOの位置で、しかもそこに自分の駒が存在していないような位置です。
とりあえず、以下のGoldMovesのような関数で、次にその駒が動ける位置のビットを立てた__uint128_tを返します。駒が一番上の段や一番下の段にいる場合は、動き方が制限されるので、条件分岐させています。
static __uint128_t GoldMoves(__uint128_t i) {
i >>= 2;
i &= ((__uint128_t(1) << 81) - 1);
if (i & ROWS[8]) {
return (((i >> 1) | (i >> 9) | (i >> 10) | (i << 9) | (i << 8)) << 2) & ((__uint128_t(1) << 83) - 1);
} else if (i & ROWS[0]) {
return (((i << 1) | (i >> 9) | (i << 9)) << 2) & ((__uint128_t(1) << 83) - 1);
} else {
return (((i << 1) | (i >> 1) | (i >> 9) | (i >> 10) | (i << 9) | (i << 8)) << 2) & ((__uint128_t(1) << 83) - 1);
}
}
次の関数で合法手を生成します。重要な点は、GoldMovesの結果得られた整数から1ビットずつ、実際の手を取り出す過程です。
下に掲載しているコードを解説します。
moves = pieceMoves(board[i]) & ~board[40];
pieceMovesはGoldMovesに読み替えてください。これで、先程生成された合法手のうち、自分の駒にかぶっているものを弾きます。
while (moves) {
move = moves & (-moves);
...
moves ^= move;
}
では、movesの最下位ビットから順に、そのビットだけ立った整数を取り出しています。x & (-x)はxの最下位ビットのみが1で他が0の整数を返します。
内側でやっている処理は、動いた先に相手の駒があった場合の評価値の更新や、成るかどうかの処理です（金の場合は成駒がないので、不要ですがこの関数は共通処理なので）
moves = pieceMoves(board[i]) & ~board[40];
while (moves) {
move = moves & (-moves);
if (maskPos(move & board[41])) {
idx = posToIdx[getPos(move & board[41])];
if ((board[idx] >> 1) & 1) {
meval = move | (__uint128_t(int(CAPTURED_COEF * WEIGHTS[idx] + PRO_WEIGHTS[idx])) << 95);
} else {
meval = move | (__uint128_t(int((1 + CAPTURED_COEF) * WEIGHTS[idx])) << 95);
}
} else {
meval = move;
}
m = board[i] | meval;
if (maskPos(m) & (ROWS02 << 2) && !((m >> 1) & 1)) {
ret.push_back((m + (__uint128_t(PRO_WEIGHTS[i] - WEIGHTS[i]) << 95)) | 2);
if (!(isKnightIdx(i) && maskPos(m) & (ROWS01 << 2))) ret.push_back(m);
} else {
ret.push_back(m & ~2);
}
moves ^= move;
}
ここまで来て、評価関数が具体的にどうなっているか気になっている人は多いと思いますが、単に駒得の評価値です。おかげで惨敗したのですが、Girigiriを書いている途中に、評価値を出来る限り軽くした時、どこまで探索できるのかということが気になって突き詰めていった結果なのでしょうがないかなあと思っています。
飛車角を動かす
金や桂馬を動かすのは上に述べた方法で簡単ですが、飛車や角の場合、そう簡単ではありません。角の場合を例にとりますが、以下のような方法で行いました。
まず、角の動きを4方向に分けます。なぜなら、金の場合のようにwhile文で探索を書きたいからです。左上に動く場合についてまとめます。
以下のbishopTopLeft[i]は、いま角がi（i行j列を9*j+iに対応させている）の位置にいるとき、角が左上に進むとして、進むことができる位置のビットをすべて立てた整数です。ここで、自分の駒や相手の駒の位置関係は無視しています。C++では__uint128_tのリテラルを使うことができないので、64bitをシフトする形でコードを書いています。世界一読みにくい。
static __uint128_t bishopTopLeft[] = {
(__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 1ul, (__uint128_t(0ul) << 64) + 2ul, (__uint128_t(0ul) << 64) + 4ul, (__uint128_t(0ul) << 64) + 8ul, (__uint128_t(0ul) << 64) + 16ul, (__uint128_t(0ul) << 64) + 32ul, (__uint128_t(0ul) << 64) + 64ul, (__uint128_t(0ul) << 64) + 128ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 512ul, (__uint128_t(0ul) << 64) + 1025ul, (__uint128_t(0ul) << 64) + 2050ul, (__uint128_t(0ul) << 64) + 4100ul, (__uint128_t(0ul) << 64) + 8200ul, (__uint128_t(0ul) << 64) + 16400ul, (__uint128_t(0ul) << 64) + 32800ul, (__uint128_t(0ul) << 64) + 65600ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 262144ul, (__uint128_t(0ul) << 64) + 524800ul, (__uint128_t(0ul) << 64) + 1049601ul, (__uint128_t(0ul) << 64) + 2099202ul, (__uint128_t(0ul) << 64) + 4198404ul, (__uint128_t(0ul) << 64) + 8396808ul, (__uint128_t(0ul) << 64) + 16793616ul, (__uint128_t(0ul) << 64) + 33587232ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 134217728ul, (__uint128_t(0ul) << 64) + 268697600ul, (__uint128_t(0ul) << 64) + 537395712ul, (__uint128_t(0ul) << 64) + 1074791425ul, (__uint128_t(0ul) << 64) + 2149582850ul, (__uint128_t(0ul) << 64) + 4299165700ul, (__uint128_t(0ul) << 64) + 8598331400ul, (__uint128_t(0ul) << 64) + 17196662800ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 68719476736ul, (__uint128_t(0ul) << 64) + 137573171200ul, (__uint128_t(0ul) << 64) + 275146604544ul, (__uint128_t(0ul) << 64) + 550293209600ul, (__uint128_t(0ul) << 64) + 1100586419201ul, (__uint128_t(0ul) << 64) + 2201172838402ul, (__uint128_t(0ul) << 64) + 4402345676804ul, (__uint128_t(0ul) << 64) + 8804691353608ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 35184372088832ul, (__uint128_t(0ul) << 64) + 70437463654400ul, (__uint128_t(0ul) << 64) + 140875061526528ul, (__uint128_t(0ul) << 64) + 281750123315200ul, (__uint128_t(0ul) << 64) + 563500246630912ul, (__uint128_t(0ul) << 64) + 1127000493261825ul, (__uint128_t(0ul) << 64) + 2254000986523650ul, (__uint128_t(0ul) << 64) + 4508001973047300ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 18014398509481984ul, (__uint128_t(0ul) << 64) + 36063981391052800ul, (__uint128_t(0ul) << 64) + 72128031501582336ul, (__uint128_t(0ul) << 64) + 144256063137382400ul, (__uint128_t(0ul) << 64) + 288512126275026944ul, (__uint128_t(0ul) << 64) + 577024252550054400ul, (__uint128_t(0ul) << 64) + 1154048505100108801ul, (__uint128_t(0ul) << 64) + 2308097010200217602ul, (__uint128_t(0ul) << 64) + 0ul, (__uint128_t(0ul) << 64) + 9223372036854775808ul, (__uint128_t(1ul) << 64) + 18014398509481984ul, (__uint128_t(2ul) << 64) + 36063981391052800ul, (__uint128_t(4ul) << 64) + 72128031501582336ul, (__uint128_t(8ul) << 64) + 144256063137382400ul, (__uint128_t(16ul) << 64) + 288512126275026944ul, (__uint128_t(32ul) << 64) + 577024252550054400ul, (__uint128_t(64ul) << 64) + 1154048505100108801ul
};
あとは、簡単で、while文の中で間に自分の駒がないかや、相手の駒が２つ以上ないかなどをチェックすればいいです。いかにコードの抜粋を示します。
moves = bishopTopLeft[getPos(board[i])] << 2;
bool blocked = false;
while (moves) {
move = msb(moves);
if (maskPos(move & board[41])) {
idx = posToIdx[getPos(move & board[41])];
if ((board[idx] >> 1) & 1) {
meval = move | (__uint128_t(int(CAPTURED_COEF * WEIGHTS[idx] + PRO_WEIGHTS[idx])) << 95);
} else {
meval = move | (__uint128_t(int((1 + CAPTURED_COEF) * WEIGHTS[idx])) << 95);
}
} else {
meval = move;
}
if (move & board[40] || blocked) break;
if (move & board[41]) blocked = true;
m = board[i] | meval;
if (maskPos(m) & (ROWS02 << 2) && !((m >> 1) & 1)) {
ret.push_back((m + (__uint128_t(PRO_WEIGHTS[i] - WEIGHTS[i]) << 95)) | 2);
} else {
ret.push_back(m & ~2);
}
moves ^= move;
}
moves = bishopBottomLeft[getPos(board[i])] << 2;
leftTopの場合は、whileの探索順序が金の場合と同じで最下位ビットからなんですが、たとえばrightBottomの場合は最上位ビットからなので、ちょっと難しくなります（省略します）。
持ち駒を使う
合法手の表現上、単に、置きたい位置のビットを立てるだけで終わりです。
手を適用する
上述したように、基本はxorをとるだけですが、相手の駒をとった場合や成った場合には処理が追加されます。
所有者の変更や、成ビットを1にする処理をちゃんと書くだけです。
さいごに
やることは決まっていますが、本当にバグ地獄に苦しみました。バグに気づいてから4時間立って、原因箇所を突き止めて、さらに2時間コードとにらめっこしてtypoを直す、みたいな作業を無限回繰り返しました。
この他にも、通信用プロトコルの実装など、やることはかなり多く、大会3日前ぐらいからラストスパートの実装をしていて、本当にギリギリに完成させました。二歩判定はすごく気をつけていたはずなんですが、大会中にも数回二歩で判定負けをしてしまったので、まだバグが残っていたようですが、とりあえずGirigiriのコードはRustに生まれ変わることになったので、この煩雑な実装はいったんここまでということで、忘れようと思います。