ビットボード

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

同じビットボード内のビットはゲームのルールによって互いに関連しており、多くの場合、まとめてゲームポジションを形成します。他のビットボードは、ポジションに関するクエリを変換したり回答したりするためのマスクとして一般的に使用されます。ビットボードは、ゲームボード上の離散的な空間における駒の状態、または駒の存在によって進行が表現されるあらゆるボードゲームに適用できます。この表現は、空間の状態をデータ構造内のビットにマッピングすることで実現されます。ビットボードは、従来のメールボックス表現（ボード上の各駒または空間が配列要素となる）よりも効率的な代替表現です。

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

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

説明

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

ビットボードの有効性は、実装上の他の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」（または「先頭の 0 を数える」）および「1 を数える」（または「0 を数える」）のハードウェア命令がない場合、これらの操作はアセンブリ言語のループとしてコード化するには非常に非効率であるため、実装は大幅に不利になります。

キャッシュとメモリの使用

長所

ビットボードは駒リスト型ボードデータ構造よりも多くのメモリを必要としますが、多くのループと比較演算が1つ（または少数）のビット演算に簡略化されるため、実行効率は向上します。例えば、メールボックスにおいて、駒がスペースを攻撃するかどうかを判断するには、駒の有効な移動を生成してループし、最終的なスペースとスペースを比較する必要があります。ビットボードでは、駒の有効な移動はビットマップに格納され、そのマップとスペースのビットマップの論理積が取られます。結果がゼロ以外の場合、駒はスペースを攻撃することを意味します。

短所

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

増分更新

チェスの攻撃マップのように、ある種のビットボードは、複雑な相互相関処理によって他のビットボードから派生します。ゲームの状態（例えば着手）が変化するたびにこれらのマップをすべて再構築するのは非常にコストがかかるため、派生したビットマップは段階的に更新されます。この処理には複雑で精密なコードが必要です。この方法は、盤上のすべてのビットマップではなく、変更されたマスに関連付けられたビットマップのみを変更する必要があるため、実行速度が大幅に向上します。段階的な更新がなければ、ビットマップ表現は、更新が本質的にローカルかつ段階的である従来のメールボックス表現よりも効率的ではない可能性があります。

事前計算されたビットマップとテーブル検索

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

チェスのビットボード

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

標準

代数記法

ビットボード表現では、64ビットワード（32ビットアーキテクチャではダブルワード）の各ビットがチェス盤のマス目に対応付けられます。ビットとマス目の対応付けは任意ですが、大まかな慣例により、ビットは左から右、下から上の順でマス目に対応付けられます。つまり、ビット0はマス目a1、ビット7はマス目h1、ビット56はマス目a8、ビット63はマス目h8を表します。

盤上の様々な配置は通常、それぞれ独自のビットボードで表現される。これにはキングの位置、白のみのポーンの位置、黒のみのポーンの位置、そして他の駒の種類や白のみの駒のような駒の組み合わせごとのビットボードが含まれる。2つの攻撃ビットボードも普遍的である。1つはマスごとに1つのビットボードで、そのマスを攻撃するすべての駒を表す。もう1つは、駒があるマスごとに、そのマスが攻撃するすべてのマスを表す逆ビットボードである。ビットボードは、1が最初のランクを表す定数でもあり、その場合は位置0 - 7に1のビットが入る。「敵の駒が攻撃するキングに隣接するすべてのマス」のような他のローカルまたは遷移的なビットボードは、必要に応じて、あるいは都合に応じて照合される。[ 1 ]

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

標準的なビットボードの欠点の一つは、スライディング駒（ルーク、ビショップ、クイーン）の攻撃ベクトルを照合することです。なぜなら、これらの駒は、他の駒の占有スペースに応じて攻撃スペースの数が不定だからです。そのため、駒ごとにマスク、シフト、補完という長いシーケンスを複数回実行する必要があります。

補助ビットボード表現

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

回転したビットボード

回転ビットボードは、滑駒攻撃ベクトルを表形式化できる補完的なビットボードデータ構造です。ルークのファイル攻撃ベクトルを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チェスエンジンの作者であるロバート・ハイアット教授によって1990年代半ばに発明され、Dark Thoughtプログラミングチームと共有されました。後にCraftyとDark Thoughtに実装されましたが、最初の説明が公開されたのは1997年でした。

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

その他のゲーム

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

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

参照

注記

  1. ^このメソッドの実装には完全なハッシュ関数の使用は必須ではなく、標準的なハッシュメソッドに比べてごくわずかな利点しかありません。

参考文献

  1. ^アトキン, ラリー・R.; スレート, デイビッド・J. (1983) [1977]. 「チェス4.5：ノースウェスタン大学チェスプログラム」. フレイ, ピーター・W. (編). 『人間と機械におけるチェスの技能』（第2版）.シュプリンガー出版社. pp.  82– 118. CiteSeerX  10.1.1.111.926 . ISBN 0-387-90790-4。
  2. ^ハインツ、エルンスト・A.（1997年9月）「ダーク・ソートのチェス戦略」 ICCAジャーナル20 ( 3): 166-176。
  3. ^ Hyatt, Robert (1999). 「回転ビットボード：古いアイデアの新たな展開」 2005年4月28日時点のオリジナルよりアーカイブ。
  4. ^ Tannous, Sam (2007-07-23) [2006]. 「直接参照による回転ビットボードの回避」. ICGAジャーナル. 30 (2) (第2版). ノースカロライナ州ダーラム: 85–91 . arXiv : 0704.3773v2 . CiteSeerX 10.1.1.561.3461 . doi : 10.3233/ICG-2007-30204 . 
  5. ^ Knuth, Donald (1973). 「セクション6.4. アルゴリズムD (二重ハッシュによるオープンアドレス指定)」. 『The Art of Computer Programming』第3巻.
  6. ^シャーウィン、マイケル、アイゼンバーグ、ゲルト (2006年12月4日). 「マジックビットボード解説！」 . Winboardフォーラム.幼稚園ビットボードとでも呼ぼう
  7. ^ハンセン、ラッセ (2006-06-14)。「高速なビットボード移動ジェネレーター」。ウィンボードフォーラム。。
  8. ^「チェッカーゲームを用いた機械学習に関するいくつかの研究」IBM研究開発ジャーナル、1959年。
  9. ^ Adel'Son-Vel'Skii, GM; Arlazarov, VL; Bitman, AR; Zhivotovskii, AA; Uskov, AV (1970). 「チェスをプレイするコンピュータのプログラミング」.ロシア数学概論. 25 (2): 221. Bibcode : 1970RuMaS..25..221A . doi : 10.1070/RM1970v025n02ABEH003792 .

さらに読む

電卓

チェッカーズ

チェス

記事

コード例

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

実装

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

オセロ

言葉遊び

「 https://en.wikipedia.org/w/index.php?title=Bitboard&oldid=1328223926」から取得