4

私はチェス エンジンに取り組んでおり、現在、転置テーブル (過去の動きから既に評価されたボードの位置のセット) を実装しています。一般的な考え方は、移動が行われると、転置テーブルで一致する位置を確認するというものです。存在する場合は、コストのかかる評価プロセスをスキップして、以前に計算された結果を転置テーブルから取得するだけです。存在しない場合は、必要な計算を行い、後で参照できるように転置表に追加します。

私には、これはハッシュセットまたは辞書の仕事のように思えます。私は辞書に決めました。キーを自分のボードを表すクラスにし、値をその位置に遭遇した回数の int カウントにしたいと考えました。カウントの理由は、3 回の反復ドローを検出できるようにするためです。同じポジションが 3 回以上発生した場合、プレーヤーは引き分けをコールするオプションがあります。ハッシュセットの代わりに辞書を使用すると、転置テーブルと組み合わせることで、3 回繰り返し描画の検出を大幅に簡素化できます。

これを行うために、ボードの状態オーバーライド Equals() と GetHashCode() を表すクラスを作成しました。それは問題なく動作し、ゲームが以前に遭遇したすべての履歴状態を追跡できるようになりました.

私の問題は、辞書内のキー オブジェクトのプロパティにアクセスできる必要があることです。(.ContainsKey(...) メソッドと Equals()/GetHashCode() ロジックを使用して) 一致が存在するかどうかを確認できますが、前述の計算値をプルする必要があります (ボードのパブリック プロパティとして保存されます)。キーからの状態オブジェクト)。

私は思いつくことができました：

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.GetHashCode() == this.GetHashCode());

これは機能しますが、私には不格好に感じます。転置テーブルの要点は、何百万もの連続するボード状態の再帰的検索を高速化することです。一致ごとに辞書を照会することは、直感に反するように思えます。これを行うより良い方法はありますか？

編集：

指摘されているように、有効なボードの状態が膨大にあるため、私のハッシュは完全ではありませんでした。私の Equals() オーバーライドは、衝突の可能性を減らすために、代替的に生成された 2 番目のハッシュをチェックします。上記の「ソリューション」には、不完全なハッシュに依存しているため、欠陥があります。私は使用する必要がありました：

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.Equals(this));

私の愚かな見落とし。それでも、私は辞書を照会するファンではありません。

4

1 に答える 1

2

1 つのオプションは、次のように、ディクショナリの値とディクショナリの実際の値のキーへの参照を保持することです。

Dictionary<BoardState, Tuple<BoardState, int>>

次に、オブジェクトを追加するたびに、キーと同じオブジェクトを値に追加します。

Dictionary<BoardState, Tuple<BoardState, int>> boards = 
    new Dictionary<BoardState,Tuple<BoardState,int>>();
BoardState board = new BoardState();
boards.Add(board, Tuple.Create(board, 1));

もう 1 つのオプション (おそらくより適切な設計) は、ボード状態オブジェクトを 2 つの異なるタイプに分割することです。ボードの状態を実際に表すもの (これは不変である必要があります) と、その状態に関するその他の情報 (発生時刻や特定のアプリケーションに適用されるその他の可変属性を含む) を保持するものがあります。これにより、辞書キーにアクセスする必要がなくなります。

于 2013-02-11T17:57:54.950 に答える