ビットボード

ビットボードは、ボードゲームをプレイするコンピュータ システムで一般的に使用される特殊なビット配列 データ構造で、各ビットはゲーム ボードのスペースまたは駒に対応します。これにより、並列ビット演算によってゲームの状態を設定または照会したり、ゲーム内の動きやプレイを決定したりできます。

同じビットボード内のビットは、ゲームのルールによって互いに関連しており、多くの場合、まとめてゲームの位置を形成します。他のビットボードは、位置に関するクエリを変換または回答するためのマスクとしてよく使用されます。ビットボードは、ゲームボードの個別のスペースの状態またはピースの存在によって進行が表されるゲームに適用できます。これは、スペースの状態をデータ構造内のビットにマッピングすることによって行われます。ビットボードは、従来のメールボックス表現よりも効率的な代替ボード表現であり、ボード上の各ピースまたはスペースは配列要素です。

ビットボードは、ボード上のさまざまな関連状態の関連ビットが CPU アーキテクチャの単一ワードまたはダブルワードに収まる場合に特に効果的です。これにより、AND や OR などの単一ビット演算子を使用して、ゲーム状態を構築または照会できます。

ビットボードを使用するコンピュータゲームの実装には、チェス、チェッカー、オセロ、ワードゲームなどがあります。この方式は、1950年代にチェッカープログラムで初めて採用され、1970年代半ば以降はコンピュータオートマトンにおけるゲームボード表現の事実上の標準となっています。

ビットボードは特殊なビット フィールドで、複数の関連するブール変数を同じマシン ワードにパックする形式であり、通常はボード ゲーム上の位置またはゲームの状態を表します。各ビットはスペースを表します。ビットが正の場合、そのスペースのプロパティは true です。ビットボードを使用すると、コンピューターは 1 つのビット演算でゲームの状態に関するいくつかの質問に答えることができます。たとえば、チェス プログラムが白のプレーヤーがボードの中央 (中央の 4 つのマス) にポーンを持っているかどうかを知りたい場合は、ビット AND 演算を使用して、プレーヤーのポーンのビットボードとボードの中央のビットボードを比較するだけです。中央のポーンがない場合、結果はすべてゼロ ビット (つまり、ゼロに等しい) になります。複数のビットボードがボード上のスペースのさまざまなプロパティを表す場合があり、特殊または一時的なビットボード (一時変数など) がローカル プロパティを表したり、中間の照合結果を保持したりする場合があります。

ビットボードの有効性は、実装の他の 2 つの特性によって強化されます。まず、ビットボードは、駒が移動されたときに駒の位置を示すビットボードのソース位置と宛先位置のビットを反転するなど、段階的に高速に更新されます。次に、チェス盤上のすべての位置で各駒の種類によって攻撃されるすべてのスペースなどの静的プロパティを表すビットマップを事前に照合してテーブルに格納できるため、「スペース e4 でのナイトの正当な動きは何ですか?」などの質問に、1 回のメモリ フェッチで回答できます。

ビットフィールドの実装では、最新の CPU アーキテクチャ上の AND、OR、NOT などのフルワード (32 ビットまたは 64 ビット) ビット単位の論理演算を利用して効率化を図っています。ビットボードは、以前の 8 ビットおよび 16 ビットのミニコンピュータやマイクロプロセッサ アーキテクチャでは効果がない可能性があります。

膨大なテーブルの内容を圧縮してエンコードする必要があり、転写やエンコード エラーが発生する可能性もあるため、ソフトウェア開発者にとって、ビットボード プログラムの作成やデバッグは面倒です。通常、テーブルを構築するには、アプリケーションの一部ではない補助的な生成方法が必要です。

ビットボード表現は、ほぼすべてのCPUで利用可能な並列ビット単位演算を使用します。これらの演算は1 サイクルで完了し、完全にパイプライン化され、キャッシュされます。ほぼすべての CPU には、AND、OR、NOR、およびXOR があります。さらに、最新の CPU には、実行のために命令をキューに入れる命令パイプラインがあります。複数の実行ユニットを持つプロセッサは、パイプラインで複数の命令が使用可能な場合、1 サイクルあたり複数の命令を実行できます。分岐を含む通常の命令シーケンスでは、分岐が誤って予測された場合にパイプラインが空になることがあります。多くのビットボード演算では条件文が少なくて済むため、パイプラインが増加し、多くの CPU で複数の実行ユニットを効果的に使用できます。

CPU には、設計上のビット幅があり、この幅で 1 サイクルでビット単位の演算を実行できます。したがって、64 ビット以上の CPU では、64 ビットの演算を 1 つの命令で実行できます。より幅の広い命令や狭い命令がサポートされている場合もあります。多くの 32 ビット CPU には 64 ビット命令がいくつかある場合があり、それらの命令は 1 サイクル以上かかるか、32 ビット命令に比べて不利になる場合があります。

ビットボードが命令セットの幅より大きい場合、全幅の操作を実行するには複数の命令が必要になります。そのため、64 ビット ビットボードを使用するプログラムは、32 ビット プロセッサよりも 64 ビット プロセッサでより高速に実行されます。

ビットボード表現には、ソース コードとオブジェクト コードの両方で、はるかに長いコードがあります。長いビット ツイドリング シーケンスは、技術的に記述およびデバッグするのが難しいです。ビットボード自体はまばらで、64 ビットのうち 1 ビットしか含まれないこともあるため、ビットボードの実装はメモリを大量に消費します。これらの問題は両方とも、キャッシュ ミスの増加やキャッシュ スラッシングの原因となる可能性があります。

プロセッサに「最初の 1」（または「先頭のゼロを数える」）および「1 を数える」（または「ゼロを数える」）のハードウェア命令がない場合、これらの操作はアセンブリ言語のループとしてコード化するには非常に非効率であるため、実装は大幅に制限されます。

ビットボードは、駒リスト ボード データ構造よりも多くのメモリを必要としますが、多くのループおよび比較操作が 1 つの (または少数の) ビット単位の操作に削減されるため、実行効率が高くなります。たとえば、メールボックスで駒がスペースを攻撃するかどうかを判断するには、駒の正当な動きを生成してループし、最終的なスペースをスペースと比較する必要があります。ビットボードでは、駒の正当な動きはビットマップに格納され、そのマップはスペースのビットマップと AND 演算されます。結果がゼロ以外の場合、駒がスペースを攻撃することを意味します。

一部のゲームでは、ビットボード エンジンの作成に、コンパクトなメールボックス/列挙実装よりも長くなるデータ テーブルを含む、かなりの量のソース コードが必要です。レジスタやプロセッサ命令キャッシュの数が限られているモバイル デバイス (携帯電話など) では、これが問題になることがあります。フルサイズのコンピューターでは、レベル 1 キャッシュとレベル 2 キャッシュの間でキャッシュ ミスが発生する可能性があります。これは潜在的な問題にすぎず、大きな欠点ではありません。ほとんどのマシンには、これが問題にならないだけの十分な命令キャッシュが搭載されているからです。

ビットボードの種類によっては、チェスの攻撃マップのように、相互相関の複雑なプロセスによって他のビットボードから派生します。ゲームの状態が変化するたびに (移動など) これらすべてのマップを再作成するのは非常にコストがかかるため、派生したビットマップは増分更新されます。このプロセスには複雑で正確なコードが必要です。ボード上のすべてのビットマップではなく、変更されたスペースに関連付けられたビットマップのみを変更する必要があるため、この方法の方がはるかに高速に実行できます。増分更新がなければ、ビットマップ表現は、更新が本質的にローカルで増分的である古いメールボックス表現よりも効率的ではない可能性があります。

ボードの構成に依存しないビットマップの種類によっては、ボードの移動または状態の変化後に照合するのではなく、テーブル検索によって事前に計算して取得することができます。たとえば、チェス盤の 64 個のスペースのそれぞれにあるナイトまたはキングが攻撃するスペースなど、通常は列挙が必要となるスペースです。

チェス盤上の駒の配置を最もわかりやすく簡単に表現する方法は、駒を便利な検索順 (値の小さい順など) に並べたリスト (配列) で、各駒を盤上の位置にマップすることです。同様に、各駒が攻撃するスペースを照合するには、駒ごとにそのようなスペースを連続的に列挙する必要があります。この方式は、メールボックス アドレス指定と呼ばれます。白と黒の駒、および多くの場合、白と黒のポーンごとに別々のリストが維持されます。マップは各移動ごとに更新され、駒リストの線形検索 (駒が捕獲された場合は 2 回) が必要になります。 メールボックスの利点はコードが簡単なことですが、欠点は線形検索が遅いことです。駒を位置にマップする、より高速でより複雑なデータ構造は、ビットボードと呼ばれます。

ビットボード表現では、64 ビット ワード (または 32 ビット アーキテクチャではダブル ワード) の各ビットがチェス盤のマス目に関連付けられます。ビットとマス目のマッピングは任意に使用できますが、一般的な慣例により、ビットは左から右、下から上のマス目に関連付けられます。つまり、ビット 0 はマス目 a1、ビット 7 はマス目 h1、ビット 56 はマス目 a8、ビット 63 はマス目 h8 を表します。

盤面のさまざまな構成は、通常、キングの位置、すべて白のポーン、すべて黒のポーン、および他の駒の種類やすべて白の駒などの駒の組み合わせのビットボードを含む独自のビットボードで表されます。 2 つの攻撃ビットボードも普遍的です。1 つはマスごとに 1 つのビットボードで、マスを攻撃するすべての駒を表します。もう 1 つは、駒が含まれるマスごとに、駒が攻撃するすべてのマスを表します。 ビットボードは、1 位を表す定数にすることもできます。1 位の場合は、位置 0 - 7 に 1 つのビットがあります。 「敵の駒が攻撃するキングに隣接するすべてのマス」などの他のローカルまたは遷移ビットボードは、必要に応じてまたは都合に応じて照合できます。^[1]

ビットボードの使用例としては、駒がen prise であるかどうかを判断することが挙げられます。 「スペースを守っているすべての味方の駒」と「スペースを攻撃しているすべての敵の駒」のビットボードを使用すると、ピースを一致させて、スペース上のターゲットの駒がen priseであるかどうかを簡単に判断できます。

標準ビットボードの欠点の 1 つは、スライディング ピース (ルーク、ビショップ、クイーン) の攻撃ベクトルを照合することです。これは、他の占有スペースに応じて攻撃スペースの数が不定になるためです。これには、ピースごとにマスク、シフト、および補完の長いシーケンスがいくつか必要になります。

スライディング ピースの攻撃ベクトルのビットボードを生成するためのコード サイズと計算の複雑さを考慮して、それらを照合するための代替ビットボード データ構造が考案されました。ナイト、キング、ポーン、その他のボード構成のビットボード表現は、スライディング ピースの補助ビットボードの使用による影響を受けません。

回転ビットボードは、スライディング ピースの攻撃ベクトルを表形式にできる補完的なビットボード データ構造です。1 つはルークのファイル攻撃ベクトル用、もう 1 つはビショップの対角および反対角攻撃ベクトル用です (ルークのランク攻撃は標準ビットボードからインデックスできます)。これらのビットボードを使用すると、1 回のテーブル参照で長いビット単位の演算シーケンスを置き換えることができます。

これらのビットボードは、ボードの占有構成を 90 度、45 度、および/または 315 度回転します。標準のビットボードは、チェス ボードのランクごとに 1 バイトを持ちます。このビットボードを使用すると、占有されているマス目とランク内の占有位置でインデックス付けされたテーブルを使用して、ランク全体のルークの攻撃を簡単に判断できます (ルークの攻撃は最初の占有マス目で停止するため)。ビットボードを 90 度回転すると、ファイルの上下のルークの攻撃を同じ方法で調べることができます。45 度と 315 度 (-45 度) 回転したビットボードを追加すると、対角線を調べやすいビットボードが作成されます。クイーンは、ルークとビショップの攻撃を組み合わせることで調べることができます。実際にビットボードを回転することは、数十の命令を必要とする、エレガントでない変換です。^{[2] [3]}

ルークのランクとファイル攻撃ベクトルとビショップの対角および反対角攻撃ベクトルは別々にマスクされ、占有率に応じて事前計算された攻撃ベクトルのハッシュテーブルへのインデックスとして使用できます。ルークの場合はそれぞれ 8 ビット、ビショップの場合はそれぞれ 2 ～ 8 ビットです。駒の完全な攻撃ベクトルは、ハッシュテーブルからインデックスされた 2 つの一方向ベクトルのそれぞれの和集合として取得されます。ハッシュテーブルのエントリ数は 8*2^8 または 2K バイト程度と控えめですが、駒ごとに 2 回のハッシュ関数計算と 2 回のルックアップが必要です。^[4]使用されているハッシュスキームを参照してください。^[5]

マジック ビットボードは、攻撃ベクトルを直接ハッシュ検索する際の時間と空間のトレードオフを推定したものです。これらは、ハッシュ テーブルへのインデックスとして、完全な攻撃ベクトルの変換を使用します。 マジックというのは誤った呼び方で、単に、メモリに格納する必要があるハッシュ テーブルの潜在的なサイズ (8*2^64 または 144エクサバイト)を削減するためのトリックと組み合わせて、完全なハッシュ関数を生成して使用することを指します。^{[注 1]} 最初の観察結果は、外側の正方形または 1 番目と 8 番目のランク、および 'a' ファイルと 'h' ファイルが攻撃ベクトルの占有とは無関係であるということです。占有に関係なく、ピースがそれらの正方形を攻撃するかどうかは (他のブロック ピースに応じて) 決まるため、これらを考慮から除外して、6x6 または 36 個の正方形 (対応するハッシュ関数の ~ ビット) だけ残すことができます。完全なハッシュ関数を必要とする他の方式と同様に、ハッシュ関数を生成するには、部分的にアルゴリズム的かつ部分的に試行錯誤的な列挙の徹底的なプロセスが必要です。しかし、解決困難な問題が残っています。これらは非常にアクティブなテーブルであり、そのサイズ (ほとんどの場合、100 万エントリ未満) は、最新のチップ アーキテクチャの低レベル キャッシュ サイズに比べて非常に大きいため、キャッシュ フラッディングが発生します。そのため、多くのアプリケーションでは、マジック ビットボードは、より控えめなハッシュ スキームやローテーション ビットボードに比べてパフォーマンスの向上をもたらしません。^{[6] [7]}

ボードゲームを表現するビットボード方式は、1950年代半ばにアーサー・サミュエルによって発明され、彼のチェッカープログラムで使用されたようです。^[8] より複雑なチェスゲームについては、この方式は1960年代後半にソ連のカイサチームによって独立して再発見され、^[9] 1970年代初頭には米国ノースウェスタン大学のプログラム「チェス」の作者によっても再発見されました。1970年代のアムダールやクレイマシンなどのスーパーコンピューターの64ビットワード長により、チェス盤の64マスをワードのビットに便利にマッピングするビットボード表現の開発が促進されました。

スライドする駒の動きを照合するための回転ビットボードは、Cray Blitz および Crafty チェス エンジンの作者である Robert Hyatt 教授によって 1990 年代半ばに発明され、Dark Thought プログラミング チームと共有されました。後に Crafty および Dark Thought に実装されましたが、最初の説明が公開されたのは 1997 年になってからでした。

10 年後、マスクされたランク、ファイル、および対角線を使用して、マスクの下のビットの占有状態に応じて攻撃ベクトルのテーブルをインデックスする直接検索方法が導入されました。ハッシュ衝突を排除するために完全ハッシュ関数を使用するこのようなスキームの 1 つは、「マジック ビットボード」と呼ばれていました。ただし、このようなテーブルはサイズが大きくアクセス率が高いため、メモリ占有とキャッシュ競合の問題が発生するため、必ずしもローテーション ビットボード アプローチよりも効果的ではありませんでした。今日、ゲーム プログラムは分割されたままであり、最適なスキームはアプリケーションによって異なります。

チェス以外にも多くのゲームがビットボードの恩恵を受けています。

• Connect Fourでは、方向ごとに 2 つの shift + AND 演算を実行するだけで、連続する 4 つのディスクを非常に効率的にテストできます。
• Conway のライフゲームでは、配列の代替として使用できます。
• オセロ/リバーシ (リバーシの記事を参照)。

• ボード表現（チェス）

• http://people.csail.mit.edu/heinz/dt/node2.html

• 64ビットの表現と操作

• チェッカーズ Bitboard チュートリアル (Jonathan Kreuzer 著)

• ビットボード - チェスプログラミング wiki
• Beowulfプロジェクトのプログラミング領域
• Laramee, Francois-Dominic. チェス プログラミング パート 2: データ構造。
• フェルヘルスト、ポール。チェス盤の表現
• ハイアット、ロバート。チェスプログラムボードの表現
• フレイン、コリン。チェス エンジンでビットボードを実装する方法 (チェス プログラミング理論)
• Pepicelli, Glen. ビットフィールド、ビットボード、そしてその先 - (Java 言語のビットボードの例と、この最適化が Java 仮想マシンで機能する理由の説明 (www.OnJava.com 発行元: O'Reilly 2005))
• コンピューターチェスにおけるマジックムーブビットボード生成。Pradyumna Kannan

• [1] Frenzeeエンジンの作者はいくつかのソース例を投稿していました。
• [2] ビットボードの使い方を示す155行のJava Connect-4プログラム。

• Beowulf Unix、Linux、Windows。回転したビットボード。
• Crafty Crafty の記事を参照してください。純粋な C で書かれています。古いバージョンではビットボードが回転していましたが、現在はマジック ビットボードを使用しています。
• GNU チェス GNU チェスの記事を参照してください。
• Stockfish UCI チェス エンジンは、2010 年現在 Elo で 2 位にランクされています。
• Gray Matter C++、回転したビットボード。
• KnightCap GPL。ELO 2300。
• Pepito C. Bitboard、Carlos del Cacho 著。Windows および Linux バイナリとソースが利用可能です。
• Simontacci 回転ビットボード。

• DarkThought ホームページ

• C およびアセンブリの Othello ビットボードを含むソース コードを含む、 Othello ( Reversi ) エンジンの完全な説明。
• Edax (コンピューティング) Edax の記事を参照してください。ビットボードに基づいたソースコードを備えたオセロ (リバーシ) エンジン。

• 単語ゲームにおけるビットボードの使用の概要。