## 3 Review of Alpha-Beta Pruning  
Alpha-Beta pruning [17] is a mathematically sound technique to detect and prune away \"dead branches\" in a game tree, _i.e._, branches that cannot have an effect on the outcome of the search. Today, alpha-beta pruning remains a crucial component of any practical game program that uses minimax.  
Figure 1 shows alpha-beta pruning applied to the standard negamax formulation of minimax search. If \(x\) is a node in a game tree, let \(\ell(x)\) denote its level and let \(p(x)\) denote its parity,  
\[p(x)=\left\{\begin{array}{ll}1&\text{if }\ell(x)\text{ is odd}\\ 0&\text{if }\ell(x)\text{ is even}\end{array}\right. \tag{3}\]  
When the algorithm begins processing a new node \(x\), the parameter \(\alpha\) represents the current maximum valuation of any node of \(x\)'s parity that is an ancestor of \(x\). The parameter \(\beta\) represents the negative of the current maximum valuation of any node of the opposite parity to \(x\) that is an ancestor of \(x\). For example, in Figure 2, \(x\) is passed \(\alpha=-2\) and \(\beta=1\). The \(\alpha=-2\) indicates the fact that \(u\) has a value of \(-2\). The \(\beta=1\) represents the fact that \(y\) currently has a value of \(-(1)\). When \(z\) returns to \(x\) a value of \(2>\beta\) (note that when we say \"return to \(x\)\" we mean the value returned by \(z\) after \(x\) has negated it), it becomes clear that the remaining children of \(x\) do not need to be examined. This is because the value that \(x\) will return to \(y\) will be less than or equal to \(-2\), which means that \(y\) will prefer \(v\) over \(x\). Therefore, the remaining children of \(x\) become irrelevant and can be safely pruned. When \(x\) passes parameters to its own child \(z\), it will pass \(\beta\) equal to the negative of its own \(\alpha\). For \(x\), \(\alpha\) represented the highest value of an ancestor of its own parity. Since the child of \(x\) will be of opposite parity to \(x\), the value that will be passed for \(\beta\) will correctly be the negative of the maximum value of an ancestor of opposite parity.  
When \(x\) passes the \(\beta\) parameter to a child, it should pass the negation of the maximum value of an ancestor of the child of opposite parity to the child, _i.e._, of its own parity. This value will either be the negation of the \(\alpha\) that \(x\) received from its own parent, or it will be the negation of the value of one of the earlier siblings of \(z\) (represented in the algorithm in Figure 1 by the variable \(\verb\(x\) itself. Therefore, \(z\) will be passed a value of \(\beta\) equal to the negation of the value \(x\) received from \(w\), which is a sibling of \(z\).  
In this way, the values of \(\alpha\) and \(\beta\) are propagated throughout the tree, where for each node, they represent a window within which the node must score or else it will be irrelevant.  
Figure 3: Illustration of parameter-passing in alpha-beta pruning.  
Figure 2: Example of a cut-off in pruning with standard negamax.  
Algorithm ABAlthofer (\(x\),\(\alpha\),\(\beta\))  
\(h\longleftarrow\) static evaluation (\(x\))  
if \(x\) is a leaf  
return (\(h\))  
Generate children \(x_{1},\ldots,x_{n}\), of \(x\).  
\(m\longleftarrow\alpha-h\)  
For \(i\) := 1 to \(n\) do  
\(t\longleftarrow\) ABAlthofer (\(x_{i},-(\beta-h),-m\))  
if (\(t>m\))  
\(m\longleftarrow t\)  
if (\(m+h\geq\beta\))  
return (\(m+h\)) /* cut-off */  
od  
return (\(m+h\))