as in (2).

$$\frac{\mathrm{\boldmath~X~}|\mathrm{\boldmath~Y~}}{\mathrm{\boldmath~O~}|\mathrm{\boldmath~O~}}$$

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

The functions R and C approximate R 0 and C 0 . Once again turning to our tic-tac-toe example, suppose that we take S to be the set of positions appearing in (5) and that p is given by

$$\begin{array}{c c c}{{}}&{{}}&{{\mathrm{-}}}&{{\mathrm{-}}}\\ {{p.}}&{{R(p,S)\ \mathrm{might}}}\end{array}$$

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

so that S can be reached from p. R(p, S) might be

$\mathfrak{h}\mathfrak{g}$
$$\quad(6\,)$$
$\{p\}$ or $R(p,S)$ to be. 
as in (3), although we could also take R(p, S) = {p} or R(p, S) to be although this last union might be awkward to represent. Note again that R and C are functions of p as well as S; the set returned must include the given position p but can otherwise be expected to vary as p does.

We will now modify Algorithm 2.2.5 so that the transposition table, instead of caching results for single positions, caches results for sets of positions. As discussed in the introduction to this section, this is an analog to the introduction of truth maintenance techniques into adversary search. The modified algorithm 2.3.3 appears in Figure 2 and returns a pair of values - the value for the given position, and a set of positions that will take the same value.

Proposition 2.3.4 Suppose that v = αβ (p, [ x,y ]) for every ( S, [ x,y ],v ) in T and p ∈ S.

Then if evc(p) E [x,y], the value returned by Algorithm 2.3.3 is evc(p).

Proof. We need to show that when the algorithm returns, any position in S ans will have the value vans. This will ensure that the transposition table remains correct.

To see this, suppose that the node being expanded is a maximizing node; the minimizing case is dual. Suppose first that this node is a loss for the maximizer, having value 0.

In showing that the node is a loss, we will have examined successor nodes that are in sets denoted S new in Algorithm 2.3.3; if the maximizer subsequently finds himself in a position from which he has no moves outside of the various S new , he will still be in a losing position. Since S all = US new: the maximizer will lose in any position from which he is constrained to next move into an element of S all.  Since every position in C ( p, S all ) has this property, it is safe to take Sans = C (p, Sall). This is what is done in the first line with a dagger in the agorithm.

The more interesting case is where the eventual value of the node is nonzero; now in order for another node n to demonstrably have the same value, the maximizer must have nnnee options at n, and must still have some move that achieves the value vans at n.

The first condition is identical to the earlier case where vans = 0. For the second, note that any time the maximizer finds a new best move, we set S ans to the set of positions that