10

私は現在、駒を配置できる（つまり、元々ボード上にない）チェスバリアントエンジンの転置テーブルをデバッグしています。キーの衝突が発生する頻度を知る必要があります。通常のハッシュデータとともに、各テーブルインデックスにピースリストを保存しています。2つのピースのリストを線形に比較しているため、2つの位置が等しいかどうかを判断するための簡単な解決策は、転置に失敗することです。

ピースセントリックではなくボードセントリックで保管することを提案しないでください。配置可能でキャプチャされたピースのユニークな性質のため、ピースリストを保存する必要があります。これらの州の作品は、重なり合って位置のない場所を占めているようなものです。ピースの保管方法の説明をご覧ください。

// [Piece List]
// 
// Contents: The location of the pieces.
//           Values 0-63 are board indexes; -2 is dead; -1 is placeable
// Structure: Black pieces are at indexes 0-15
//            White pieces are at indexes 16-31
//            Within each set of colors the pieces are arranged as following:
//            8 Pawns, 2 Knights, 2 Bishops, 2 Rooks, 1 Queen, 1 King
// Example: piece[15] = 6 means the black king is on board index 6
//          piece[29] = -2 means the white rook is dead
char piece[32];

移調は、ピースが異なる順序で移動されたときに発生しますが、最終的には同じボード位置になります。たとえば、次の位置は同じです。

1) first rook on A1; second rook on D7
2) first rook on D7; second rook on A1

以下は、最適化されていない一般的なアルゴリズムです。内側のループは別の一般的な問題に似ていますが、0〜63の値が1回だけ発生するという制限が追加されています（つまり、正方形ごとに1つだけ）。

for each color:
    for each piece type:
        are all pieces in the same position, disregarding transpositions?

次の比較は、転置のために機能しません。私が必要としているのは、転置を等しいものとして検出し、実際には異なる位置のみを報告する方法です。

bool operator==(const Position &b)
{
    for (int i = 0; i < 32; i++)
        if (piece[i] != b.piece[i])
            return false;
    return true;
}

テーブルは1ターンあたり100Kヒット（キーが等しい場合）を超え、通常のテーブルには100万のアイテムがあるため、パフォーマンス/メモリが考慮されます。今後は、リストをコピーして並べ替えるよりも速いものを探しています。

4

7 に答える 7

8

コンピュータチェスについては多くの研究が行われており、位置の一意のハッシュを作成する方法は、事実上すべてのチェスエンジンで使用されるユニバーサルソリューションのよく知られた問題です。

あなたがする必要があるのは、 Zobrist Hashingを使用して、異なる位置ごとに一意の（実際には一意ではありませんが、これが実際には問題にならない理由を後で説明します）キーを作成することです。ここでは、チェスに適用されるアルゴリズムについて説明します。

プログラムを開始すると、ゾブリストキーと呼ばれるものが作成されます。これらは、各ピース/平方ペアの64ビットのランダムな整数です。Cでは、次のような2次元配列があります。

unsigned long long zobKeys[NUMBER_OF_PIECES][NUMBER_OF_SQUARES];

この各キーは、適切な乱数ジェネレーターで初期化されます（警告：gccまたはVC ++で提供される乱数ジェネレーターは十分ではありません。MersenneTwisterの実装を使用してください）。

ボードが空の場合は、ハッシュキーを任意に0に設定します。次に、ボードにピースを追加する場合、たとえばA1のルークを追加する場合は、ハッシュキーを使用してA1のルークのゾブリストキーをXORすることによってハッシュキーも更新します。ボードの。このように（Cで）：

boardHash = boardHash ^ zobKeys[ROOK][A1];

後でこの正方形からルークを削除する場合は、今行ったことを元に戻す必要があります。XORは再度適用することで元に戻すことができるため、ピースを削除するときに同じコマンドをもう一度使用できます。

boardHash = boardHash ^ zobKeys[ROOK][A1];

ピースを移動する場合、たとえばA1のルークがB1に移動した場合、2つのXORを実行する必要があります。1つはA1のルークを削除し、もう1つはB2のルークを追加します。

boardHash = boardHash ^ zobKeys[ROOK][A1] ^ boardHash ^ zobKeys[ROOK][B1];

このように、ボードを変更するたびに、ハッシュも変更します。とても効率的です。ボード上のすべてのピースに対応するzobKeysをxorすることで、毎回スクラッチからハッシュを計算することもできます。また、通過できるポーンの位置と両側のルーキング機能のステータスをXORする必要があります。同じように、可能な値ごとにzobrisキーを作成します。

このアルゴリズムは、各位置に一意のハッシュがあることを保証するものではありませんが、優れた疑似乱数ジェネレーターを使用すると、衝突が発生する可能性が非常に低いため、エンジンに一生プレイさせても、実質的にチャンスはありません。これまでに発生した衝突の。

編集：私はあなたがオフボードのピースを持っているチェスの変則のためにこれを実装しようとしていることを赤くしました。Zobristハッシュは依然としてあなたにとって正しい解決策です。これらの情報をハッシュに組み込む方法を見つける必要があります。たとえば、オフボードのピースにいくつかのキーを設定できます。

unsigned long long offTheBoardZobKeys[NUMBER_OF_PIECE][MAXIMUM_NUMBER_OF_ON_PIECE_TYPE];

ボードから2つの足があり、このポーンの1つをa2に置く場合、2つの操作を行う必要があります。

// remove one pawn from the off-the-board
boardHash = boardHash ^ offTheBoardZobKeys[WHITE_PAWN][numberOfWhitePawsOffTheBoard];

// Put a pawn on a2
boardHash = boardHash ^ zobKeys[WHITE_PAWN][A2];
于 2010-10-08T12:51:51.403 に答える
6

チェス盤のレイアウトに対応する64バイトの文字列をデータベースに保持してみませんか？「ピースなし」を含むすべてのタイプのピースは文字を表します（両方の色で異なるキャップ、つまり黒の場合はABC、白の場合はabc）。ボードの比較は、単純な文字列の比較に要約されます。

一般に、ピースの観点ではなく、チェス盤の観点から比較すると、転置の問題が解消されます。

于 2010-10-08T08:43:53.400 に答える
4

「ピース中心ではなくボード中心で保管することを提案しないでください」。

あなたはそれをしないことに集中しているので、明白な解決策を見逃しています。ボード固有を比較します。L12つの位置リストとを比較するにはL2、のすべての要素をL1（一時的な）ボードに配置します。次に、の各要素についてL2、それが一時的なボードに存在するかどうかを確認します。L2の要素がボード上（したがってL1）に存在しない場合は、等しくない値を返します。

のすべての要素を削除した後L2もボードに残っている部分がある場合は、L1要素が存在しない必要がL2あり、リストは同じです。その後、一時ボードが空になった場合にのみ等しくなりますL1。L2

最適化は、最初にL1との長さをチェックすることです。L2これにより、多くの不一致がすぐに検出されるだけでなく、L2ボードからの要素を削除する必要がなくなり、最後に「空のボード」チェックが行われます。L1これは、がの真のスーパーセットである場合をキャッチするためにのみ必要ですL2。L1とL2が同じサイズでありL2、のサブセットである場合L1、L1とL2は等しくなければなりません。

于 2010-10-08T12:01:45.737 に答える
3

ボードごとに状態を保存することへのあなたの主な反対は、あなたが位置のない部分のバッグを持っているということです。ボードとピースのベクトルを維持してみませんか？これはあなたの要件を満たし、あなたの州の標準的な表現であるという利点があります。したがって、並べ替えは必要ありません。この表現を内部で使用するか、比較する必要があるときに変換します。

Piece-type in A1
... 63 more squares
Number of white pawns off-board
Number of black pawns off-board
... other piece types
于 2010-10-08T12:58:27.737 に答える
1

そして3番目のオプション（1つの質問に3つの回答を投稿しても大丈夫です、stackoverflowに関して;））：

常に同じタイプのピースをインデックス順に保持します。つまり、リストの最初のポーンは常に最も低いインデックスを持つ必要があります。これを破る動きが起こった場合は、リスト内のポーンの位置を反転するだけです。使用法では違いはわかりません。ポーンはポーンです。

これで、位置を比較するときに、転置の問題がなく、提案されたforループを使用できることを確認できます。

于 2010-10-08T09:15:54.837 に答える
1

ピースの観点から、これを行うことができます：

for each color:
    for each piece type:
        start new list for board A
        for each piece of this piece type on board A
            add piece position to the list
        start new list for board B
        for each piece of this piece type on board B
            add piece position to the list
        order both lists and compare them

最適化にはさまざまな方法があります。あなたの利点は次のとおりです。違いに気づいたらすぐに：完了です！

たとえば、両方のボードについて、すべてのピースのすべてのインデックスを合計することで、すばやくダーティなチェックを開始できます。合計は等しくなければなりません。そうでない場合は、違いがあります。

合計が等しい場合は、ユニークなピース（キングとクイーン）の位置をすばやく比較できます。次に、ペアになっている部分の比較を（やや複雑なifステートメントで）書き出すことができます。次に行う必要があるのは、上記の方法を使用してポーンを比較することだけです。

于 2010-10-08T09:10:16.427 に答える
1

ゲームの状態表現を選択した場合、黒のポーンのインデックス、白のポーンのインデックスなどをいずれかの方法で並べ替える必要があります。新しいゲーム状態を作成する過程でそれを行わない場合は、比較時にそれを行う必要があります。最大8つの要素を並べ替えるだけでよいため、これは非常に高速に実行できます。

ゲームの状態を表すためのいくつかの選択肢があります。

  • 各タイプのピースをビットフィールドとして表します。最初の64ビットは、そのボード座標にこのタイプのピースがあることを意味します。次に、nビットの「配置可能」スロットとnビットの「デッド」スロットがあり、片側から埋める必要があります（nはこのタイプのピースの数です）。

また

  • 各タイプのピースに一意のIDを付けます。たとえば、白いポーンは0x01である可能性があります。ゲームの状態は、64個のピース​​（ボード）の配列と、「配置可能」および「デッド」ピースの2つの順序付けられたリストで構成されます。これらのリストの順序を維持することは、挿入および削除時に非常に効率的に行うことができます。

これらの2つの選択肢には、移調の問題はありません。

とにかく、最初にそれを機能させる必要があるときに、マイクロ最適化をいじっているような印象があります。

于 2010-10-08T11:50:24.107 に答える