ノードタイプは、alpha-beta / PVS 探索において各ノードがどのような役割を持つかを分類する考え方である。
特に PV-node、Cut-node、All-node の区別が重要である。
Knuth と Moore に由来する分類では、
という見方をする。
この分類は、
を考えるうえで役に立つ。
PV-node では最善手列上の正確な値が必要なので、
といった扱いをすることが多い。
Cut-node は、ある 1 手が beta を超えれば十分なノードである。
そのため、
といった特徴がある。
All-node は、すべての手が alpha を超えないことを確認する側のノードである。
cut は起きにくいので、探索量が増えやすい。
そのため、quiet move の reduction や pruning が効く余地が大きい。
実装ではノードタイプを明示的な enum で持たないことも多いが、
から暗黙に扱いを変えていることが多い。
将棋AIでは選択的探索の分岐が多いため、 「このノードは正確値が必要か、それとも cut を期待するか」を意識すると設計が整理しやすい。
たとえば、
といった調整方針が取りやすくなる。