Loading article…
ビットボードとは、ボードゲームをプレイするコンピュータシステムで一般的に使用される、特殊なビット配列データ構造であり、各ビットがゲーム盤のマス目または駒に対応する。
この手法は、チェス、チェッカー、オセロ、ワードゲームなど、ゲームの状態がゲーム盤上の個別のマス目に配置された駒によって表現されるあらゆるボードゲームに適用可能です。1950年代にチェッカーのプログラムで初めて採用され、1970年代半ば以降、コンピュータによるゲーム盤表現の事実上の標準となっています。
従来のメールボックス表現では、盤上の各駒やマス目が配列の要素として扱われるのに対し、ビットボードはよりスペース効率の良い盤面表現である。
ビットボードは、多くの場合、処理時間も効率的です。ビットボード上の関連する状態の関連ビットがCPUアーキテクチャの1ワードまたは2ワードに収まる場合、ANDやORなどの単一のビット演算子を使用してビットボードを操作できます。これらの並列ビット演算は、メールボックス表現に対して反復的な配列演算を実行するよりも、ゲーム状態の設定や照会、ゲーム内の動きやプレイの決定において、はるかに高速になります。
現代のチェスエンジンは主にマジックビットボードを利用しており、これはパーフェクトハッシュを用いて、駒の占有マスクを、事前に計算された攻撃パターンの配列に単一の検索操作で直接マッピングする。
ビットボードとは、特殊なビットフィールドのことで、複数のブール変数を同じマシンワードに詰め込むことで、ボードゲームの状態を表すフォーマットです。各ビットは空間を表し、ビットが正の値をとると、その空間の特性が真となります。
ビットボードを使うことで、コンピュータはごく少数のビット演算でゲームの状態に関する質問に答えることができます。例えば、チェスプログラムが白のプレイヤーが盤面中央（中央の4マス）にポーンを持っているかどうかを知りたい場合、プレイヤーのポーンを表すビットボードと盤面中央を表すビットボードをビットごとのAND演算で比較するだけで済みます。中央にポーンがない場合は、結果はすべてゼロビット（つまりゼロ）になります。複数のビットボードは盤面上のさまざまなマスの異なる特性を表すことができ、特別なビットボードや一時的なビットボード（一時変数など）は、ローカルな特性を表したり、中間的な集計結果を保持したりすることができます。
ビットボードの有効性は、実装の他の2つの特性によってさらに強化されます。まず、ビットボードは増分更新が高速です。例えば、駒が移動した際に、駒の位置を示すビットボードの始点と終点の位置のビットを反転させるだけで済みます。次に、チェス盤上の各位置における各駒の種類が攻撃するすべてのマスなど、静的な特性を表すビットマップを事前に収集し、テーブルに格納することができます。これにより、「e4マスにいるナイトの合法的な動きは何か？」といった質問に、1回のメモリフェッチで答えることが可能になります。
ビットボードの実装では、最新のCPUアーキテクチャに搭載されているAND、OR、NOTなどのフルワード（32ビットまたは64ビット）ビット単位の論理演算を利用して、高速な演算を実現しています。そのため、8ビットや16ビットといった旧世代のミニコンピュータやマイクロプロセッサでは、ビットボードの有効性は劣る可能性があります。
ビットボードの実装には、膨大なテーブルと複雑なゲーム状態の適切な圧縮とエンコードが必要となるため、ソフトウェア開発者にとってビットボードプログラムの作成とデバッグは面倒な作業となる可能性がある。
ビットボード表現は、ほぼすべてのCPUで利用可能な並列ビット演算を使用し、1サイクルで完了します。これらの演算は、パイプライン化とキャッシュ化が完全であること、およびその他のCPU固有の最適化により、通常、最も高速な命令の一つです。ほぼすべてのCPUには、AND、OR、NOR、およびXOR演算があります。さらに、最新のCPUには、実行のために命令をキューに入れる命令パイプラインがあります。複数の実行ユニットを持つプロセッサは、パイプラインに複数の命令が利用可能な場合、1サイクルあたり複数の命令を実行できます。分岐を含む通常の命令シーケンスでは、分岐が誤って予測された場合、パイプラインが空になる可能性があります。多くのビットボード演算では条件分岐が少なくて済むため、パイプライン化が進み、多くのCPUで複数の実行ユニットを効果的に利用できます。
CPUにはビット幅があり、これは1サイクルで実行可能なビット演算の数です。64ビット以上のCPUでは、1つの命令で64ビット演算を実行できます。ビット幅がより大きい、または小さい命令もサポートされている場合があります。多くの32ビットCPUには64ビット命令が含まれている場合があり、それらの命令は1サイクル以上かかるか、32ビット命令に比べて何らかの制約を受ける可能性があります。
ビットボードが命令セットの幅よりも大きい場合、全幅演算を実行するには複数の命令が必要になります。したがって、64ビットビットボードを使用するプログラムは、32ビットプロセッサよりも64ビットプロセッサの方が高速に動作します。
ビットボード表現は、ソースコードとオブジェクトコードの両方において、はるかに長いコード量を必要とします。長いビット操作シーケンスは、技術的に記述とデバッグが困難です。この問題は、キャッシュミスの増加やキャッシュスラッシングを引き起こす可能性があります。
プロセッサに「最初の1」（または「先頭のゼロを数える」）と「1を数える」（または「ゼロを数える」）のハードウェア命令がない場合、これらの操作をループやその他の高レベルな構造としてコーディングするのは非常に非効率的であるため、実装は著しく制限されます。
ビットボードはピースリストのボードデータ構造よりも多くのメモリを必要としますが、多くのループ比較操作が1つ（または少数）のビット演算に削減されるため、実行効率が高くなります。たとえば、mailboxでは、ピースがスペースを攻撃するかどうかを判断するには、ピースの合法的な動きを生成してループし、最終的なスペースをスペースと比較する必要があります。ビットボードでは、ピースの合法的な動きはビットマップに格納され、そのマップがスペースのビットマップとAND演算されます。結果がゼロ以外であれば、ピースがスペースを攻撃していることを意味します。
ゲームによっては、ビットボードエンジンを実装するには、コンパクトなメールボックス/列挙実装よりも長いデータテーブルを含む、かなりの量のソースコードが必要になります。これは、レジスタ数やプロセッサ命令キャッシュが限られているモバイルデバイス（携帯電話など）では問題となる可能性があります。フルサイズのコンピュータでは、レベル1キャッシュとレベル2キャッシュの間でキャッシュミスが発生する可能性があります。これは潜在的な問題であり、大きな欠点ではありません。ほとんどのマシンは、この問題を解消するのに十分な命令キャッシュを備えているからです。
チェスの攻撃マップのように、一部のビットボードは、複雑な相互相関処理によって他のビットボードから派生します。ゲームの状態（例えば、駒の移動）が変化するたびにこれらのマップをすべて再構築するのは非常にコストがかかるため、派生ビットマップは段階的に更新されます。このプロセスには、複雑かつ正確なコードが必要です。この方法は、盤面全体のビットマップではなく、変更されたマスに関連付けられたビットマップのみを変更すればよいため、実行速度が大幅に向上します。段階的な更新を行わない場合、ビットマップ表現は、更新が本質的に局所的かつ段階的な従来のメールボックス表現よりも効率的ではない可能性があります。
盤面構成に依存しない種類のビットマップは、事前に計算しておき、盤面の動きや状態変化の後に照合するのではなく、テーブル参照によって取得することができます。例えば、チェス盤の64マスそれぞれにある、ナイトやキングが攻撃するマスなどがこれに該当し、そうでなければ列挙が必要になります。
チェス盤上の駒の配置を最も分かりやすく、かつ単純に表現する方法は、駒を一覧表（配列）にし、各駒を盤上の位置にマッピングし、検索しやすい順序（例えば、値の小さい順から大きい順）で並べることです。同様に、各駒が攻撃するマス目を把握するには、その駒が攻撃するマス目を順番に列挙する必要があります。この方式はメールボックス方式と呼ばれます。白と黒の駒、そして多くの場合、白と黒のポーンについても、それぞれ別のリストが保持されます。マップは各手ごとに更新され、駒のリストに対して線形検索（駒が取られた場合は2回）が必要となります。メールボックス方式の利点はコードがシンプルであること、欠点は線形検索が遅いことです。ビットボード方式は高速ですが、より複雑です。
ビットボード表現では、64ビットワード（32ビットアーキテクチャではダブルワード）の各ビットがチェス盤のマス目に対応付けられます。ビットとマス目の対応付けは任意ですが、一般的な慣例として、ビットは左から右、下から上の順にマス目に対応付けられます。つまり、ビット0はマス目a1、ビット7はマス目h1、ビット56はマス目a8、ビット63はマス目h8を表します。
盤面のさまざまな構成は、キングの位置、すべての白ポーン、すべての黒ポーンの位置、およびすべての白駒など、他の駒の種類や駒の組み合わせごとにビットボードで表現されることがよくあります。2 つの攻撃ビットボードも普遍的です。1 つのビットボードは、そのマスを攻撃するすべての駒を表します。もう 1 つのビットボードは、駒があるマスごとに、その駒によって攻撃されるすべてのマスを表します。ビットボードは定数にもなり得ます。たとえば、1 段目を表すビットボードは、位置 0 ～ 7 に 1 つのビットを持ちます。必要に応じて、または都合の良いときに、「キングに隣接するすべてのマスが相手の駒によって攻撃されている」などの他のローカルまたは遷移ビットボードをまとめることができます。[ 1 ]
ビットボードの使用例としては、駒が占領されているかどうかを判断することが挙げられます。「スペースを守るすべての味方の駒」と「スペースを攻撃するすべての敵の駒」のビットボードを使用することで、駒を照合して、スペース上のターゲットの駒が占領されているかどうかを簡単に判断できます。
標準的なビットボードの欠点の1つは、移動可能な駒（ルーク、ビショップ、クイーン）の攻撃ベクトルを照合することです。なぜなら、これらの駒は他の駒の占有状況に応じて攻撃可能な空間が不定となるからです。そのため、各駒ごとにマスク、シフト、補数といった一連の操作を何度も繰り返す必要があります。
チェスの駒（ルーク、ビショップ、クイーン）の場合、有効な攻撃を決定するには、その駒から伸びる特定の光線に沿って他の駒の動きを妨害する必要があるため、計算が複雑になります。
スライドする駒の攻撃ベクトルに対応するビットボードを生成する際のコードサイズと計算複雑度を相殺するために、代替のビットボードデータ構造が考案された。ナイト、キング、ポーン、その他の盤面構成のビットボード表現は、スライドする駒に補助ビットボードを使用しても影響を受けない。
回転ビットボードは、スライディングピース攻撃ベクトル、ルークのファイル攻撃ベクトル、ビショップの対角線および反対角線攻撃ベクトルをそれぞれ表形式で表化できる、補完的なビットボードデータ構造です（ルークのランク攻撃は標準ビットボードからインデックス付けできます）。これらのビットボードを使用すると、長いビット演算のシーケンスを単一のテーブル参照に置き換えることができます。
これらのビットボードは、盤上の占有構成を 90 度、45 度、および/または 315 度回転させます。標準のビットボードは、チェス盤の各ランクに 1 バイトが割り当てられています。このビットボードを使用すると、占有されたマスとランク内の占有位置でインデックス付けされたテーブルを使用して、ランクを横切るルーク攻撃を簡単に判断できます (ルーク攻撃は最初に占有されたマスで停止するため)。ビットボードを 90 度回転させると、ファイルの上下方向のルーク攻撃を同じ方法で調べることができます。45 度と 315 度 (-45 度) 回転したビットボードには、ビショップ攻撃を判断するために簡単に調べられる対角線があります。クイーンは、ルークとビショップの攻撃を組み合わせることで調べることができます。ただし、ビットボードの回転は、数十 の命令が必要になる場合がある、洗練されていない変換です。[ 2 ] [ 3 ]
ルークとビショップの攻撃ベクトルは個別にマスクされ、占有状況に応じて事前に計算された攻撃ベクトルのハッシュテーブルへのインデックスとして使用できます。ルークの場合はそれぞれ8ビット、ビショップの場合はそれぞれ2～8ビットです。駒の完全な攻撃ベクトルは、ハッシュテーブルからインデックス付けされた2つの単方向ベクトルの和集合として得られます。ハッシュテーブルのエントリ数は控えめで、オーダーはバイト、つまり約2キロバイト。ハッシュ方式では、1ピースあたり2回のハッシュ関数計算と2回のルックアップが必要です。[ 4 ] [ 5 ]
初期のチェスエンジンはレイキャスティングループ、回転ビットボード、または直接ハッシュを使用していたが、現代のチェスエンジンは主にマジックビットボードを利用している。この技術はパーフェクトハッシュを用いて、駒の占有マスクを、事前に計算された攻撃パターンの配列に単一のルックアップ操作で直接マッピングする。
マジックビットボードは、攻撃ベクトルの直接ハッシュルックアップの時間と空間のトレードオフを拡張したものです。これらは、完全な攻撃ベクトルの変換をハッシュテーブルへのインデックスとして使用します。マジックという用語は誤称であり、単に完全なハッシュ関数の生成と使用を、メモリに格納する必要のあるハッシュテーブルの潜在的なサイズを削減するためのトリックと組み合わせて使用することを指します。バイト、または144エクサバイト。[ nb 1 ]
外側のマス目、つまり「a」ファイルと「h」ファイルを含む第1ランクと第8ランクは、攻撃ベクトルの占有とは無関係です。ピースは占有に関係なく（他のブロックピースに応じて）これらのマス目を攻撃するかしないかを決定するため、これらは考慮から除外でき、6x6または36個のマス目（対応するハッシュ関数の~ビット）だけが残ります。
攻撃指数与えられた正方形の面積は、次の式を使用して計算されます。 どこ関連するスライダーの光線上のブロックピースを表す 64 ビット占有ビットボードは、は、平方数専用の64ビット「マジック乗数」であり、は、その特定の正方形の攻撃ルックアップテーブルをインデックス化するために必要なビット数です。結果として得られるビット単位のシフトにより、乗算の最上位ビットが分離され、高速ルックアップのための衝突のないインデックスが作成されます。[ 6 ]
完全なハッシュ関数を必要とする他の方式と同様に、ハッシュ関数を生成するには、アルゴリズムと試行錯誤を組み合わせた、網羅的な列挙プロセスが必要です。マジックビットボードは非常にアクティブなテーブルでもあり、そのサイズ（ほとんどの場合100万エントリ未満）は、最新のチップアーキテクチャの下位レベルのキャッシュサイズに比べて非常に大きいため、キャッシュフラッディングが発生します。多くのアプリケーションでは、マジックビットボードは、より控えめなハッシュ方式や回転ビットボードに比べてパフォーマンスの向上をもたらしません。[ 7 ] [ 8 ]
BMI2 (Bit Manipulation Instruction Set 2) アーキテクチャをサポートする最新の x86-64 プロセッサでは、チェスのスライディングピース攻撃の計算をハードウェアで直接高速化できるため、マジック乗数ハッシュは不要になります。このアプローチでは、並列ビット抽出 ( _pext_u64) および並列ビット格納 ( _pdep_u64) アセンブリ命令を利用します。このPEXT命令は、事前に計算されたブロッカーマスクを使用して、関連する占有ビットを連続したゼロ拡張インデックスに直接抽出します。このインデックスは、攻撃マップの瞬時配列ルックアップを実行するために使用され、CPU レジスタの使用を最適化し、より大きなマジックルックアップテーブルに関連する潜在的なキャッシュミスを排除します。[ 9 ]
ボードゲームを表現するためのビットボード方式は、1950年代半ばにチェッカープログラムで使用したアーサー・サミュエルに帰属する。 [ 10 ] より複雑なチェスについては、この方式は1960年代後半にソビエト連邦のカイッサチーム[ 11 ]と、1970年代初頭に米国ノースウェスタン大学のプログラム「チェス」の作者の両方に帰属する。アムダールやクレイマシンなどの1970年代のスーパーコンピュータの64ビットワード長は、チェス盤の64マスをワードのビットに都合よくマッピングするビットボード表現の開発を容易にした。
駒の動きを整理するための回転ビットボードは、 Cray BlitzとCraftyチェスエンジンの開発者であるロバート・ハイアット教授によって1990年代半ばに考案され、Dark Thoughtプログラミングチームに共有されました。その後、CraftyとDark Thoughtに実装されましたが、初めて公開されたのは1997年のことでした。
10年後、マスクされたランク、ファイル、対角線を使用して、マスク下のビットの占有状態に応じて攻撃ベクトルのテーブルをインデックス化する直接ルックアップ方式が導入された。ハッシュ衝突を排除するために完全なハッシュ関数を利用するそのような方式の1つは、「マジックビットボード」と呼ばれた。しかし、そのようなテーブルのサイズが大きくアクセス頻度が高いため、メモリ占有とキャッシュ競合の問題が発生し、回転ビットボード方式よりも必ずしも効果的ではなかった。2026年現在、ゲームプログラムでは依然として意見が分かれており、最適な方式はアプリケーションによって異なる。
チェス以外にも、多くのゲームがビットボードの恩恵を受けている。
幼稚園向けビットボードと呼ぼう
