4

私はチェスエンジンの作成を開始しています。ある手が正しいかどうかをチェックする関数を作成したとき、最初に手を取ってから、その手でキングがチェックされたかどうかを確認し、それから解除する必要がありました。

手を動かさない機能を作る方法を考えた後、ボードをコピーして、コピーしたボード上で仮想の動きをする方がはるかに簡単で、元のボード構造をまったく変更しないことにしました。

しかし、AI 部分に到達すると、ボードを完全にコピーする必要があり、エンジンの速度が低下する可能性があるため、これは悪い考えではないかと心配しています。そうですか？私はアルゴリズムの複雑さなどについてよく知らないので、これについての考えを教えてください。

ありがとうございました。

4

2 に答える 2

5

一般に、ボードの不必要なコピーを避けるため、unmake アプローチがより多く使用されます。Positionこれは、クラスで作品を 2 つの異なる形式で保持したい場合に特に当てはまります。従来の 8x8 配列として、および 64 ビットの符号なし整数 (ビットボード) のセットとして。

UnmakeMoveInfowhich を保持するクラスを作成する必要があります。

  • 移動の開始/終了。
  • 前の位置ハッシュ。
  • 「ハーフムーブクロック」。
  • アンパッサンマスク。
  • キャプチャされたピース。
  • 以前の位置フラグ (チェック、ep_move、キャスリング権)。

そのため、動きを元に戻すために必要なすべての情報が得られます。

于 2012-07-26T12:00:10.263 に答える
5

あなたが言うように、ボード全体をコピーすると、処理がかなり遅くなる可能性があります。元に戻すリストを作成して、実行したすべての動きの逆を追加することをお勧めします。次に、元に戻すには、リストから移動を繰り返しポップし、リストが空になるまで適用します。このようにして、AI は maxdepth パラメーターを指定した単純な再帰関数を使用して、すべての可能性を探索できます。

Re: ボーのコメント

私は丁重に反対します。

低レベル言語で書かれたプログラムの場合、ボードのコピーは 1 つの memcpy になる可能性があり、その場合は非常に高速になる可能性があります。しかし、チェスの駒ごとに 1 つのオブジェクトとメタデータがあるオブジェクト指向の Python プログラムの場合、完全に独立したゲーム状態のコピーは、単一の新しい「元に戻す」オブジェクトを作成してリストに追加するよりも、ほぼ確実にはるかに遅くなります。

これは構造体のサイズとはほとんど関係がなく、その構造体をコピーするために必要な操作の数とは関係ありません。特に Python では、関数呼び出しによってかなりの量のオーバーヘッドが追加されます。この回答 (私自身) によると、CPython で 32 個のオブジェクトをインスタンス化することは、83 回の関数呼び出しに相当し、. 以外のサブクラスがないことを前提としていますobject。次に、データの割り当てとコピーがその上に来ます。

ボードが 16x16 numpy 配列であった場合、ボード コピーの方が高速であることに同意します。

于 2012-07-26T11:58:39.167 に答える