3

私はチェス盤の表現に取り組んでおり、32 バイト配列に格納する予定です。各バイトは 2 つの駒を格納するために使用されます。(この方法では、ピースごとに必要なビットは 4 つだけです)

そのようにすると、ボードの特定のインデックスにアクセスするためのオーバーヘッドが発生します。このコードを最適化できると思いますか、またはインデックスにアクセスするためのまったく異なる方法を使用できますか?

c++

char getPosition(unsigned char* c, int index){
    //moving pointer
    c+=(index>>1);

    //odd number
    if (index & 1){
        //taking right part
        return *c & 0xF;
    }else
    {
        //taking left part
        return *c>>4;
    }
}


void setValue(unsigned char* board, char value, int index){
    //moving pointer
    board+=(index>>1);

    //odd number
    if (index & 1){
        //replace right part
                 //save left       value only 4 bits
        *board = (*board & 0xF0) + value;
    }else
    {
        //replacing left part
        *board  = (*board & 0xF) + (value<<4);
    }
}


int main() {

    char* c = (char*)malloc(32);

    for (int i = 0; i < 64 ; i++){
        setValue((unsigned char*)c, i % 8,i);
    }

    for (int i = 0; i < 64 ; i++){
        cout<<(int)getPosition((unsigned char*)c, i)<<" ";

        if (((i+1) % 8 == 0) && (i > 0)){
            cout<<endl;
        }


    }


    return 0;
}

独立した問題として、チェスの表現と上記の方法の最適化に関するあなたの意見にも同様に興味があります.

どうもありがとう

編集

返信ありがとうございます。少し前に、64 バイトのボード表現を使用していたチェッカー ゲームを作成しました。今回は、自分の好みを確認するために、いくつかの異なる方法を試しています。メモリはそれほど大きな問題ではありません。ビットボードは間違いなく私のリストに載っています。ありがとう

4

6 に答える 6

9

それが時期尚早の最適化の問題です。チェス盤の保存に 64 バイトかかっていたところを、今では 32 バイトにしています。その記憶を保存する必要があるかどうか、実際に状況を分析しましたか?

最も最適でない検索方法の 1 つを使用し、ヒューリスティックを使用せずに深さ D までストレート AB 検索を使用し、検索前に位置で可能なすべての動きを生成すると仮定すると、ボードに必要な絶対最大メモリは sizeof(board) になります。 * W * D. かなり大きな W = 100 と大きな D = 30 を想定すると、深さ D でメモリに 3000 枚のボードが格納されることになります。

一方、board[location] にアクセスするために必要な操作の量が増えたため、これは検索ごとに何百万回も呼び出されます。

チェスの AI を構築するとき、主に探すことになるのはメモリではなく CPU サイクルです。携帯電話などをターゲットにしている場合、これは少し異なる場合がありますが、それでも、メモリの問題を引き起こすのに十分な深さに達する前に、速度についてもっと心配する必要があります.

どちらの表現が好きかというと…ビットボードが好きです。多くの本格的な測定は行っていませんが、私が作成した 2 つのエンジン (ビットボードとアレイ) を比較しました。

于 2010-04-16T20:40:11.043 に答える
3

潜在的なバグを最初に指摘させてください (コンパイラとコンパイラの設定によって異なります)。そしてバグは時期尚早の最適化が悪である理由です:

   //taking left part
    return *c>>4;

*c が負の場合、>> は負の上位ビットを繰り返す可能性があります。つまり、バイナリで：

0b10100000 >> 4 == 0b11111010

一部のコンパイラの場合 (つまり、C++ 標準では、上位ビットを運ぶかどうか、および char が符号付きか符号なしかの両方の決定をコンパイラに任せています)。

パックされたビットを先に進めたい場合 (そして、おそらく気にする必要はありませんが、それはあなた次第です)、パックされたビットをクラスにラップし、 [] をオーバーライドすることをお勧めします。

board[x][y]

アンパックされたビットを提供します。次に、パッキングのオンとオフを簡単に切り替えることができ、どちらの場合も同じ構文を使用できます。演算子のオーバーロードをインライン化すると、現在のコードと同じくらい効率的になります。

于 2010-04-16T21:28:21.087 に答える
2

64 バイトは非常に少量の RAM です。char[8][8] だけを使用したほうがよいでしょう。つまり、大量のチェス盤を保管する予定がない限り. char[8][8] を実行すると、ボードにアクセスしてより複雑な操作を実行するのが簡単 (かつ高速) になります。

ボードをパック表現で保存することにまだ興味がある場合 (練習用または多くのボードを保存するため)、ビット操作に関しては「正しく行っている」と言えます。inlineキーワードを使用して速度を上げる場合は、アクセサーをインライン化することを検討してください。

于 2010-04-16T20:32:24.483 に答える
0

チェス プレーヤーとして、私はあなたに言うことができます: 位置には、各駒の単なる配置以上のものがあります。他にもいくつかのことを考慮する必要があります。

  1. 次に動かなければならないのはどちらの側か？
  2. 白と/または黒のキャッスルキングと/またはクイーンサイドはできますか?
  3. ポーンを途中で取ることはできますか?
  4. 最後のポーンの移動および/またはキャプチャの移動から何回の移動が経過しましたか?

位置を表すために使用するデータ構造がこの情報を反映していない場合、大きな問題が発生します。

于 2010-04-16T21:28:33.493 に答える
0

正方形を表すのに 1 バイトだけを使用できない場合、十分なスペースを考慮する必要がありますか? これにより、プログラムでアクセスを追跡しやすくなり、ビット操作が不要になるため、さらに高速になる可能性があります。

それ以外の場合、すべてがスムーズに進むようにするには、すべての型が符号なしであることを確認します。ほとんどの場合、signed-ness に問題はありませんが、予期しない動作をするアーキテクチャに賭ける必要はありません。

于 2010-04-16T20:37:08.783 に答える
0

素晴らしいコードですが、パフォーマンスの最適化に本当に深く取り組んでいる場合は、特定の CPU アーキテクチャについてもっと学ぶ必要があります。

私の知る限り、チェスの駒を 8 バイト程度に格納する方が効率的であることがわかるかもしれません。15 移動深く再帰しても、L2 キャッシュ サイズはほとんど制約になりませんが、RAM のミスアライメントは. チェス盤の適切な処理には、アルゴリズムのさまざまな部分でボードの表現を変換するための Expand() および Reduce() 関数が含まれると思います。コンパクトな表現の方が高速な場合もあれば、その逆の場合もあります。たとえば、キャッシング、および隣接する 2 つのセルの構成によるハッシュを含むアルゴリズムは、コンパクトな構造に適している可能性があります。

パフォーマンスが非常に重要な場合は、FPGA ボードや GPU コードなどのヘルパー ハードウェアの開発も検討します。

于 2010-04-16T20:38:20.190 に答える