ポジションプレゼンテーション
ゲーム内でポジションを提示することは、後続のすべてに影響を与える重要なステップです。 私が学生だったとき、ためらうことなく、各セルに1つずつ、32バイトの配列の形で最も明白な表現を選びました。 これは非効率的なソリューションであることが判明しました。 そして、少なくともチェッカーで機能した場合、チェスの場合、結果は嘆かわしかったです。
後で、すべての動きのリストを取得するための最速のアルゴリズムのいくつかがビットボードを使用することを学びました。 チェスの場合、これは64ビット数の形式での位置の表現であり、各ビットはボードの1つのセルを担当します。 合計で、複数のビットボードが使用されます。1つは白のポーンの位置を保存し、もう1つは黒馬の位置を保存します。チェスのすべての動きを生成するには2つの基本的な方法が使用されます：「回転可能なビットボード」と「魔法のビットボード」。 「回転可能なビットボード」メソッドの使用については、記事「 回転可能なビットボード：古いアイデアの新しいラウンド 」で説明されています。 「マジックビットボード」メソッドの使用については、 チェスプログラミングwikiで英語で見つけることができます 。 Cプログラミング言語での実装に興味がある場合は、 craftychess.comで入手可能なCraftyチェスエンジンのコードを確認することをお勧めします。 エンジンの作成者であるRobert Hyatt教授（Robert Hyatt）は、コードの可読性に多くの注意を払い、多くの場所で説明が提供されています。 彼はまた、チェスプログラミングに関する興味深い記事の著者でもあります。
チェスの場合、ビットボードの使用は自然に思えます。 64セル-64ビット。 ビットの番号付けの問題はありません。 1つのフィールドに白いポーンのすべての動きを生成することにします。 これを行うには、すべてのポーンのビットマスクを取得し、それを左に8ビットシフトし（黒のポーンがそれに応じて右に移動します）、すべてのフリーセルのビットボードとANDを行う必要があり、ポーンが移動できるフィールドのビットマスクを即座に取得します。 移動のリストを作成するためだけに残ります。
ロシアのドラフトでは、すべてが少し複雑です。 ビットとボードフィールドの対応は何ですか？ チェスから可能な限り多くを取るためのオプションの1つは、64ビット整数の形式でボードの表現を使用することです。ここでは、ブラックフィールドを担当する32ビットのみが使用されます。 はい、それはオプションですが、すべてのビットのちょうど半分が使用されないという事実に私は落ち込んでいます。 ゲームに32個のブラックセルのみが使用されている場合、32ビットの数値をビットボードとして使用しないのはなぜですか？
したがって、ロシアのドラフトでの位置は、動きの順番を示す整数と、4つの32ビットビットボードによって記述されます。 フィールドとビットの対応についての質問は後ほど残されます。 ボードを表すには、どの4つのビットボードを選択する必要がありますか？ 両側に2つのビットボードを使用する場合、すべての単純なチェッカー、および単純な女性と女性の両方のすべてのチェッカーのオプションに決めました。 この場合、1回の操作で興味のあるすべてのビットボードを取得できます。 だから
typedef int square_t; typedef uint32_t bitboard_t; typedef int side_t; enum side_t { WHITE, BLACK }; enum position_bitboard_index_t { IDX_ALL_0 = 0, // IDX_ALL_1 = 1, // IDX_SIM_0 = 2, // IDX_SIM_1 = 3 // . }; struct position { bitboard_t bitboards[4]; side_t active; }; // : uint32_t /* */ all_bb = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1]; uint32_t /* */ empty_bb = ~all_bb; uint32_t /* */ mam_bb = bitboards[IDX_ALL_0] ^ bitboards[IDX_SIM_0];
番号付けビット
重要な問題は、ビットの番号付けです。 単純なチェッカーの動きを生成する問題を考慮する最も簡単な方法。 ビットの番号付け方法ごとに、可能な動きのビットマスクを簡単に取得できる単純な式を見つける必要があります。 最も明白なビット番号付けオプションから始めましょう：
+-+-+-+-+-+-+-+-+ | | 28 | | 29 | | 30 | | 31 | 8 +-+-+-+-+-+-+-+-+ | 24 | | 25 | | 26 | | 27 | | 7 +-+-+-+-+-+-+-+-+ | | 20 | | 21 | | 22 | | 23 | 6 +-+-+-+-+-+-+-+-+ | 16 | | | 17 | | | 18 | | 19 | | | 5 +-+-+-+-+-+-+-+-+ | | 12 | | 13 | | 14 | | 15 | 4 +-+-+-+-+-+-+-+-+ | 8 | | 9 | | 10 | | 11 | | 3 +-+-+-+-+-+-+-+-+ | | 4 | | 5 | | 6 | | 7 | 2 +-+-+-+-+-+-+-+-+ | 0 | | 1 | | 2 | | 3 | | 1 +-+-+-+-+-+-+-+-+ abcdefgh
きれいに見えますが、やや不快です。 実際、素数のビットマスクをシフトする必要があるビット数は、シリーズのパリティに依存します。 これにより、より複雑な式を記述できます。
// , , — : uint32_t up_right_bb = 0 | ((bb & RANK_1357) >> 4 | ((bb & RANK_2468) >> 5 ;
ここでは、予備のパラシュートなどのオプションを保持し、同じ対角線上のビット番号が算術級数を形成する番号付けを見つけようとします。 少しプレイすると、この番号付けオプションが表示されます。
+-+-+-+-+-+-+-+-+ | | 31 | | 5 | | 11 | | 17 | | 8 +-+-+-+-+-+-+-+-+ | 24 | | 30 | | 4 | | 10 | | 7 +-+-+-+-+-+-+-+-+ | | 23 | | 29 | | 3 | | 9 | 6 +-+-+-+-+-+-+-+-+ | 16 | | | 22 | | 28 | | 2 | | 5 +-+-+-+-+-+-+-+-+ | | 15 | | 21 | | 27 | | 1 | 4 +-+-+-+-+-+-+-+-+ | 8 | | 14 | | 20 | | 26 | | 3 +-+-+-+-+-+-+-+-+ | | 7 | | 13 | | 19 | | | 25 | 2 +-+-+-+-+-+-+-+-+ | 0 | | 6 | | 12 | | 18 | | 1 +-+-+-+-+-+-+-+-+ abcdefgh
対角線を左上に移動すると、すべてがうまくいきます。単純な動きを生成するには、左[右]に白[黒]の単純なシフトを使用できます。 対角線a1-h8（bolshak）と平行に走る対角線をとると、算術級数があり、モジュロ32加算が使用され、巡回シフト演算に対応します。 この操作は、一部のプロセッサ、特にx86ファミリの命令セットに含まれているため、非常に効果的です。 これで停止します。
現実には、単純なものすべてが前進して去れるわけではありません。 したがって、実際のプログラムでは、シフトの前にAND演算を実行する必要があり、この機能を持つチェッカーのみを残します。 複数の対戦相手のチェッカーを1回の動きでとることができるという技術的な難しさを排除する場合、単純なものをとることも同様に考慮され、2回連続してシフトする必要があります。最初の対戦は対戦相手のチェックボードで、2回目はフリーフィールドで行います。 以下は、左上のテイクをチェックする場合の例です。
all = bitboards[IDX_ALL_0] | bitboards[IDX_ALL_1]; enemy = bitboards[IDX_ALL_1 ^ active]; bitboard_t empty = ~all; bitboard_t singles = bitboards[IDX_SIM | active]; bitboard_t try_left_up = ((((singles & possible_left_up) << 1) & enemy) << 1) & empty;
かなり効果的なソリューションを得ましたが、8x8ボードでのみ機能します。 国際チェッカー（10x10ボード）の場合、ボードには50個の黒いセルがあります。 同様のタイプの番号付けを使用して、50ビットの巡回シフトを必要とするレーキを踏んでいます。 そのような命令はないため、左シフト、右シフト、ORの3つの操作でビットマスクを取得する必要があります。 8x10ボードが使用されることを除いて、ロシアのドラフトと変わらないSparintetiドラフトの場合、そのような番号付けのアナログを思い付くのは難しいので、ほとんどの場合、ボードの10x10サブセットを使用する必要があります。
魔法
次に、女性の捕獲に関連する問題を検討します。 女性はキャプチャを実行できますか、どのチェッカーが殺されますか？キャプチャ後に女性はどこになりますか？ これらの質問に答えることは退屈なサイクルなしではできないようです。 しかし、よく見ると、これらの質問に答えるために同じ対角線のビットのみが使用されています。 doubleに平行な対角線（対角線g1-a7およびh2-b8）には、連続したビット番号が付けられています。 これはかなり単純なアイデアにつながります。すべてのチェッカーのビットボードを右に移動して、対角線のすべてのビットが最低位置を占めるようにする必要があります。 そして、事前にコンパイルされたテーブルを参照します。 そして、これは最小限の操作です！
// sq - , const struct square_info * sm = square_infos + sq; // , shift - uint32_t index = (all >> sm->shift) & 0x7F; // const struct mam_take_magic * mtm = mam_take_magic[sq] + index; // mtm , , ,
大きなものと平行な対角線の場合、これらの質問に対する答えを得るのはやや困難です。 1つの方法は、同時に2つの数値をサポートすることです。1つは大きい方に平行な対角線に沿ったキャプチャをチェックするのに便利で、もう1つはdoubleに平行な対角線に沿ったキャプチャをチェックするのに便利です。 この番号は、90度の角度で回転したように見えます。 したがって、名前-回転式ビットボード。 このアイデアに基づいてチェスムーブジェネレーターを実装したとき、90度回転した16進形式のビットボードを読むたびに、思わず頭を回しました。 回転式ビルボードの可能な番号付けは次のとおりです。
+-+-+-+-+-+-+-+-+ | | 25 | | 19 | | | 13 | | 7 | 8 +-+-+-+-+-+-+-+-+ | 24 | | 18 | | 12 | | 6 | | 7 +-+-+-+-+-+-+-+-+ | | 17 | | | 11 | | 5 | | 31 | 6 +-+-+-+-+-+-+-+-+ | 16 | | | 10 | | 4 | | 30 | | 5 +-+-+-+-+-+-+-+-+ | | 9 | | 3 | | 29 | | 23 | 4 +-+-+-+-+-+-+-+-+ | 8 | | 2 | | 28 | | 22 | | 3 +-+-+-+-+-+-+-+-+ | | 1 | | 27 | | 21 | | 15 | 2 +-+-+-+-+-+-+-+-+ | 0 | | 26 | | 20 | | 14 | | 1 +-+-+-+-+-+-+-+-+ abcdefgh
しかし、もっと美しいアイデアもあります！ だから、大きな男を検討してください。 ビットボードでは、これらはビット0、7、14、21、28、3、10、17です。これらのビットを0〜7の順番に並べ替える関数を考え出す必要があります。 次に、事前に準備されたテーブルを使用できます。
私にとって、このような操作は、特に異なるゲームでロジックを実装するように設計されたプロセッサ命令セットで非常に役立ちます。 命令自体の形式はSUBBITS a、vです 。ここで、aは特定の数、vはどのビットを残して下位ビットに転送するかを示すビットマスクです。 たとえば、SUBBITS 0xFF00FF、0x111111は出力110011 2を提供する必要があります：番号0、4、8、12、16、20のビットを残し、ゼロビットをゼロの位置、4番目から1番目、8番目から2番目、...
まあこれは余談です。 ほとんどの場合、このような操作を既存のコマンドで効果的に実装することは難しくありません。 ビットを右に運ぶことは分割です。 実際には、すべてのビットを一番左の位置に転送（乗算）してから、右に大きくシフトする方が簡単であることが判明しました。 どうやって？
少し考えてみてください。 数値xがあり、この数値の10番目のビットを31番目の位置にしたいとします。これは残りのビットでは意味がありません。 31-10 = 21なので、これはかなり単純なタスクです。x<< 21が得られます。10番目のビットだけでなく、20番目のビットもあり、30番目の位置に転送したいとします。 これは難しくありません：
bit10 = 1 << 10; bit20 = 1 << 20; mask10 = x & bit10; mask20 = x & bit20; result = (mask10 << 21) | (mask20 << 10);
それでは、このシーケンスを別の方法で見てみましょう。 第一に、最後の行のOR演算は追加で簡単に置き換えることができます：オーバーフローは私たちの生活を台無しにしません。 第二に、OR記号をプラスに置き換えた後、最後の行の式は疑わしく乗算に似ています。 確かに
(x << 21) + (x << 10) == x * 0x00100400
mask10とmask20は1つのxから取得されるため、例を次の形式にできます。
bit10 = 1 << 10; bit20 = 1 << 20; mask = x & (bit10 | bit20); result = mask * 0x00100400;
ゴミが他のビットに残る可能性があることに注意を払わなければ、これは機能します。
まとめると。 空の星が成功した場合、AND演算と乗算により、指定されたビットを高い位置に転送できます。 そして、うまくいかないかもしれません。 この例では、10と20の数字のビットは互いに遠くにあり、加算の結果は結果の31番目と30番目のビットに影響を与えることはありません。
メソッドが失敗するのはいつですか？ 4番目のビットを7番目に、2番目のビットを6番目に、0番目から5番目に転送するとします。 この場合、マジック定数は0x38の形式を取り、3つのビットが設定されます：5番目（5番目のシフト）、5番目、3番目。 しかし、問題は、乗算を実装しようとすると、ビットが互いにオーバーラップすることです。
* 10101
111,000
--------
10101000
101010000
1010100000
-----------
???
そのような迷惑を回避する方法は？ 解決策は、ビットの別の順列を試すことができるということです。 たとえば、4→6、2→7、0→5。 この場合、マジック定数は0x24の形式を取り、2ビットのみが設定されます。これは、2番目と0ビットが同じ値だけシフトする必要があるためです。
* 10101
100100
--------
1010100
1010100000
----------
..111 .....
これはチェッカービットボードにとって何を意味しますか？ 対角線は7つありますが、運が良ければ、ビットの順列を見つけることができるので、マジック定数を掛けると各ビットが適切な場所に転送され、何も損なわれません。 しかし、このためには、そのような定数を見つけるだけでなく、質問への回答を保存する魔法の配列を形成する別の検索プログラムを作成する必要があります、キャプチャすることができるかどうか、どのチェッカーが殺されるか、キャプチャ後に女性が行くことができるフィールド）
おわりに
もちろん、ムーブのリストを生成するとき、技術的な問題が依然として発生する可能性があります。 たとえば、殺害されたチェッカーがストライキの完了後にのみボードから削除される場合、 トルコのストライキを忘れてはなりません。 しかし、それらはすべて技術的な性質のものです。 この記事では、マジックビットマスクを使用した移動ジェネレーターの実装を紹介する小さなケーススタディを実装しました。 checkers-0.1.tar.bz2で言えます。