# ノードタイプ ノードタイプは、alpha-beta / PVS 探索において各ノードがどのような役割を持つかを分類する考え方である。 特に `PV-node`、`Cut-node`、`All-node` の区別が重要である。 ## 概要 Knuth と Moore に由来する分類では、 - PV-node 正確値を求めたいノード - Cut-node どれか 1 手で cut が起これば十分なノード - All-node 全手を見ても境界を超えないことを確かめたいノード という見方をする。 この分類は、 - どこで選択性を弱めるか - どこで reduction を強めるか - どこで並列化を行うか を考えるうえで役に立つ。 ## PV-node `PV-node` では最善手列上の正確な値が必要なので、 - 探索窓を広く取る - [LMR](/shogi/shogiwiki/search/late-move-reductions/)を弱める - [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)を控える といった扱いをすることが多い。 ## Cut-node `Cut-node` は、ある 1 手が `beta` を超えれば十分なノードである。 そのため、 - [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が特に重要 - [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)が効きやすい - [YBWC](/shogi/shogiwiki/search/young-brothers-wait-concept/)とも相性が良い といった特徴がある。 ## All-node `All-node` は、すべての手が `alpha` を超えないことを確認する側のノードである。 cut は起きにくいので、探索量が増えやすい。 そのため、quiet move の reduction や pruning が効く余地が大きい。 ## 実装との関係 実装ではノードタイプを明示的な enum で持たないことも多いが、 - 窓の形 - 親から見た期待 - fail-high / fail-low の文脈 から暗黙に扱いを変えていることが多い。 ## 将棋AIでの位置づけ 将棋AIでは選択的探索の分岐が多いため、 「このノードは正確値が必要か、それとも cut を期待するか」を意識すると設計が整理しやすい。 たとえば、 - PV-node は安全重視 - Cut-node は高速化重視 といった調整方針が取りやすくなる。 ## 注意点 - 期待ノードタイプと、探索後に実際どうなったかは一致しないこともある - [PVS](/shogi/shogiwiki/search/principal-variation-search/)や再探索で文脈が変わることがある - 厳密な分類よりも、実装上の挙動差を理解するための概念として使う方が分かりやすい ## 関連項目 - [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/) - [Principal Variation](/shogi/shogiwiki/search/principal-variation/) - [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/) - [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/) - [Young Brothers Wait Concept](/shogi/shogiwiki/search/young-brothers-wait-concept/) ## 参考にしたホームページ - [Chessprogramming Wiki: NODE Types](https://www.chessprogramming.org/Node_Types) - [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search) - [Chessprogramming Wiki: Parallel Search](https://www.chessprogramming.org/Parallel_Search)