回転可能なビットボード：古いアイデアの新しいラウンド

簡単な説明

この記事では、「ビットボード」（各ビットが1つのチェッカーボードフィールドを表す64ビット整数）を使用する場合のニュアンスについて説明します。 1994年、ニュージャージー州ケープメイでACMが主催したチェスシンポジウムの後、私はCray Blitz（Crayスーパーコンピューター用にRobert Hyatt、Harry Nelson、Albert Goverによって書かれたコンピュータープログラム）を完全に置き換えることにしました。翻訳。）。 私はチェス4.x（イリノイ州ノースウェスタン大学で開発され、20世紀の70年代に支配されたチェスプログラム-約翻訳）でテストされたビットボード法を試してみることに興味がありました。チェスに適しているかどうかを自分で決めてください。 この新しいプログラムの開発中に、「回転可能なビットボード」の概念が考案され、このタイプのデータ構造を許容可能なパフォーマンスで動作させるために必要なことが判明しました。

1.はじめに

ビットボードは、コンピューターチェスの文献で何度も言及されています。 1970年代半ばに、スレートとアトキンは12個の64ビット整数を使用する方法を思いつき、説明しました。各整数は、チェス盤上の1種類のチェスの駒（白は6個、黒は6個）を表しました。 ここでは、KAISSAチーム（Donskoyなど）が、ノースウェスタン大学のチームとは独立して同じアイデアを発明したようであり、過去25年にわたって同じアプローチを使用して他の多くのプログラムが作成されていることに注意してください。



提案された一致ビットをチェス盤のフィールドに関連付けます。 値が1のビットは、チェス盤上の駒の存在の兆候として機能し、ビット0はその不在を示しました。 したがって、白いポーンが占めるフィールドに対応するwhite_pawnビットボードでは、値が1の最大8ビットがあります（この記事では、フィールドには0から63までの番号が付けられ、位置0はフィールドA1に、7はフィールドH1に対応、56 64ビット整数の位置0にあるビットは「最上位ビット」と呼ばれ、位置63のビットは「最下位ビット」と呼ばれます）（最上位ビット、MSB最下位ビット、LSB-およその翻訳。）



これらの12の64ビットワードでボードに位置情報を保存することに加えて、スレートとアトキンは、異なる種類の情報を対象としたビットボードの2つの追加セットを生成し、その後更新する方法を説明しました。 attack_from [64]-各フィールドの値が1であるビットボードの配列。特定のフィールドに立っているフィギュアによって攻撃される可能性があります。 たとえば、attacks_from [E4]は、フィールドE4に立っている人物によって直接攻撃されたフィールドを提供します。 さらに、attacks_to [64]配列には、このフィールドを攻撃するフィギュアが占めるすべてのフィールドのビット1を持つビットボードが含まれています。 たとえば、attacks_to [E4]は、ボード上のすべてのフィールドにビット1を含むビットボードで、印象的なフィールドE4の数字があります。



この2セットのビットボードはこの記事の主題であり、実行速度を大幅に低下させることなくattack_from []ビットボードを動的に計算する新しい非常に高速な方法を説明します。これはSlateとAtkinが説明した更新方法の場合です。 （Slate / Atkinはシーケンシャルアップデートを使用したことに注意してください。以下に説明する手順は、「オンザフライ」で長距離フィギュアの攻撃を計算するには遅すぎるためです。ビットボードを動作させると同時に高い計算コストを回避するために、シーケンシャルアップデートを使用しました）



チェスプログラムで非常に役立つビットボードには、他にも便利なプロパティがあります。 これらのプロパティの1つは、「ビット並列」操作と呼ばれるものです。 たとえば、従来のチェスプログラムでは、ポーンがE4フィールドにあり、それがチェックポイントであるかどうかを確認する場合、D5、E5、F5、D6、E6、F6、D7、E7、F7フィールドをチェックする必要があります敵の駒がないことを確認してください。 これには、9つの比較操作が必要です。 ビットボードを使用して、ポーンが立つことができる各フィールドのマスクの配列を事前に計算し、is_passed_white [E4]マスクを取得して、ビットポーンと黒ポーンのビット単位の「AND」演算を実行するだけです。 マスクを正しく計算して、上部の9つのフィールドのそれぞれに単位がある場合、1つのAND演算により、黒のポーンが存在しないか、逆にそれらの存在が判定され、E4の白のポーンが通過できなくなります。 実際、9つの異なるチェックを並行して実行し、1つのAND演算で9つの質問に同時に回答しました。



他の利点もありますが、この記事のトピックは回転可能なビットボードであり、必要に応じて、連続更新による制限なしで複雑な/遅いサイクルなしで、attacks_from [64]およびattacks_to [64]配列からデータを取得する方法です。 。

2.通常のビットボードを使用したAttacks_from配列[64]の計算

回転ビットボードの方法に進む前に、attacks_from []の計算の複雑さに注意する必要があります。 短距離の数字の場合、これはもちろん非常に簡単です。 たとえば、knight_attacks [64]配列を事前に準備して、馬がF6フィールドにいる場合、knight_attacks [F6]は、馬がF6フィールドから攻撃できるすべてのフィールドにビット1を含むビットボードになるようにすることができます。馬に攻撃された場合、チェス盤上の駒の配置に依存しないでください）。 同じ考え方がキングとポーンにも機能します（ポーンは斜めにヒットするため、1つまたは2つのフィールドを前方に移動することなく、わずかな変更を加えます）。



ただし、長距離フィギュアの場合、長距離フィギュアは動きの方向でのみ攻撃し、この方向で最初に遭遇する数字だけを攻撃するため、アレイへの単純なアピール（上記のように）は機能しません。 では、これをどのように計算するのでしょうか？



最初に、占領された正方形と呼ばれるビットボードが必要です。これは、任意の色の形状があるすべてのフィールドに単位が表示されたビットボードにすぎません（たとえば、ビット単位の「OR」（OR）図のタイプごとに12個のビットボードすべての間で、実際にはそのような2つのビットボードを格納します：1つは黒用、もう1つは白用-必要に応じてそれらの間でOR演算を使用し、占領された正方形のビットボードを取得します）。



図1は、占有フィールドに「X」のマークが付けられ、非占有フィールドに「-」のマークが付けられたチェッカーボードの位置の例を示しています。







長距離のフィギュアは、どんな種類のフィギュアに出会っても停止するため、フィールドに何があるかは問題ではありません。 象がフィールドF5に立つと（図2でBでマークされている）、次のフィールドセットを直接攻撃していることがわかります：{B1、C2、D3、E4、G6、H3、G4、E6、D7}。 攻撃ビットボードを計算した後（これがこの位置からの許容される象の動きを使用する場合）、自分の駒を打つすべての動きを除外する必要があります。 前述のwhite_occupiedビットボードを使用して、補数演算（ビットごとの否定）を適用し、次に攻撃ビットボードとAND演算を適用できます。これにより、象の攻撃ビットボード内の自分のピースに対する攻撃に対応するビットがリセットされます。これらは無効な動きです。



これまでのところ良い。 しかし、ピースが移動できる4本（またはクイーンの場合は8本）の光線をすべて列挙せずに、攻撃されたビットをどのように判断するのでしょうか？ 一般に、これはそれほど難しくありませんが、各方向でループの個別の反復が必要になるため、あまり効果的ではありません。



最初に、フィギュアが移動できる8つの方向それぞれにマスクのセットを作成します。 プラス1 [64]、プラス7 [64]、プラス8 [64]、プラス9 [64]、マイナス1 [64]、マイナス7 [64]、マイナス8 [64]、マイナス9 [64]と呼びます。 これらのビットボードには、特定の方向でSQフィールドから象を攻撃できるフィールドのビット1が含まれています。 この例では、F5の司教がplus7方向（これらのフィールドはF5-E6-D7-C8です）で、plus7 [F5]は図3のようになります。



これにより、象とボードの端の間に障害物がなければ、象が+7方向に攻撃できるすべてのフィールドが得られます。 しかし、我々はそれらが存在する可能性があることを知っており、もしそうなら、私たちはこの方向の妨害人物を見つけなければなりません。 これを行うために、上記のビットボードを取得し、それと占領された正方形のビットボードの間でANDを実行します。 象がこの方向でブロックされている場合、ビット1が各フィールドを表し、象のC8への斜めの動きをブロックする図がある空でないビットボードを取得します。 最初のブロック図のみが必要なため、FirstOne（）関数を使用します。これは、値1の最初のビットのインデックスを返します。たとえば、象がC8およびD7でブロックされた場合、FirstOne（）はフィールド番号D7（51）を返す必要があります。



これで、この対角線に沿って攻撃されたフィールドのリストと、長距離フィギュアがブロックされているフィールドができました。 私たちがやるべきことは、ブロッキング数字の後に攻撃されたフィールドを削除することだけです。 そして、これは最も簡単な部分です。 これを行う方法を次のコード例で説明します。

  diag_attacks = plus7 [F5];
	ブロッカー= diag_attacks＆占領された正方形;
	 blocking_square = FirstOne（ブロッカー）;
	 diag_attacks ^ = plus7 [blocking_square]; 

これが、1つのビームに対して行う必要があるすべてです。 コードをわかりやすくするため、diag_attacksは上記のビットボードで、F5フィールドからの攻撃フィールドが+7方向に含まれています。 ブロッカーには、すべてのピースがこの対角線上にあるビットボードがあります。 最初のブロック図を見つけ、plus7 [blocking_square]とdiag_attacksの間の排他的「OR」を作成します。これにより、それに続くすべての攻撃フィールドが実際に遮断されます。 （それを理解してみましょう。F5の司教がE6でブロックされている場合、この場合のplus7 [E6]は次のようになります。ユニットのビットはD7とC8のみです。D7/ C8ビットは両方のビットボードでゼロではないため、排他的な "または「ビットボード間で、これらの（およびこれらのビットのみ）がリセットされます。）



最後のブロック図を見つける必要があるため、マイナス方向の場合はFirstOne（）を使用しないという違いだけで、4つの方向すべてについてこれを繰り返します。 これの代わりに、LastOne（）に切り替えます。 これで、4つの方向すべてで象の攻撃をカウントするコードは次のようになります。

  diag_attacks = plus7 [F5];
	ブロッカー= diag_attacks＆占領された正方形;
	 blocking_square = FirstOne（ブロッカー）;
	 bishop_attacks = diag_attacks ^ plus7 [blocking_square];
	 diag_attacks = plus9 [F5];
	ブロッカー= diag_attacks＆占領された正方形;
	 blocking_square = FirstOne（ブロッカー）;
	 bishop_attacks | = diag_attacks ^ plus9 [blocking_square];
	 diag_attacks = minus7 [F5];
	ブロッカー= diag_attacks＆占領された正方形;
	 blocking_square = LastOne（ブロッカー）;
	 bishop_attacks | = diag_attacks ^ minus7 [blocking_square];
	 diag_attacks = minus9 [F5];
	ブロッカー= diag_attacks＆占領された正方形;
	 blocking_square = LastOne（ブロッカー）;
	 bishop_attacks | = diag_attacks ^ minus9 [blocking_square]; 

これは、ANDおよびORを使用した多数の操作とマスキングの必要性に加えて、FirstOne（）/ LastOne（）関数を使用してブロッキングフィールドを検出することになります。 これは非常に高価ですが、ブール演算子ではほとんどの作業が並行して行われるため、それでも正当化できます。 ただし、FirstOne（）/ LastOne（）の呼び出しを削除するより良い方法があり、このメソッドのように2段階ではなく、1段階で対角線/水平/垂直全体を処理します。



FirstOne（）/ LastOne（）関数は、Cでプロシージャとして実行すると非常に高価になることに注意する必要があります。最初または最後のビットを見つけることは、上記の攻撃の計算に多くの時間を必要とする重要なタスクだからです。 幸いなことに、最新のマイクロプロセッサにはこれらの値を計算するためのハードウェア命令があります（IntelはX86アーキテクチャにBSF / BSR [ビットスキャンフォワード、ビットスキャンリバース]命令を備えています）。 他のタイプのアーキテクチャも同様の指示を提供します。

3.回転可能なビットボード

1994年9月にビットボードを使用したCraftyバージョンが登場した後、私はUABでセミナーを開始しました（Crafty-Robert Hyattによって書かれたチェスプログラム、UAB-バーミンガムのアラバマ大学-およその翻訳）。効率を高めるための新しい方法に取り組み、開発します。 最初の議論の1つは、水平面に沿って長距離の人物の動きを生成することがいかに簡単かということでした。



特定の水平線（チェス盤のフィールドの水平列）のフィールドを取る場合、長距離の駒の動きは非常に簡単に取得できます。これは、占領された正方形のビットボードの8ビットによって水平が決定されるためです。 このビットボードを右に移動して、その下位ビットに水平方向の8ビットが含まれるようにし、次に数値255とANDを実行すると、この水平方向のフィールドに対応する8ビットが得られます。



これを念頭に置いて、rank_attacks [64] [256]ビットボードの配列を検討してください。 この配列を初期化するには、A1などのフィールドを使用します。 どのフィールドが占有され、どのフィールドが占有されていないかに応じて、その水平には256の異なる状態しかないことがわかります。 ゲームを開始する前に、この水平の単一ビットの256のすべての組み合わせを考慮して、A1のルークがどのフィールドに進むことができるかを事前に計算できる場合、ビットボードrank_attacks [A1] [contents]を参照するだけで、この水平のフィールドを攻撃することができます。ここで、contentsは与えられた水平の状態の8ビット表現です。 必要なのは、64個のフィールドのそれぞれと、これらのフィールドが配置されている水平線の256の異なる状態すべてに対してビットボードのセットを計算することです（そう、考えてみれば、水平線は128状態しか持てません。フィールドの1つはルークですが、この単純化を無視する方が簡単です）。 ここで、水平には8つのステータスビットがありますが、2つの極端なビット（LSBとMSB）は、数字があるかどうかに関係なく攻撃されるため、何も変わりません。 その結果、各水平のテーブルサイズを75％削減するために、それらを以降の計算から削除します。 したがって、rank_attacks配列のサイズをrank_attacks [64] [64]に減らします。 他のすべての同様の配列は、同じ単純化を使用します。



これまでのところ、rank_attacks配列でメモリにアクセスするだけで、ルーク攻撃の半分を得ることができます。 しかし、象の垂直攻撃と2つの対角線はどうでしょうか。 そこでは、ビットは占領された正方形のビットボードで隣接していないため、等高線以外には適用できません。



セミナーでこれについて議論している間、特殊なチェスの機器を使用する場合、レジスタを割り当てて64ビットの占領された正方形の値を格納することに気づきましたが、占領された正方形にアクセスできる他の3つの「疑似レジスタ」を強調表示できますさまざまな方法で。 たとえば、占領された正方形の内容全体を90度回転して、同じ垂直のビットが連続するようにします。 事前に計算された水平方向の攻撃と同じように、これを使用して垂直方向の攻撃を見つけることができます。 また、占領された正方形のビットボードを左右に45度回転させる2つのレジスタを区別できるため、これらの回転したビットボードの対角線ビットが隣接します。 図4は、通常のチェッカーボード上のフィールドの番号付け方法を示しています。







A1がzero_bitビット（MSB）であり、H8が占領平方ビットボードの63番目のビット（LSB）であることを思い出してください。 最初に、左に90度回転して垂直ビットを連続させます（64ビットのビットボードでは左下隅がゼロビットのままであり、右上隅には常にシリアル番号63があることに注意してください）図5。



次に、図6に示すように、元の位置を左に45度回転します。







この回転したビットボードでは、ボトムフィールド（A1）がヌルビットになり、次のものが順番になります。 したがって、たとえば、A2はビット1になり、B1はビット2になり、H8がビット63になるまで続きます。



上記のビットボードでは、H1からA8までの対角線とそれに平行なすべての対角線上のビットが隣接していることに注意してください。 これは、最初の2つのビットボードほど便利ではありません。 配列のインデックスとして使用できるように、特定の水平または垂直を数値の右端にどれだけシフトする必要があるかを簡単に計算できます。 また、必要な8ビットを抽出するには、数値255とANDを実行する必要があることもわかっていました。対角線の場合、各対角線の長さは異なります。つまり、シフトとマスクの値を変えて余分なビットを削除します。 この問題の解決策については後述します。



図7のビットボードのように、元のビットボードを右に45度回転して、他の対角線上に隣接するビットを作成します。



これがすべて揃ったので、すでに考慮されているrank_attacks [64] [64]に加えて、攻撃のためにビットボードの配列をさらに3つ追加する必要があることが明らかになります。 File_attacks [64] [64]、diaga1h8_attacks [64] [64]、およびdiagh1a8_attacks [64] [64]が追加され、元の占領された正方形のビットボードの回転を学習する場合、同じインデックススキームを使用できます。ゾウまたはルーク用のテーブルへの2回の呼び出しとクイーン用の4回の呼び出しの更新手順。



その後、占領された正方形のビットボードを回転させる方法について多くの議論をした後、簡単な解決策が見つかりました。 占領された正方形のビットボードのみを保存し、必要に応じて回転させるのではなく（非効率性のためほとんど不可能と考えられます）、占有フィールドに4つのビットボードを保存できます：通常および90度回転、左に45度、右に45度。 MakeMove（）の図を移動する手順で、占領された正方形のビットボードを更新する同様のコードを見つけることができるため、これは非常に簡単です。



占有スクエア^ = set_mask [from] | set_mask [to];



これは、opposed_squaresの開始フィールド「from」のビットを1に設定する必要があることがわかっているためです（そうでない場合、移動する図形はありません）。 ）; また、occupiced_squaresビットボードの最後の「to」フィールドのビットの値はゼロでなければなりません（そうでなければテイクになります）。 したがって、排他的な「OR」を使用して、開始フィールドビットがリセットされ、終了フィールドビットが設定されます。



set_mask [64]ビットボード配列のすべての要素には、対応する位置に1ビットのみが設定されています。 たとえば、set_mask [0]には左端のビットセット（ゼロビット）があり、set_mask [63]には最下位ビットセット（63番目のビット）があります。 回転可能なビットボードを使用するために、set_mask_rl90 [64]、set_mask_rr45 [64]、set_mask_rl45 [64]という3つの新しいマスクセットを作成しました。 これらはそれぞれ、フィールド番号をインデックスとして使用し、ビットマップを返します。ビットボードでは、対応するビットが占領下の回転可能なビットボードに設定されています。 たとえば、set_mask_rl90 [0]は実際に7番目のビットを設定します。これは、rotated_leftビットボードで画像を見ると、ビット0が7番目になるためです。



これが、すべてを機能させるために必要なソリューションでした。 占領された正方形のビットボードを回転させる代わりに、4つの占領された正方形のビットボードを同時に保存し、これらのタイプのフィギュアの攻撃を受ける必要があるときはいつでもビショップ/ルーク用に2つ、または女王用に4つ使用できます。



象の場合、使用できる最適化が1つありますが、メモリに比べて高価です。 ルークの場合、対応する水平または垂直を数値の右端に移動し、255とANDを実行してこの水平または垂直の内容を取得したことを思い出してください。 これは、各水平または垂直に8ビットが含まれているため機能しました。 しかし、対角線の場合、それぞれの長さは隣のものとは異なります。



このアルゴリズムを単純化するために、対角線の場合にAND 255を実行します。これにより、明らかに、目的の対角線が得られますが、隣接する対角線（対角線）からの余分なビットがいくつかあります。 対象の対角線に3ビット（合計8つの一意の状態）しかない場合、これらの8つの状態のそれぞれに32ビットの余分なビットが結合されます。 つまり、必要な3ビットの状態があり、32回繰り返されます。 したがって、追加の5ビットに何が含まれているかは関係ありませんが、3ビットの対角線に対して正しい攻撃ビットボードを取得できます。

4.回転可能なビットボードを使用したattack_from [64]の計算

攻撃を計算するために、4つの異なる配列を使用します。1つは水平攻撃、1つは垂直攻撃、もう1つはフィールドを通過する2つの対角線です。 これらのアレイには、rank_attacks [64] [64]、file_attacks [64] [64]、diaga1h8_attacks [64] [64]、diagh1a8_attacks [64] [64]という名前を付けました。



これらの配列を初期化するために（これはアプリケーションの起動時に行われ、それ以降は配列は変更されません）、問題の方向（たとえば、女王）に移動できるフィールドに長距離の数字があると単純に仮定しました。 次に、各フィールドにrank_attacks [square] [rank_contents]を導入しました。この水平のフィールドがrank_contents番号の8ビットに従って占有されている場合、正方形の正方形に立つルーク/クイーンがどの水平線を移動できるかを示すビットボード「。 たとえば、以前に検討された占領された正方形のビットボードを取り上げますが、前の例のようにF5フィールドの司教の代わりに、そこにルークを置きます（図8）。 rank_attacks [37] [100]を初期化しようとしていると仮定します（37はフィールドF5で、100はこの水平方向の占有フィールド-01100100に対応します）。 図9に示すように、このrank_attacks要素を初期化します。これは、上記のように、ピースがF5にあり、水平が3つのピースで占められている場合、ルーク/クイーンが5番目の水平で攻撃できるフィールドに完全に対応します。







まあ、悪くない。 これを行うことにより、水平に沿ってルーク攻撃をすばやく取得できます。 しかし、水平方向ではなく垂直方向に攻撃を計算する必要があります。 これを行うには、占領されたrl90ビットボードを使用します。これは、前の占領された正方形の正確なコピーですが、図10に示すように90度回転されています。



3番目の「水平」を取得すると、実際には、垂直Fでの雇用に関する情報を取得します（おそらく、水平から3番目-およその翻訳を意味します）。 以前に計算された攻撃ビットボードが再び使用されますが、今回はattacks_file [37] [251]（もう一度、37はフィールドF5、およびこの垂直フォーム11111011の占有フィールドを意味します）、図に示すように決定した値11。







ここで、水平攻撃と垂直攻撃の両方の値を取り、それらの間でORを行うと、フィールドF5に立っているルークの攻撃フィールドの完全なセットが得られます。 occupied_squares, , OR / . , . :

 BITBOARD attacks=0;
    if (BishopMover(piece)) {
      get diaga1 status (shift/AND); /* 6 bits */
      attacks|=diaga1h8_attacks[square][status];
      get diagh1 status (shift/AND); /* 6 bits */
      attacks|=diagh1a8_attacks[square][status];
     }
    if (RookMover(piece)) {
      get rank status (shift/AND); /* 6 bits */
      attacks|=rank_attacks[square][status];
      get file status (shift/AND); /* 6 bits */
      attacks|=file_attacks[square][status];
     } 

, , . BishopMover() RookMover() «», , ( ), ( ). Crafty , P=1, N=2, K=3, B=5, R=6 Q=7. piece_type&4, , . , piece_type&1 , , piece_type&2 , /.

5. attacks_to[64]

attacks_to[] , , . , attacks_to[28] (28 = E4) , 12, , E4 E8 F6, E1 D3 (E4 T, «target»).







«T» — , 0 . X ( 1) , E4. , E4, AND occupied_squares . 1 , , E4. E4 , AND occupied_squares .



: () () ? (, , , , ), E4, AND / , 1 /, , . /. , AND / . , , OR , , E4.



, , ( ) , (, , , ), .

6.

, , . «/» , , . «» , FirstOne() , «», . . , : (, Crafty 21 . 6 «FROM» (), 6 — «TO» (), 3 — MOVING_PIECE ( ), 3 — PROMOTE_TO, .)

 piecebd=WhiteQueens;
    while (piecebd) {
      from=LastOne(piecebd);
      moves=AttacksQueen(from);
      temp=from+(queen<<12);
      while (moves) {
        to=LastOne(moves);
        move_list[i++]=temp+to<<6;
        Clear(to,moves);
       }
      Clear(from,piecebd);
     } 

, , , , , — . , AND , , , — , . , , , , , ; , , , . , . , .

 piecebd=WhiteQueens;
    while (piecebd) {
      from=LastOne(piecebd);
      moves=AttacksQueen(from) & BlackPieces;
      temp=from+(queen<<12);
      while (moves) {
        to=LastOne(moves);
        move_list[i++]=temp+to<<6;
        Clear(to,moves);
       }
      Clear(from,piecebd);
     } 

, , . , «». , , occupied_squares , ( ).



, attacks_to[]. , (attacks_to[sq]), / . — « ?», , . (/, /, , ) AND ( , , ), , , «», «, ».



, . , , attacks_to[sq], , . , ; AND attacks_to , . AND , , . attacks_to, , AND attacks_to , . , attacks_to .



, , ? . , «» attacks_to, (, , , , , «»). AND, , , . , (/ , / /), OR attacks_to, , . ( plusN[]/minusN[], , , .)



, , , . , . , . . , , (, ), , , . , attacks_to , .

7.結論

, « ». , 64 , , . , CPU 64- , , , 64- . 64- , .



64- (Alpha, HP, MIPS — ) 64- , Intel Merced, , . , (AND, OR, XOR, ) 32- — 64- . 64- , . , , .



, ( ), , ( AND , ), . «Chess 4.0» , , , , Crafty ( . , ), . , , Crafty, , «Chess 4.0», « », . « , ?». . , « » (« , » — . .) , ( ) , , «» , .



:

: http://www.cis.uab.edu/info/faculty/hyatt/bitmaps.html

翻訳者から

, . , , . , , , .



:

www.frayn.net/beowulf/theory.html#bitboards

www.craftychess.com



«bitboard», «», , « » .



«bitmap» «bitboard» , « » « » . «».



, : AND, OR . ., .