YavalathのBitboard

github.com

Yavalathというボードゲームの2人向けルールのAIを、Bitboardを多用して実装しました。思考部分はMCTSで実装してあり、コマンドラインで遊べるようになっています。

盤面の表現

Yavalathは1辺5マスの六角形の盤面を使います。2人で交互に石を置いていき、4目以上並べたら勝ちで、ただし3目並べたら負けというルールです。(同時に満たした場合は勝利条件が優先されます)ちなみに『パイルール』という特殊ルールがオプションとして存在します。これは、先手が最初の手を指した直後に後手が「先手後手を交換するか否か」を選べるというルールです。このゲーム、先手は初手真ん中が圧倒的有利なのですが、パイルールはそれを封じさせます。先手有利だと交換されてしまうので、互角な初手を指すのが最善となるわけです。名前の由来は、「先手がパイを2つに切って後手が選ぶ」ことで両者が公平以上に感じられる分割ができるという逸話からです。(無羨望(envy-free)分割などと呼ばれる研究分野があります。)

……話を戻しますが、Yavalathは1辺5マスの六角形の盤面を使います。これは合計61マスなので、64bit整数1個でBitboardできます。例えば横ラインで4目並んでいる箇所を列挙する関数とか、横ラインが「●□●●」になっている箇所を列挙する関数とかは、以下のように書けます。

//uint64_t型変数がYavalathのビットボードだとする。すなわち、
/*
      1 2 3 4 5
    a . . . . . 6
   b . . . . . . 7
  c . . . . . . . 8
 d . . . . . . . . 9
e . . . . . . . . .
 f . . . . . . . . 9
  g . . . . . . . 8
   h . . . . . . 7
    i . . . . . 6
      1 2 3 4 5
*/
//という盤面(例えば左上はa1、右下はb5などと呼ぶ)だとして、変数が
//変数の最下位ビットが[a1]で、その次のビットが[a2]で、
//0b100000のビットが[b1]で、2^60のビットが[i5]だとする。

//xを2進数表示したときに、1が4個連続している箇所を全て探して、
//その最下位ビットが立っている値を返す。
//この関数はハッカーのたのしみ106ページ図6.5を参考にして書かれた。
uint64_t find_4_or_more_consecutive_bits(uint64_t x) noexcept {
	x = x & (x >> 2);
	x = x & (x >> 1);
	return x;
}

//xとyを2進数表示したときに、xが"1011"になっている箇所で、
//かつその0の箇所でyのビットが立っているような箇所をすべて探して、
//その最下位ビットが立っている値を返す。
//ただし、xとyで同じ箇所にビットが立っていないことを仮定する。
uint64_t find_0b1011(const uint64_t x, const uint64_t y) noexcept {
	const uint64_t xx = (x >> 1) & x;
	return (x >> 3) & (y >> 2) & xx;
}

constexpr uint64_t BB_MASK_4 = 0b000'00011'000111'0001111'00011111'000111111'00011111'0001111'000111'00011ULL;
constexpr uint64_t BB_MASK_3 = 0b000'00111'001111'0011111'00111111'001111111'00111111'0011111'001111'00111ULL;
constexpr uint64_t BB_MASK_2 = 0b000'01111'011111'0111111'01111111'011111111'01111111'0111111'011111'01111ULL;

find_4_or_more_consecutive_bits関数は、Bitboard上では4連続だけれど盤上では4連続ではないケースも拾ってしまいます。それはBB_MASK_4 変数で適宜マスクすれば解決できます。

Bitboardの回転

横ラインで特定のビットパターンになっている箇所を列挙することはできました。しかし、斜めラインはこの方法では扱えません。この課題に対して、今回はBitboardをn*60度(n=1,2,4,5)回転させる関数を用意して対処しました。具体的には、まず盤面を意味する構造体は元のBitboardを0度・60度・120度に傾けた状態を保持しておきます。そして「どれかのラインで特定のビットパターンになっている箇所を全列挙」とかするときは、3方向各々の横ラインを計算してから300度・240度回転させる関数を使って1個の64bit変数にまとめ直します。

この回転処理は、前回の記事で紹介した「ワードの一般的順列演算」に帰着させました。そのうえで、300度・240度回転についてはsag関数4回で計算できることを確認しました。

eukaryote.hateblo.jp

高速な1手詰め・3手詰め関数

任意のビットパターンを高速に列挙できるので、「そこに石を置くと(勝てる/即負けになる/王手になる)座標」とかも列挙できます。これらを用いれば1手詰めや3手詰めの存在を高速に検出できます。これによって、シミュレーションのときに3手詰めを回避できたり見逃さなかったりする、完全なランダムよりちょっと強いプレイヤーでシミュレーションできるわけです。

モンテカルロ木探索(MCTS)

対戦できるようにするための思考ルーチンはMCTSで作りました。いわゆる評価関数(=局面を引数に取り、優劣を予測してスカラー値を返す関数)が無い場合のベターな選択肢だと思われたからです。ただし実際にはそんなに強くなくて、人間側は序盤の手筋を知っていれば簡単に勝ててしまいます。Yavalathは1手差で勝敗が決まりやすいので、ランダムに近いシミュレーションで局面の優劣を正確に評価するのは難しいからだと思われます。

コード中ではMCTS_Solverクラスがこれを実装しています。MCTSは「selection→expansion→simulation→backpropagation」の4ステップから成りますが、これらを割と読みやすい形で実装できたと思っています。