ボード表現（コンピュータチェス）

コンピュータチェスのボード表現は、チェス盤上の位置と関連するゲーム状態を表すチェス プログラムのデータ構造です。 ^[1] ボード表現は、動きの生成、評価機能、動きの作成と取り消し (つまり検索)、およびプレイ中のゲーム状態の維持など、チェス プログラムのすべての側面の基本です。いくつかの異なるボード表現が存在します。チェス プログラムは、効率性を高めるために、異なるタイミングで複数のボード表現を使用することがよくあります。実行効率とメモリ フットプリントは、ボード表現を選択する際の主な要素です。次に考慮すべきことは、アプリケーションのコーディング、テスト、デバッグに必要な労力です。

初期のプログラムでは、配列ベースのピース リストとスクエア リストが使用されていました。最近の実装のほとんどは、64 ビット ワードまたはダブル ワードのビットをボードのスクエアにマップする、より複雑で効率的なビット配列アプローチであるビットボードを使用しています。

チェスの位置、つまり位置の「状態」の完全な説明には、次の要素が含まれている必要があります。

• 盤上の各駒の位置
• 誰が動く番か
• 50 手引き分けルールのステータス。このルールの名前は、各プレイヤーが 50 手ずつ、つまり 100 の半手、つまりプライであるため、少しわかりにくい場合があります。たとえば、前の 80 の半手で捕獲やポーンの動きがなかった場合、さらに 20 の半手が経過すると、50 手ルールが適用されます。
• どちらかのプレイヤーが、キングサイドとクイーンサイドの両方でキャスリングを永久に失格するかどうか。
• アンパッサント捕獲が可能であれば。

ボードの表現には通常、 3 倍の繰り返し 引き分けルールの状態は含まれません。このルールを決定するには、最後の不可逆なアクション (キャプチャ、ポーンの移動、キャスリング) からのゲームの完全な履歴を維持する必要があり、通常は別のデータ構造で追跡されます。この情報がなければ、モデルは勝利の優位性があるにもかかわらずポジションを繰り返し、過剰な引き分けが発生する可能性があります。^[2]

ボードの状態には、どの駒がマス目を攻撃しているか、駒があるマス目の場合、どのスペースがその駒によって攻撃または守られているか、どの駒が固定されているか、その他の便利な状態または一時的な状態など、二次的に派生した情報も含まれる場合があります。

ボードの状態はゲーム ツリーの各ノードに関連付けられており、ボード上で行われた移動か、プログラムの検索の一部として生成された移動によって到達した位置を表します。概念的にはノードに対してローカルですが、グローバルに定義することもでき、ツリーをトラバースするときにノードからノードへと段階的に更新されます。

非常に限られた量のメモリで動作する最初期のチェス プログラムの中には、最大から最小のような、検索しやすい順序で駒のシリアル リスト (配列) を維持していたものがありました。各駒には、盤上の位置や、その駒の有効な動きを表すマス目などの情報が関連付けられていました。リストは複数あり、1 つは白の駒用、もう 1 つは黒の駒用でした。リストは通常​​、駒とポーンに分けられていました。盤上のほとんどのマス目は空いているため、これはコンパクトな表現でしたが、駒と盤、または駒同士の関係に関する情報を取得するのが面倒なため、非効率的でした。駒リストは、盤を検索せずに駒にシリアル アクセスできるように、別の盤表現構造と組み合わせて、今日の多くのプログラムで今でも使用されています。

盤面を表現する最も簡単な方法の 1 つは、8x8 の 2 次元配列(または、同等の 64 要素の 1 次元配列) を作成することです。各配列要素は、特定のマス目を占める駒、またはマス目が空であるかどうかを識別します。一般的なエンコードは、0 を空、正を白、負を黒と見なすことです。たとえば、白のポーン+1、黒のポーン -1、白のナイト+2、黒のナイト -2、白のビショップ+3 などです。この方式は、メールボックスアドレス指定と呼ばれます。

このアプローチの問題は、移動の生成時に発生します。各移動は、ボードの端を回り込まないことを確認する必要があり、これによりプロセスが大幅に遅くなります。1つの解決策は、代わりに12x12配列を使用し、外側の端をたとえば値99で埋めることです。移動の生成中、目的のマスに駒があるかどうかを確認する操作は、目的のマスがボードの外にあるかどうかも示します。^{[1] [3]}

10x12配列を使用すると、メモリの使用効率が向上します。これは、左端と右端のエッジファイル（盤外としてマークされている）を重ね合わせることで、12x12配列と同じ機能を提供します。^{[1] [3]} 一部のチェスエンジンは、ランクとファイル番号の変換速度を向上させ、攻撃などに特別なコーディングトリックを可能にするために、16x16配列を使用します。

0x88 メソッドは、チェス盤の 8x8 の次元が 2 の偶数乗 (つまり 8 の 2 乗) であるという事実を利用しています。ボードは、サイズ 64 の配列ではなく、サイズ 16x8 = 128 の 1 次元配列 (0 から 127 の番号が付けられています) を使用します。これは基本的に 2 つのボードが隣り合っており、左側が実際のボードで、右側のボードには不正な領域が含まれます。配列内の正当なボード座標のランクとファイルのバイナリ レイアウトは次のとおりです0rrr0fff(r はランクを表すために使用される 3 ビットです。f はファイル用です)。たとえば、0x71 (バイナリ) は、マス b8 (代数記法01110001)を表します。メイン ボードから移動を生成する場合、配列を参照する前に、マス番号と16進数の0x88 (バイナリ) のAND 演算を行うだけで、移動先のマス目がメイン ボード上にあるかどうかを確認できます。結果がゼロ以外の場合、マス目がメイン ボードの外にあることを示します。さらに、2つの正方形の座標の差によって、その2つの正方形が同じ行、列、または対角線上にあるかどうかが一意に決定されます（チェックを決定するために使用される一般的なクエリ）。^{[1] [4]}10001000

配列ベースの構造よりも効率的で複雑なボード表現は、ビットボードです。ビットボードは 64 ビットのビット シーケンス (0 または 1) で、ボード上の各スペースの状態の有無 (偽または真) を示します。ボードの位置は、一連のビットボードを使用して表すことができます。たとえば、各ピース タイプ、各サイドの一連のビットボードで、ボードの位置を表すことができます。

この表現の利点は、反復処理の代わりに64 ビットエンティティに対してビット並列操作を使用して、ボードの状態に関する情報を操作および取得できることです。これにより、特に 64 ビット プロセッサが主流になったため、利用可能なハードウェアを最大限に活用できます。

ビットボードの実質的な利点は、盤上の各マスにある各タイプの駒が攻撃するマスのマップを事前に照合してテーブルに格納できるため、駒の可能な動きを、駒が置かれているマスの攻撃マップを 1 回メモリ フェッチするだけで取得でき、味方の駒が占めるマス (1 ビット操作) を除いた駒の正当な動きが得られることです。しかし、スライディング ピース (ルーク、ビショップ、クイーン) の動きは、盤上の他の駒の構成によって決まるため不確定です。そのため、これらの動きを表すために、特別で複雑なデータ構造が考案されました。

回転ビットボードは、ビットボードの回転コピーを使用して、ランクを表すビットに類似したファイルまたは隣接ビットの対角線内のスペース (ビット) を配置する、スライディング ピースの移動生成テクニックです。これらのビットは抽出され、テーブルのインデックスとして使用されて、これらのピースによって攻撃されるスペースのマップを取得できます。ビットボードは、ファイル インデックスの場合は 90° 回転され、対角インデックスの場合は 45° または -45° 回転されます。チェス ボードを回転することは概念的に困難であり、ビットボードを回転することは計算上洗練されていませんが、変換により、ピースの移動を連続的に列挙したり、ボードの構成を考慮してピースの攻撃マップのビットボードをシフトおよびマスクする長いシーケンスを回避できます。

マスクされたランク、ファイル、およびスライディング ピースの対角線は、ハッシュ関数を介して、マスクされた部分の占有ビットに基づいて、事前に計算された攻撃ベクトルのテーブルに直接インデックスを付けるために使用できます。メモリに格納する必要があるテーブルの潜在的なサイズを最小限に抑えるトリックとともに完全なハッシュ関数を使用するこのようなスキームの 1 つは、「マジック ビットボード」と呼ばれます。

転置表は、コンピュータゲームプログラムによって生成されたゲームツリー内の、以前に見た位置と関連する評価のキャッシュです。表を高速に検索するために、ゾブリストハッシュなどのハッシュ関数を使用して、一致するボードをすばやく見つけることができます。^[5]

コンパクトチェスボード表現（CCR）などの他の方法も提案されていますが^{（引用が必要）}、どれも受け入れられていません。

CCR は、マス目ごとに 4 ビットを使用してマス目の占有状況を表します。^{[注 1]}ランク全体は 32 ビットで表すことができ、盤面は 8 つのレジスタで表すことができます (残りの位置情報用に追加の 1 つ)。マス目の占有コードはレジスタからダイヤルアウトしてプログラム カウンタに追加し、ジャンプ テーブルをインデックス化して、このマス目の駒の種類 (ある場合) に応じた動きを生成するコードに直接分岐します。プログラムは従来の動き生成方法よりも長くなりますが、盤面の端のチェックは必要なく、盤面外への動きは不可能なので、動き生成速度が向上します。

CCR の欠点は、1) 32 ビット ワード サイズへの依存、2) API に少なくとも 9 個の空きレジスタが使用可能、3) レジスタにアクセスするために CISC アーキテクチャ上でアセンブリ プログラミングが必要、4) アセンブリ アプリケーションの移植性がないこと、です。