ヌルムーブ

ゲーム理論では、ヌルムーブまたはパスとは、プレイヤーが自分の番になったときに手を打たないという決定です。ヌルムーブは多くのゲームのルールに反しますが、これらのゲームを分析する際に考慮すると役立つことがよくあります。この例としては、ツークツヴァング（チェスやその他のゲームで、ヌルムーブが許可されていれば、他のどの手よりも優れている状況）の分析^[1]や、ゲームツリー分析におけるヌルムーブヒューリスティック（ヌルムーブを行ってからより深いところまで検索するゲームツリーの剪定方法） ^[2]などがあります。

深さを減らしたヌルムーブがゲームツリーのアルファベータ検索削減に効果的な理由は、戦術的脅威が 1 つか 2 つの動きで非常に早く現れる傾向があるためです。ヌルムーブ検索によって対戦相手に戦術的脅威がない場合は、そのポジションはツリーの別のブランチで得られる最良の結果 (つまり「ベータ」) を超えるほど十分に優れている可能性があるため、現在のノードからさらに検索を行う必要はなく、ヌルムーブの結果を検索値として返すことができます。ヌルムーブ検索値がベータを超えない場合でも、返された値は現在のアルファよりもポジションの評価の下限を高く設定する可能性があるため、そのポジションから子孫の兄弟ノードでより多くのカットオフが発生します。

基本的な仮定は、ノードでプレイヤーが移動する際に、少なくとも何らかの合法的な移動が可能である方が、まったく移動しないよりも良いということです。移動中のプレイヤーがツークツヴァング状態にある場合、この仮定は誤りであり、ヌル移動の結果は無効です (その場合、実際にポジションの値に上限が設定されます)。したがって、ツークツヴァングが可能なツリーのノードでヌル移動を除外するロジックが必要です。チェスでは、ツークツヴァング ポジションはキングとポーンのエンドゲームで発生する可能性があり、他の駒も含まれるエンドゲームでも発生することがあります。