

![0_image_0.png](0_image_0.png)

This section explains these ideas via an example and then describes them formally.

Experimental results for bridge are also presented.

## 21 An Example

Our illustrative examples for partition search will be taken from the game of tic-tac-toe. A portion of the game tree for this game appears in Figure 1, where we are analyzing a position that is a win for X. We show O's four possible moves, and a winning response for X in each case. Although X frequently wins by making a row across the top of the diagram, α-β pruning cannot reduce the size of this tree because O's losing options must all be analyzed separately.

$$\frac{\mathrm{\bf{x}}\left|\mathrm{\bf{x}}\right|\mathrm{\bf{x}}}{\mathrm{\bf{0}}\left|\mathrm{\bf{0}}\right|}$$

Consider now the position at the lower left in the diagram, where X has won:

$$\left(\mathbf{\Omega}\right)$$

The reason that X has won is local. If we are retaining a list of positions with known outcomes, the entry we can make because of this position is:

$$\left(\,2\,\right)$$

where the ? means that it is irrelevant whether the associated square is marked with an X, an O, or unmarked. This table entry corresponds not to a single position, but to approximately 36 because the unassigned squares can contain X's, O's, or be blank. We can reduce the game tree in Figure 1 to:

