ゲーム理論において、ヌルムーブまたはパスとは、プレイヤーが自分の番に着手しないという決定を指します。ヌルムーブは多くのゲームではルール違反ですが、これらのゲームを分析する際には考慮すると有用です。例としては、ツークツヴァング（チェスなどのゲームにおいて、ヌルムーブが許可されていれば他のどの手よりも優れている状況）[1]や、ゲームツリー分析におけるヌルムーブヒューリスティック（ヌルムーブを行ってからより深い階層まで探索するゲームツリーの枝刈り手法）[2]などが挙げられます。
深さを縮小したヌルムーブがゲームツリーのアルファベータ探索削減に効果的な理由は、戦術的脅威が1～2手で非常に早く現れる傾向があるためです。ヌルムーブ探索によって対戦相手に戦術的脅威が見つからなかった場合、その局面はツリーの別の枝で得られる最良の結果（つまり「ベータ」）を超えるほど優れている可能性があり、現在のノードからそれ以上の探索を行う必要はなく、ヌルムーブの結果を探索値として返すことができます。ヌルムーブ探索値がベータを超えない場合でも、返された値は現在のアルファよりも局面の評価の下限を高く設定する可能性があるため、その局面から子孫の兄弟ノードでより多くのカットオフが発生します。
根底にある前提は、プレイヤーがノードで着手する際に、少なくとも何らかの合法的な手が使える方が、全く着手しないよりはましだということです。プレイヤーがツークツヴァング状態にある場合、この前提は誤りであり、ヌル手の結果は無効です（この場合、ヌル手は実際にはポジションの値に上限を設定します）。したがって、ツークツヴァングが可能なツリー内のノードでは、ヌル手を排除するロジックが必要です。チェスでは、ツークツヴァングポジションはキングとポーンのエンドゲームで発生する可能性があり、他の駒も含まれるエンドゲームでも発生することがあります。
参考文献
- ^ Beal, Don F. (1990)、「一般化された静止探索アルゴリズム」、人工知能、43 (1): 85– 98、doi :10.1016/0004-3702(90)90072-8。
- ^ Goetsch, G.; Campbell, MS (1990)、「ヌルムーブヒューリスティックの実験」、Marsland, T. Anthony; Schaeffer, Jonathan (編)、『コンピュータ、チェス、認知』、Springer-Verlag、pp. 159– 168。
