主変化探索

主変化探索はPVSと略され、手が適切に並んでいれば最初の候補が最善である可能性が高い、という期待から始まる。最初の手には完全探索を行う。後続の手には、すでに得た結果を上回れるか判断するため、まず低コストな試験を行う。

低コストな試験は狭いウィンドウを使う。ウィンドウとは、探索が区別する必要のある値の範囲である。手がどれほど良いか悪いかを正確に求める代わりに、PVSは最初に、現在の基準を上回るかどうかだけを問う。上回らなければ、完全探索なしでその手を退けられる。

後続候補が基準を上回るように見えた場合、狭い試験だけでは正確な値を確定できない。局面を分析するプログラムであるエンジンは、完全なウィンドウでもう一度探索する。この2回目の処理を再探索と呼び、手法の正しさを保つ一方、時間を消費する。そのためPVSは、手の順序付けが成功し、最善の選択が最初に現れると最も効果を上げる。

PVSは、判断を改善できないとすでに証明された枝を放棄するアルファベータ探索を、ミニマックスの枠組み内で効率的に構成する方法である。エンジンが現時点で最善と見る手順にすぎない主変化そのものと混同してはならない。MultiPVとも異なる。MultiPVは複数の開始ラインを求めるが、PVSは内部探索の手法を表す。