5

キラーヒューリスティックの背後にある考え方と、それが役立つ理由を理解しています。私が苦労しているのは、アルファベータ検索ルーチンでそれを実装する方法です。特に、兄弟ノードのキラー ムーブのみが最初に試行されるようにするにはどうすればよいでしょうか? 擬似コードは非常に役立ちます。

4

2 に答える 2

7

実装について説明します。兄弟ノードのキラーな動きを得るには、このようなスキームを使用します

killerMoves[ply][slot]

ここplyで、 はルートからの距離 (検索の深さではありません) でslotあり、必要なキラー ムーブの数です。これにより、兄弟ノードが同じ層にあるため、兄弟ノードが最初に試行されます。

ベータ カットオフを取得したときにキラー ムーブを挿入するには、指定されたプライのムーブを右にシフトし、おそらく古いムーブを破棄してから、新しいムーブを挿入します。通常、キャプチャまたはハッシュ ムーブは、他のメカニズムを通じて順序付けられるため、キラー ムーブとして保存しません。

for (int i = killerMoves[ply].Length - 2; i >= 0; i--) 
    killerMoves[ply][i + 1] = killerMoves[ply][i];
killerMoves[ply][0] = move;

これで、移動の順序付けを (移動リストを反復処理する前に) 実行しているときに、移動がキラー移動かどうかを判断できます。

for (int slot = 0; slot < killerMoves[ply].Length; slot++) {
    int killerMove = killerMoves[ply][slot];

    for (int i = 0; i < movesCount; i++)
        if (moves[i] == killerMove) {
            // moves[i] is a killer move so move it up the list
            break;
    }
}

プライなどのキラー ムーブをクリアする必要はありません。キラー ムーブは、同じプライで発生する同様の位置の範囲にわたる適切なムーブである可能性が非常に高いためです。

他の答えがそれをもたらしたので、キラーヒューリスティックは理論的には健全であるため、厳密なテストを実行する必要はないかもしれません. 使用するキラー ムーブの数 (2 または 3 が標準) と、キャプチャなどの他の優れたムーブとの相対的な順序を試すことができます。

于 2013-07-17T17:15:44.990 に答える
0

キラー ムーブは、検索ツリーの多くの部分で適切な反駁のムーブになる可能性があります。したがって、他のポジションでキラームーブを試すのは良い考えかもしれません。

プライごとに異なるキラー ムーブの配列があり、(プライ) に入るときに (プライ + 1) の配列をクリアすると、「兄弟のみ」のキラーが得られます。'+1' オフセットは調整するパラメータのようなものだと思います: 代わりに (ply+N) の配列をクリアしてみて、パフォーマンスが最高の場所を確認してください (N を増やすと改善されると思います)。

ところで、エンジンのパフォーマンスの評価は、かなりリソースを消費する別のタスクです。通常、エンジンはテスト スイートを解決しようとするか、異なるパラメーターを持つ 2 つのエンジンがそれらの間でマッチ (マッチは十分な長さ、たとえば 100 ゲーム) を行います。どちらが優れているかを判断します。

于 2013-07-17T07:22:07.823 に答える