キラーヒューリスティック

競争的な 2 人用ゲームでは、キラー ヒューリスティックとは、特定の位置での強い動き、またはそのような動きの小さなセットが、ゲーム ツリー内の同じ動き (プライ) の同様の位置でも同様に強い可能性があるという観察に基づく動きの順序付け方法です。そのような動きを保持しておくと、兄弟ノードでそれらを再発見する手間が省けます。

この手法はアルファベータ剪定の効率を改善し、ひいてはミニマックスアルゴリズムの効率を改善します。^[1] アルファベータ剪定は、最善の手を最初に考慮する場合に最も効果的です。これは、最善の手がカットオフを生み出す可能性が最も高い手であるためです。カットオフとは、ゲームプレイプログラムは、検討しているポジションが両側の最善のプレイからは生じ得ないことを知っているため、それ以上検討する必要がない状態です。つまり、ゲームプレイプログラムは常に、各ポジションに対して利用可能な最善の手を行います。その最善の手に対する他のプレーヤーの可能な応答のみを考慮する必要があり、行わない（より悪い）手に対する応答の評価をスキップできます。

キラー ヒューリスティックは、同じ深さのゲーム ツリーの別のブランチでカットオフを生成した動きが、現在の位置でもカットオフを生成する可能性が高いと想定して、カットオフを生成しようとします。つまり、別の (ただし、類似している可能性もある) 位置から非常に良い動きだった動きが、現在の位置でも良い動きである可能性があるということです。他の動きの前にキラー ムーブを試すことで、ゲーム プレイ プログラムは多くの場合、早い段階でカットオフを生成でき、位置からのすべての有効な動きを検討したり、生成したりする手間を省くことができます。

実際の実装では、ゲーム プレイ プログラムは、ゲーム ツリーの各深さ (深さ 1 より大きい) について 2 つのキラー ムーブを追跡することが多く、これらのいずれかのムーブが合法である場合、プログラムが残りの可能なムーブを生成して検討する前に、カットオフを生成するかどうかを確認します。キラーでないムーブがカットオフを生成する場合、その深さにある 2 つのキラー ムーブのいずれかを置き換えます。このアイデアは、反駁表のセットに一般化できます。

キラーヒューリスティックの一般化は、履歴ヒューリスティックです。^[2]履歴ヒューリスティックは、移動の特徴、たとえば「開始」と「終了」のマス目、または駒の移動と「終了」のマス目によってインデックスが付けられたテーブルとして実装できます。カットオフが発生すると、テーブル内の適切なエントリが、たとえばdまたはd² ( dは現在の検索の深さ) を追加するなどして増加します。

• ネガスカウト

• 複雑なゲームにおける情報に基づいた検索 (Mark Winands 著)
• キラーヒューリスティックチェスプログラミングWiki