Node Types are classifications of nodes as expected inside a minimal alpha-beta tree, or as determined by the search. These types were first formulated by Donald Knuth and Ronald Moore when describing the alpha-beta algorithm^{[1]} and further analyzed by Judea Pearl^{[2]}. While Knuth used the terms Type 1, 2, and 3, Tony Marsland and Fred Popowich introduced the more descriptive terms PV-, Cut- and All-nodes^{[3]}^{[4]}.

Node types as established by the search are stored inside the transposition table, indicating whether the score is either exact, lower or upper bounded. Expected node types, as determined by tree topology, probing the transposition table, or comparing scores of a static evaluation considering threats, or even a reduced search or quiescence search, with the bounds, may be considered by various (parallel) search algorithms and in decisions concerning selectivity.

PV-nodes (Knuth's Type 1) are nodes that have a score that ends up being inside the window. So if the bounds passed are [a,b], with the score returned s, a<s<b. These nodes have all moves searched, and the value returned is exact (i.e., not a bound), which propagates up to the root along with a principal variation.

Cut-nodes (Knuth's Type 2), otherwise known as fail-high nodes, are nodes in which a beta-cutoff was performed. So with bounds[a,b], s>=b. A minimum of one move at a Cut-node needs to be searched. The score returned is a lower bound (might be greater) on the exact score of the node

The parent of a Cut-node is either a PV- or All-node

The ply distance of a Cut-node to its PV-ancestor is odd

All-Nodes

All-nodes (Knuth's Type 3), otherwise known as fail-low nodes, are nodes in which no move's score exceeded alpha. With bounds[a,b], s<=a. Every move at an All-node is searched, and the score returned is an upper bound, the exact score might be less.

The ply distance of an All-node to its PV-ancestor is even

Node Types in PVS

Onno

Onno by Onno Garms determines expected node types, beside other things, to perform IID not only at PV-nodes but also at expected Cut-nodes. Onno Garms gave the following rules ^{[6]}

The root node is a PV-node

The first child of a PV-node is a PV-node

The further children are searched by a scout search as CUT-nodes

Following summary was given by Pradu Kannan similar to Onno's definition as an attempt to predict the node type before searching the node by assuming reasonably good move ordering on PV-nodes and Cut-nodes ^{[7]}:

The root node is a PV-node

The first child of a PV-node is a PV-node

Children of PV-nodes that are searched with a zero-window scout search are Cut-nodes

Children of PV-nodes that have to be re-searched because the scout search failed high, are PV-nodes

The first child of a Cut-node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-node

A Cut-node becomes an All-node once the first and all candidate cutoff moves are searched

In CB, I used this extensively, because you never want to split at a CUT node, and want to prefer an ALL node. YBW tries to recognize an ALL node by requiring that at least one move be searched before splitting, since > 90% of CUT nodes are discovered on the first move searched. But waiting on that first move introduces some wait time, and if you knew it was an ALL node from the get-go, you could split before the first move is completed. That was the basic premise behind the iterated search and DTS algorithm in Cray Blitz ...

Donald E. Knuth and Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326, 1975. Reprinted in Selected Papers on Analysis of Algorithms by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5

Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8, pp. 559-564

^Donald E. Knuth and Ronald W. Moore (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6:293–326, 1975. Reprinted in Selected Papers on Analysis of Algorithms by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-5

^Judea Pearl (1982). The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8, pp. 559-564

Home * Search * Node * Node TypesNode Typesare classifications of nodes as expected inside a minimal alpha-beta tree, or as determined by the search. These types were first formulated by Donald Knuth and Ronald Moore when describing the alpha-beta algorithm^{[1]}and further analyzed by Judea Pearl^{[2]}. While Knuth used the terms Type 1, 2, and 3, Tony Marsland and Fred Popowich introduced the more descriptive termsPV-,Cut-andAll-nodes^{[3]}^{[4]}.Node types as established by the search are stored inside the transposition table, indicating whether the score is either exact, lower or upper bounded. Expected node types, as determined by tree topology, probing the transposition table, or comparing scores of a static evaluation considering threats, or even a reduced search or quiescence search, with the bounds, may be considered by various (parallel) search algorithms and in decisions concerning selectivity.

^{[5]}## Table of Contents

## PV-Nodes

PV-nodes (Knuth'sType 1) are nodes that have a score that ends up being inside the window. So if the bounds passed are [a,b], with the score returned s, a<s<b. These nodes have all moves searched, and the value returned is exact (i.e., not a bound), which propagates up to the root along with a principal variation.## Cut-Nodes

Cut-nodes (Knuth'sType 2), otherwise known as fail-high nodes, are nodes in which a beta-cutoff was performed. So with bounds [a,b], s>=b. A minimum of one move at a Cut-node needs to be searched. The score returned is a lower bound (might be greater) on the exact score of the node## All-Nodes

All-nodes (Knuth'sType 3), otherwise known as fail-low nodes, are nodes in which no move's score exceeded alpha. With bounds [a,b], s<=a. Every move at an All-node is searched, and the score returned is an upper bound, the exact score might be less.## Node Types in PVS

## Onno

Onno by Onno Garms determines expected node types, beside other things, to perform IID not only at PV-nodes but also at expected Cut-nodes. Onno Garms gave the following rules^{[6]}## Summary

Following summary was given by Pradu Kannan similar to Onno's definition as an attempt to predict the node type before searching the node by assuming reasonably good move ordering on PV-nodes and Cut-nodes^{[7]}:## Number of Leaf Nodes

## Formulas

As emphasized by Daniel Shawul^{[8]}, the formulas for the number of leaf nodes of a certain Node type with uniform depthnand branching factorb, using floor and ceiling of n/2 (cut the ceiling, all the floor) ...... are already the subexpressions ...

... in Levin's famous formula demonstrating the odd-even effect of alpha-beta

## Table

Assuming a constant branching factor of 40, this results in following number of leaves:n## Quotes

Robert Hyatt on the distinction between ALL- and CUT-nodes^{[9]}:In CB, I used this extensively, because you never want to split at a CUT node, and want to prefer an ALL node. YBW tries to recognize an ALL node by requiring that at least one move be searched before splitting, since > 90% of CUT nodes are discovered on the first move searched. But waiting on that first move introduces some wait time, and if you knew it was an ALL node from the get-go, you could split before the first move is completed. That was the basic premise behind the iterated search and DTS algorithm in Cray Blitz ...## See also

## Selected Publications

1975).An analysis of alpha-beta pruning.Artificial Intelligence, 6:293–326, 1975. Reprinted in Selected Papers on Analysis of Algorithms by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-51981).On the Average Number of Terminal Nodes examined by Alpha-Beta. Technical Report UCLA-ENG-CSL-8108, University of California at Los Angeles, Cognitive Systems Laboratory1982).The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8, pp. 559-5641985).Parallel Game-Tree Search.IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 7, No. 4, pp. 442-452. 1984 pdf (Draft)2003).Enhanced forward pruning.pdf » Enhanced Forward Pruning## Forum Posts

## 2000 ...

Re: Fruit - Question for Fabien by Fabien Letouzey, CCC, March 11, 2004

## 2005 ...

## 2010 ...

## 2015 ...

## External Links

## References

1975).An analysis of alpha-beta pruning.Artificial Intelligence, 6:293–326, 1975. Reprinted in Selected Papers on Analysis of Algorithms by Donald E. Knuth, Published 2000, by Addison-Wesley ISBN: 1-57585-211-51982).The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality. Communications of the ACM, Vol. 25, No. 8, pp. 559-5642003).Enhanced forward pruning.pdf1985).Parallel Game-Tree Search.IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 7, No. 4, pp. 442-452. 1984 pdf (Draft)## What links here?

Up one Level