the set S may not conveniently describe the set R 0 ( S ) of all situations from which S can be reached.

Now suppose that we are expanding the search tree itself, and we find ourselves analyzing a particular position p that is determined to be a win for the maximizer because the maximizer can move from p to the winning set S in other words, p is a win because it is in R 0 ( S ). We would like to record at this point that the set R 0 ( S ) is a win for the maximizer, but may not be able to construct or represent this set conveniently. We will therefore assume that we have some computationally effective way to approximate the R 0 and C 0 functions, in that we have (for example) a function R that is a conservative implementation of R n in that if R says we can reach S , then so we can:

## R(P, S) C R 0 (S)

R(p, S) is intended to represent a set of positions that are "like p in that they can reach the (winning) set S ." Note the inclusion of p as an argument to R ( p, S ), since we certainly want p ∈ R ( p, S ). We are about to cache the fact that every element of R ( p, S ) is a win for the maximizer, and certainly want that information to include the fact that p itself has been shown to be a win. Thus we require p E R(p, S) as well.

Finally, we need some way to generalize the information returned by the evaluation function; if the evaluation function itself identifies a position p as a win for the maximizer, we want to have some way to generalize this to a wider set of positions that are also wins. We formalize this by assuming that we have some generalization function P that "respects" the evaluation function in the sense that the value returned by P is a set of positions that ev evaluates identically.

Definition 2.3.2  Let (G,p), S, ev) be an interval-valued game.  Let f be any function with range 2 G , so that f selects a set of positions based on its arguments.  We will say that f respects the evaluation function ev if whenever p,p' E F for any F in the range of f, e(p) = ev(p').

A partition system for the game is a triple (P, R, C) of functions that respect ev such tha t:
1. P : G → 2G maps positions into sets of positions such that for any position p, p E
P(p)

2. R : G x 2G -> 2G accepts as arguments a position p and a set of positions S.

I f p E R 0 (S), so that p can reach S, then p E R(p, S) ⊆ R 0 (S).

9. C : G x 2 G → 2 G accepts as arguments a position p and a set of positions S .

I f p E C 0 (S), so that p is constrained to reach S, then p E C (p, S) ⊆ C 0 (S).
As mentioned above, the function P tells us which positions are sufficiently "like" p that they evaluate to the same value. In tic-tac-toe, for example, the position (1) where X has won with a row across the top might be generalized by P to the set of positions

$$\left(\,5\,\right)$$

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

