eye_catching

「Sayuri で徹底解説! チェスエンジン・テクノロジー!」は、僕の自作チェスエンジン「Sayuri」に使われているチェスエンジンの技術を漫才形式で紹介するコーナーです。

第2回のテーマは「ビットボード」です。

解説 & 漫才


「エンジンの作成には先ず「エンジンにおけるチェスボードの表現」が必要・・・ってことで今回のテーマは「ビットボード」だよ。」

Sayuri
「ビットボード」はチェスエンジンの高速化の要どすな。
「ビットボード」のないエンジンは「かそく」のない「バシャーモ」のようなものどす。」


「もうか」舐めんな。
で、「ビットボード」っていうのはチェスボード上の「ある : 1」「なし : 0」といった「真理値」を表現するための 64bit の「ビットパターン」のこと。
下図のように 64bit を使って 64マスの各マスの真理値を表現しているんだ。」

bitboard

Sayuri
「これを使うと何がお得か説明しろどす。」


「偶然にもチェスボードのマスの数は「64」、そして・・・

  • 現在の CPU のレジスタのサイズは「64」bit。
  • 各プログラミング言語には「64」bit 符号なし整数を一つの変数として扱える。

・・・ってことから・・・

  • 「ビット演算」で高速に「ボードの状態」を分析・操作できる。
  • 「ボードの状態」のコピーが、単なる「整数値」のコピーと同じ。
  • 関数への「ボードの状態」の入出力が、単なる「整数値」の入出力と同じ。
  • 「駒の配置」や「駒の動ける位置」などを「ビットパターン」として記録・再利用できる。
  • 「駒の配置」や「駒の動ける位置」などを「定数」としてコードに埋め込める。

・・・ってことができちゃう。」

Sayuri
「チェスボードのマスの数が「たまたま」64マスだったから簡単にできたどすな。
81マスの将棋はビットボードの扱いが少し複雑みたいどす。」


「とっても便利なビットボード。 これを上手く使うと・・・

  • 「指し手生成」の高速化。
  • 「駒の数のカウント」の高速化。
  • ループの周回数を最小化。
  • CPU の「キャッシュメモリ」を使った高速化。

・・・などなど、様々な「裏技」が使える。」

Sayuri
「そうやって「裏技」を使いまくってコードがどんどん複雑怪奇なものに変貌していくどす。
「高速化」と「可読性」は両立しないどす。
うちのコードなんて「メタプログラミング」を使いまくったり、「Python を使った C++ コードの生成」などで、オープンソースにもかかわらず書いた本人しか理解できない状態になっているどす。」


「フッ・・・甘いな、もう書いた本人でも理解できる自信がないぜ。

Sayuri
「プログラミング作法」の一番ダメなやつどすな。」


「とりあえずビットボードを使った例をいくつか紹介するよ。」

ポーン・ナイト・キングの指し手生成

header_1


「先ずは「ポーン」「ナイト」「キング」といった「点から点へ移動する駒」の指し手の生成方法の紹介。」

Sayuri
「しろどす。」


「このタイプの駒の指し手、実は、必要になった時に計算して生成しているわけじゃなく、予めメモリ上にビットボードで準備しておいて、それを再利用しているだけだったりする。」

Sayuri
「具体例がないと言っている意味が分からないどす。」


「例えば「e4 にいるナイト」の行ける場所は「c3」「d2」「f2」「g3」「g5」「f6」「d6」「c5」の 8ヶ所って決まってる。
だからわざわざ必要になった時に「現在地から右右下と右下下と・・・」っていう計算をしなくても、ゲームが始まる前にビットボードにその 8ヶ所を記録して準備しておいて、あとはそれを現在の味方の駒のいる位置のビットボードでビット演算して削ればいい。」

knight_move_square_bitboard

bitboard_t knight_moves[64];

ナイトの行ける場所 =  knight_moves[ナイトの位置] & ~味方の駒のビットボード

Sayuri
「つまり、「ポーン」「ナイト」「キング」の各マスにおける「行ける場所」はゲームが始まる前に予め用意されているってことどすな。」


「そういうこと。
チェスエンジンは「先読み」をする際にメモリ上で実際に駒を動かすんだけど、局面を 1つ進める度に律儀に計算して次の指し手を生成していたらとんでもない時間がかかってしまう。
だからゲームが始まる前の「エンジンの初期化」や、コンパイル時の「メタプログラミング」で指し手を作っておくって感じ。」

Sayuri
「いかに努力しないか」に全力を注ぐ・・・・・・プログラマーに重要なのは「徹底的な怠惰」のセンスどすな。」

ビショップ・ルーク・クイーンの指し手生成

header_2


「今度は「ビショップ」「ルーク」「クイーン」といった「線で移動する駒」の指し手の生成方法の紹介。」

Sayuri
「しろどす。」


「実はこれ「マジックビットボード」っていう「魔法少女的な裏技」を使って作っている。」

Sayuri
「そうやって無節操に「萌え」をねじ込む態度が、世間が「萌え豚」に冷たい視線を向ける理由どす。」


「で、「マジックビットボード」の考え方をステップバイステップで説明すると・・・

【ステップ 1】 チェスの「縦」「横」「斜め」のラインって最大で 8マスだよね。

magic_1
【ステップ 2】 「8」といえば「8bit 符号なし整数型」だよね。
【ステップ 3】 「8bit 符号なし整数型」って数字で言うと「0 から 255」だよね。
【ステップ 4】 256 個のビットボード (8 バイト) の配列ってそんなにデカくないよね。
【ステップ 5】 だったら 8bit の「ミニビットボード」って「配列のインデックス」としても使えるよね。

bitboard_t line_moves[256];

ラインのビットボード = line_moves[ミニビットボード];

【ステップ 6】 ところで、ライン上の「行ける場所」は「その駒の位置」「その駒のいるライン上の駒の配置パターン」で決まるよね。

ラインのビットボード = line_moves[駒の位置][ミニビットボード];

【ステップ 7】 だったら「その駒の現在地」「ラインの種類 (0度、45度、90度、135度)」「その駒のいるライン上の駒の配置パターンのミニビットボード」というインデックスの「指し手のビットボード」の 3次元配列なんてのを作れば、必要に応じてわざわざ指し手を生成しなくてもいいよね。

ラインのビットボード = line_moves[駒の位置][ラインの種類][ミニビットボード];

・・・ってな感じ。」

Sayuri
「ザックリ言うと、8マスの小さなチェスボードをインデックスとした配列に、指し手のビットボードを記録しておくって寸法どすな。」


「ただこの方法を使うにはボードを「45度」「90度」「135度」に回転したビットボードも必要だったりする。
チェスエンジンのボードの定義がやたら複雑なのは「計算の手抜き」のための工夫。
メモリ上で 1手動かした時の処理は増えるけど、「ゲームの木」が「指数関数的」に増えていくってことを考えると「葉ノード」でまとめて処理するより圧倒的に早い。

num_job_all_nodes
num_job_leaf_nodes

Sayuri
「指数関数的」の性質の理解が不可欠どすな。
「指数関数的」ってのをザックリ「バカでかい」って意味で捉えているとできない発想どす。
そういやあんさん、歩きながら数学の研究をする癖は直したほうがいいどす。
この前、頭の中で計算している時、横断歩道を青信号で止まって赤信号で渡ったどす。
その時はたまたま車が通っていなかったものの、冗談抜きで冷や汗ものだったどす。」


「へぇ、お前が僕の心配をするなんて珍しい。 もしかして僕にデレた?

Sayuri
「違うどす。 うちはあんさんの想像の産物どす。 あんさんが死ねばうちも死ぬどす。
うちがあんさんの意識を乗っ取る前に死なれては困るどす。」


「いまサラッとサイコなこと言った?」

ビットのカウント

header_3


「ビットボードで駒を表現すれば、ビットのカウントアルゴリズムで駒の数を数えられる。

Sayuri
「あっ、説明完了したどす。」


「・・・・・・・・・・・・。
「アルゴリズム的に最速」なやつは・・・

int count_bits(bitboard_t bb) {
  bb = (bb & 0x5555555555555555) + ((bb >> 1) & 0x5555555555555555);
  bb = (bb & 0x3333333333333333) + ((bb >> 2) & 0x3333333333333333);
  bb = (bb & 0x0f0f0f0f0f0f0f0f) + ((bb >> 4) & 0x0f0f0f0f0f0f0f0f);
  bb = (bb & 0x00ff00ff00ff00ff) + ((bb >> 8) & 0x00ff00ff00ff00ff);
  bb = (bb & 0x0000ffff0000ffff) + ((bb >> 16) & 0x0000ffff0000ffff);
  return (bb & 0x00000000ffffffff) + ((bb >> 32) & 00000000ffffffffff);
}

ってのなんだけど、「実際は」もっと高速な方法があったりする。」

Sayuri
「さすがに一行で説明完了したらカッコがつかなかったどすか。 まあいいどす。」


「実は「アルゴリズム的」にはそんなに早くないんだけど、「CPU のキャッシュメモリ」を使うと上記の方法より演算がシンプルな分早くなるってやつがある。
それは予め「16bit」の全てのビットパターンにおけるビットの数を計算して「2 の 16乗」個の「8bit 整数型」の配列に格納する。
で、ビットボードを 16bit ずつその配列でビットの数を割り出し、全部足すってやつ。」

char num_bits_array[0xffff + 1];

int count_bits(bitboard_t bb) {
  return num_bits_array[bb & 0xffff]
    + num_bits_array[(bb >> 16) & 0xffff]
    + num_bits_array[(bb >> 32) & 0xffff]
    + num_bits_array[(bb >> 48) & 0xffff];
}

Sayuri
「なんだか「マジックビットボード」を応用したようなやり方どすな。
ただ計算は簡単になりそうどすが、メモリアクセスがハンパないどす。
普通にメインメモリを使うとものすごく遅くなりそうどすな。」


「そのための「8bit 整数型」の配列。 サイズが小さいのでキャッシュに残る可能性が高くなる。
実際に試して「アルゴリズム的に最速」のやつより早くなったから、考え方はそんなに間違ってないと思う。
ただし CPU 依存。 モバイル系の CPU で高速化する自信はない。」

Sayuri
「あんさんの「高速化の工夫」は「無意味」なものがほとんどどすが、これは効果があったみたいどすな。
「下手な鉄砲数撃ちゃ当たる」どすか。 あんさんもガトリング砲の如く「オレオレ高速化」を連射すれば一発くらいは「かする」どすな。」


当たれよ。

ループの周回数の最小化

header_4


「チェスボードのマスの数は「64」マス、でもチェスの駒は最も多いときで「32」個しかない。
ボード上の駒の状態を調べるのにいちいち 64 マス分ループしていたら半分以上のサイクルが「無駄サイクル」ってことになる。
ましてや終盤に駒が 4、5個くらいになるとほぼ全て「無駄サイクル」になる。」

for (各マス) {
  if (マスに駒がある?) {
    各駒の処理...
  }
}

Sayuri
「つまり「ビットボード」を使えば 64マスループして駒の状態を調べる際、「駒のないマス」のサイクルは飛ばせると言いたいどすな。」


「そう。 で、どうすればそれを飛ばせるかと言うと・・・

for (bitboard_t bb = 駒のビットボード; bb; bb &= bb - 1) {
  各駒の処理...
}

・・・ってな感じ。
これで、もしボード上に駒が 10個しかなかったら 10サイクルしかループしないって感じになる。」

Sayuri
「手品みたいどすな。
ちなみに「マスの位置」はどうやって入手するどすか?」


「マスの位置の定数」「ビットボードのビットの位置」が同じ場合は、一つ前で紹介した「count_bits()」を使って・・・

square_t square = count_bits((bb & (-bb)) - 1);

・・・で取り出せる。」

Sayuri
「コードだけ見てたら、もはや何をやっているのか分からないどす。」


「とにかく、チェスボードを「ビットボード」で表現すればいろんなビット演算のアルゴリズムを使いまくれるってこと。」

最後に

Sayuri
「今回の記事のテーマは「マニアックな技術紹介でいかにプログラミング初心者の心をくじくか」どすな。」


「まるで僕が「大学の理系の授業に意気揚々と初出席した学生を、わずか 10分で挫折させる教授」みたいじゃないか。
僕も最初からこんなマニアックなテクニックが使えたわけじゃないよ。
初めてチェスエンジンを作った時は素直に「マスの配列」でボードを表現していた。
で、他のエンジンのコードに興味を持ち始めて、「GNU Chess」のコードを読んだ時に初めて「ビットボード」の存在を知ったって感じ。」

Sayuri
「そういやあんさんはスマホを持っていなかった当時、エンジンのコードの読みたい部分をプリントアウトして通勤電車で読みふけっていたどすな。
そういう、時と場所を考えない部分は「オタク丸出し」どす。 まるで「ラブライバー」どす。」


「まるでラブライバー」か・・・・・・はぁ、お前は「ラブライブ・サンシャイン」の素晴らしさを全く理解できていない。
今から説明してやるから耳の穴かっぽじってよーく聞くんだ。

Sayuri
「いやどす。 聞きたくないどす。 やめてくださいどす。


「先ず最も重要なのは「制服 × ミニスカート × 裸足」という「中年オヤジのフェティシズム」にド直球な作品のコンセプトだ。 僕の心はあれで完全にノックアウトされた。
そうしてファンになった後は・・・

  1. 「女性しかいない世界」「いい子しかいない世界」「きれいごとが通用する世界」という「美しい世界」に溺れる。
  2. 「現実の世界」が汚く醜く歪んで見え始める。
  3. 自分が美しき「ラブライブの世界」の住人じゃないことに「憂い」を感じ始める。

・・・そしてそこでファンは以下の 2つの選択肢を迫られることになる。

  • 「ラブライバー」となって少しでも「ラブライブの世界」に近づこうとする。
  • 現実に絶望し、自分の存在を後悔し、悲しみに暮れながら「ラブライブ」の記憶が薄れるのを待つ。

そして「ラブライバー」のようなポジティブな心を持てない僕は 2番目の選択肢を選ぶしかなかった・・・。」

Sayuri
良くて「ラブライバー」、悪くて「自己嫌悪」・・・・・・すごいアニメどすな。」

一同
「ってなわけで、次回も乞うご期待!」「どす。」