Bitboard
将棋エンジンのことを調べて一番驚いたのが「Bitboard」という仕組みだ。
本ページではこれがどんなものであるかの説明と実装を行う。
Bitとは
「board」についてはタイトルを見ればなんとなく「将棋盤」のことを想像する方が多いと思う。これについては説明は不要だろう。
「Bit」についてもソフトウェア開発者であればまず説明の必要はないだろうが、そうでない方も読んでいるかもしれないので簡単に説明しておく。
Bitとは「0または1のみ保持可能なデータ」のことである。
一般的に扱う数字にも四則演算(+,-,×,÷)などの演算方法があるが、Bitには特別な演算方法がある。
これが将棋エンジンおよびBitboardにおいて非常に重要となるので簡単に紹介しておく。
|演算方法 |記号 |結果 | 0 X 0 | 0 X 1 (順不同) | 1 X 1 |
|---|---|---|---|---|---|---|
|OR || |どちらかが1なら1 | 0 | 1 | 1 |
|AND |& |両方1なら1 | 0 | 0 | 1 |
|XOR |^ |同じなら0違うなら1 | 0 | 1 | 0 |
また、一般的な数字も2進数に変換することでこれらの演算方法を適用することができる。
|式(10進数) |式(2進数) |結果(2進数) |結果(10進数) |
|---|---|---|---|---|---|---|
| 2 | 3 |10 | 11 |11 |3 |
| 2 & 3 |10 & 11 |10 |2 |
| 2 ^ 3 |10 ^ 11 |01 |1 |
Bitについてはここまで理解できれば大丈夫かと思う。
Bitboardとは
では「Bitboard」とはなんぞや？という話。
一言で書くと「Bitでできた将棋盤」である。
こんな感じ↓
これを81桁のBit(2進数)と捉えると1つのBitboardを数字として扱うことができる。
これがなに？と思うかもしれないが、
将棋エンジンの中ではこいつが信じられないほど大活躍しているのである。
Bitboardの活用例
もう少しイメージしやすくしたいと思う、
例として、初期配置における自分の駒の位置を示すBitboardは↓こうなる。
(この情報を81桁のBitとして数字で持つことができる)
初期配置における相手の駒の位置を示すBitboardは↓こう。
ここでこれら2つのBitboardをOR演算するとどうなるか？
このように初期配置における全ての駒の位置を示すBitboardを得ることができるのである。
もう1つ例を示す。
初期配置におけるすべての歩の位置を示すBitboardはこうなる。
これと先程の、初期配置における自分の駒の位置を示すBitboardをAND演算すると、
このように自分の歩の位置を取得できるわけである。
将棋エンジンはさまざまなケースのBitboardを内部で作成、必要に応じて演算することで盤上の情報を取得している。
もちろんBitboardを採用していない将棋エンジンも存在していると思うが、本記事ではこのタイプの将棋エンジンについて調べていく。
この仕組みだけでもよく思いついたものだと感じたものだが、将棋エンジン開発者はこの仕組をまた思いもよらない方法で活用していることがわかった。
そのすごさについては次回以降紹介していきたいと思う。
Bitboardの実装
さすがにここから先はソフトウェア開発の基本的な知見がある読者を想定する。
また、本記事における開発言語はC++とする。
本記事は主にやねうら王のソースコードを参考に作成するつもりであり、本ページでは現れないがやねうら王はC++特有の機能をふんだんに使用している。
実装といっても、今回は大したことをするわけではない。
81桁のBitを実際のデータにするだけだ。
81桁のBitデータを扱うのでBitboard自体のデータ量は128bit=16バイトが妥当だろう。
64bitのPCでは一度に128bitのデータを扱うことができないため、2つの64bitデータ(uint64_t)の配列とする。
大したことをするわけではない、とかいいつつかなり長くなってしまったが、
後半は動作確認と実行結果なので飛ばしてもらってもかまわない。
クラス定義
#pragma once
#include <iostream>
class Bitboard {
public:
Bitboard();
Bitboard(uint64_t l);
Bitboard(uint64_t u, uint64_t l);
uint64_t GetU() const;
uint64_t GetL() const;
private:
const int LOWER = 0;
const int UPPER = 1;
uint64_t bb[2];
};
64bitデータを2つを用意し、初期化用のコンストラクタと参照用のゲッタメソッド持つクラスを用意しただけである。
bb[1]が上位64bit、bb[0]が下位64bit。
オブジェクト指向で開発経験のある方ならなんら難しいことはないだろう。
実装
クラスの実装のコードは以下。
長いので分割して解説していく。
全体のコードはここを参照されたし。
まずは↑のヘッダで定義した機能を実装していく。
といっても、引数データの代入とメンバ変数の参照のみでなんら難しいことはない。
#include "bitboard.h"
Bitboard::Bitboard() { this->bb[UPPER] = 0; this->bb[LOWER] = 0; }
Bitboard::Bitboard(uint64_t l) { this->bb[UPPER] = 0; this->bb[LOWER] = l; }
Bitboard::Bitboard(uint64_t u, uint64_t l) { this->bb[UPPER] = u; this->bb[LOWER] = l; }
uint64_t Bitboard::GetU() const { return this->bb[UPPER]; }
uint64_t Bitboard::GetL() const { return this->bb[LOWER]; }
単体試験用プリプロセッサ定義
将来的に本来のmain関数は別で定義したく、ここでのmain関数はBitboardクラスの単体試験用として扱いたいのでUNIT_TEST_BITBOARDのプリプロセッサを定義している。
#ifdef UNIT_TEST_BITBOARD
#include <iostream>
#include <iomanip>
～～～
#endif // UNIT_TEST_BITBOARD
汎用定義値
汎用的な値をここで定義しておく。
BOARD_WIDTHは説明不要かと思う。
上位64Bbitは65桁目から開始するのでUPPER_BITを64と定義しておく(プログラム内では1桁目を0bitとするので1ずれる)。
本記事では筋を「FILE(またはFile)」、段を「RANK(またはRank)」と表現する。
プログラム内では0を起点とすることが多いため、1筋を0、9筋を8で表現するが、
直感的にわかりにくいため、FILE_1(=0)～FILE_9(=8)を定義しておく。
(段についても同様)
なお、本来は適した場所に定義するべきかと思うので、今後修正する。
const int BOARD_WIDTH = 9;
const int UPPER_BIT = 64;
enum { FILE_1, FILE_2, FILE_3, FILE_4, FILE_5, FILE_6, FILE_7, FILE_8, FILE_9, FILE_NB };
enum { RANK_1, RANK_2, RANK_3, RANK_4, RANK_5, RANK_6, RANK_7, RANK_8, RANK_9, RANK_NB };
Bitboardの視覚化
GetU関数とGetL関数で値の確認はできるが、
それだけで想定したBitboardを現しているか確認するのは難易度が高い(できる人はできそうだが)。
そこで入力したBitboardを視覚的に確認する機能を実装する。
bitが1となっている升を"*"、bitが0となっている升を”.”で表現して、
これを9×9の形式で出力する。
指定された升が上位64bitか下位64bitかの判定および処理の制御はもう少しスマートに書けるので、今後修正する。
void Print(Bitboard bb) {
uint64_t u = bb.GetU(), d = bb.GetL();
for (int r = RANK_1; r < RANK_NB; r++) {
for (int f = FILE_9; f >= FILE_1; f--) {
int shift = f * BOARD_WIDTH + r;
if (shift < UPPER_BIT) {
std::cout << ((d & ((uint64_t)1 << shift)) ? "*" : ".");
}
else {
shift -= UPPER_BIT;
std::cout << ((u & ((uint64_t)1 << shift)) ? "*" : ".");
}
std::cout << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
}
動作確認(デフォルトコンストラクタ)
ではmain関数で順番に動作確認していく
int main(int argc, char **argv) {
～～～
}
まずはデフォルトコンストラクタの動作確認を行う。
値とBitboardの両方を確認している。
値は64bitなので16桁の16進数で示すのが妥当かと思う。
Bitboard bb0 = Bitboard();
std::cout << "bb0.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb0.GetU() << std::endl;
std::cout << "bb0.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb0.GetL() << std::endl;
Print(bb0);
実行結果は以下になると思う。
bb0はどのBitも0なので全ての升が”.”となる。
bb0.GetU()=0x0000000000000000
bb0.GetL()=0x0000000000000000
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
動作確認(引数付きコンストラクタ)
次に引数付きコンストラクタ2つを見ていく。
Bitboard bb1 = Bitboard(1);
std::cout << "bb1.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb1.GetU() << std::endl;
std::cout << "bb1.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb1.GetL() << std::endl;
Print(bb1);
Bitboard bb2 = Bitboard(1, 1);
std::cout << "bb2.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb2.GetU() << std::endl;
std::cout << "bb2.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb2.GetL() << std::endl;
Print(bb2);
実行結果は以下になると思う。
bb1は下位64bit=1なので、１一の升が、
bb2は下位64bit=1、上位64bit=1なので、１一と８二の升が、
それぞれ"*"となる。
bb1.GetU()=0x0000000000000000
bb1.GetL()=0x0000000000000001
. . . . . . . . *
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
bb2.GetU()=0x0000000000000001
bb2.GetL()=0x0000000000000001
. . . . . . . . *
. * . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
動作確認(例で示したBitboard)
最後に↑の例で示したBitboardの値を代入して確認してみる。
// 初期配置における自分の駒の位置
Bitboard bb3 = Bitboard(0x140E0, 0x5028140A05038140);
std::cout << "bb3.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb3.GetU() << std::endl;
std::cout << "bb3.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb3.GetL() << std::endl;
Print(bb3);
// 初期配置における相手の駒の配置
Bitboard bb4 = Bitboard(0x503, 0x8140A05028140E05);
std::cout << "bb4.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb4.GetU() << std::endl;
std::cout << "bb4.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb4.GetL() << std::endl;
Print(bb4);
// 初期配置における全ての駒の配置
Bitboard bb5 = Bitboard(0x145E3, 0xD168B45A2D178F45);
std::cout << "bb5.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb5.GetU() << std::endl;
std::cout << "bb5.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb5.GetL() << std::endl;
Print(bb5);
// 初期配置における全ての歩の配置
Bitboard bb6 = Bitboard(0x4422, 0x1108844221108844);
std::cout << "bb6.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb6.GetU() << std::endl;
std::cout << "bb6.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb6.GetL() << std::endl;
Print(bb6);
// 初期配置における自分の歩の配置
Bitboard bb7 = Bitboard(0x4020, 0x1008040201008040);
std::cout << "bb7.GetU()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb7.GetU() << std::endl;
std::cout << "bb7.GetL()=0x" << std::setw(16) << std::setfill('0') << std::hex << bb7.GetL() << std::endl;
Print(bb7);
実行結果は以下になると思う。
bb3.GetU()=0x00000000000140e0
bb3.GetL()=0x5028140a05038140
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
* * * * * * * * *
. * . . . . . * .
* * * * * * * * *
bb4.GetU()=0x0000000000000503
bb4.GetL()=0x8140a05028140e05
* * * * * * * * *
. * . . . . . * .
* * * * * * * * *
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
bb5.GetU()=0x00000000000145e3
bb5.GetL()=0xd168b45a2d178f45
* * * * * * * * *
. * . . . . . * .
* * * * * * * * *
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
* * * * * * * * *
. * . . . . . * .
* * * * * * * * *
bb6.GetU()=0x0000000000004422
bb6.GetL()=0x1108844221108844
. . . . . . . . .
. . . . . . . . .
* * * * * * * * *
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
* * * * * * * * *
. . . . . . . . .
. . . . . . . . .
bb7.GetU()=0x0000000000004020
bb7.GetL()=0x1008040201008040
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
* * * * * * * * *
. . . . . . . . .
. . . . . . . . .
余談
ちなみにBitboardはコンピュータチェスの開発者の発想だと聞いたことがある。
チェスの盤面は8×8=64なのでBitboardは64bitで収まり、64bitデータ1つでちょうど収まりきるのである。
本当によく思いついたものだ。
やねうら王は深すぎる
なお、やねうら王は深すぎる理由により、升目とBitの対応が本ページで説明したものとは異なっている。
その理由については今後説明したいと思う。
また実装におけるデータ型もuint64_tではなく、特殊なデータ型を使っているが、
ここではわかりやすくするためシンプルな64bitデータを使うことにする。
深すぎる理由についてはやねうら王のソースコードややねうらおさんのブログが参考になると思う。