bitboardアルゴリズムでN-Queen問題を解く

はじめに

探索アルゴリズムを組むにあたって、配列を使うと効率が良くないので ビット列を使って節約することが知られている。 自分もオセロのCPUアルゴリズムを組んでいるときにビットボードの存在を知った。 ビットボードは書いたことがなく面白そうだったので、比較的簡単なアルゴリズムで書けるN-Queenをbitboardで解いてみることにした。

N-Queen問題

その名の通りだが、NxNのチェス版に、N個のクイーンを互いに取られない位置に配置する組み合わせを求める問題である。 クイーンは将棋の飛車と角行を組み合わせた動き、つまり縦横斜めに移動できるので、 その一直線上に複数のクイーンが配置されないようにする必要がある。

作ったもの

https://github.com/grugrut/n-queen

こちらで作成した。 言語はとくにこだわりなかったのでgolangで。

配列で素直に解くナイーブな解法と、bitboardを使う解法の二種類で書いている。 bitboardの場合はuint64で表現している都合上、変数1つでは8x8の盤面までしか表現できないので、 変数4つ使って16x16まで表現できるものも実装してみた。

時間計測

bitboardは省メモリももちろんだが高速化のために使われるので、 どれほど速度があがるかを見てみた。

8x8ぐらいの盤面までは、ほとんど大差ないが、9x9ぐらいから目に見えて時間が違ってきた。 11x11になると、とりうるクイーンの配置パターンが1200兆通りぐらいあるはずなので、 そこから効率的に探索ができているということがわかる。

bitboardのしくみ

ビットボードでは、それぞれのセルを1bitで示し、 操作もビットの論理演算とシフト演算の組み合わせで実現する。

クイーンがいるセルのbitを1、空のセルを0としたbit列を用意しておくと、 例えば左方向については、1ビットずつビットシフトしたものの論理和を求めることで 左方向にクイーンが効いているセルをまとめて求めることができる。 ただし、単純にビットシフトしていくだけだと左端のものをビットシフトしたときに 繰り上がり(といってよいかわからないが)により、1つ上の行の右端に移動してしまうので、 0b011111110111111011111101111110111111011111101111110111111 との論理積をビットシフトしていくことで、左端のクイーンは0になり繰り上がりを防止することができる。

こうすることで、通常の配列だと1つずつループさせないといけないのに対してビットシフトなら 複数のクイーンについてまとめて計算できるので効率よく求めることができるというわけだ。

これを八方向に対して計算することで、今のクイーンが効いているセルを求めることができる。 この状態では、1はクイーンが配置できないセル、0はクイーンが配置できるセルであるので、 0のセルに配置しては効いてるセルを求め、結果N個のクイーンが配置できれば成功となる。

候補の探索をする際には、特定のビット列 bに対して、 (b & -b) を求めることで bの一番下の1になっているビットだけが抽出できるため、 先ほどのビット列の否定(この場合は、1がクイーンが配置できるセルになるので、ここから1になっているところを抽出できれば、それが探索候補になる)に対して、 上記の計算をすれば、探索候補を順に求めていくことができる。

細かいところでは探索済のビット列を別に持っていて、何度も同じ探索をしないように、とかのロジックも入れているが 基本的な仕組みは以上である。

まとめ

uint64でビット演算を考えると意外と思い違いなどもあり、多少苦戦したが 思ったよりも簡単にN-Queenのビットボードは実装できた。

もともとの目的だったオセロのアルゴリズムについても今後ビットボードアルゴリズムで書き直して 短時間で強い探索ができるオセロAIを作成していきたい。