Thus every one of O's moves leads to a position that is known to be a win for X, and we can conclude that the original position (4) is a win for X as well. The root node in the reduced tree can therefore be replaced with the position of (4).

These positions capture the essence of the algorithm we will propose: If player x can move to a position that is a member of a set known to be a win for x, the given position is a win as well. If every move is to a position that is a loss, the original position is also.

## 2.2 Formalizing Partition Search

In this section, we present a summary of existing methods for evaluating positions in game trees. There is nothing new here; our aim is simply to develop a precise framework in which our new results can be presented.

Definition 2.2.1 An interval-valued game is a quadruple (G,p1, s,ev), where G is a finite set of legal positions, p1 E G is the initial position, s : G → 2G gives the immediate successors of a given position, and ev is an evaluation function

## Ev : G → {Max,Min} U [0,1]

Informally, p' E s(p) means that position p' can be reached from p in a single move, and the evaluation function ev labels internal nodes based upon whose turn it is to play (max or min) and values terminal positions in terms of some element of the unit interval [0,1].

The structures G, pi, s and ev are required to satisfy the following conditions:

1. There is no sequence of positions po, . . ,pn with n > 0, pi E s(pi-1) for each i and Pn = po. In other words, there are no "loops" that return to an identical position.

2. ev(p) E [0, 1] if and only if s(p) = 0. In other words, ev assigns a numerical value to p if and only if the game is over. Informally, ev(p) = max means that the maximizer is to play and ev(p) = min means that the minimizer is to play.
We use 2 G to denote the power set of G, the set of subsets of G. There are two further things to note about this definition.

First, the requirement that the game have no "loops" is consistent with all modern games. In chess, for example, positions can repeat but there is a concealed counter that draws the game if either a single position repeats three times or a certain number of moves pass without a capture or a pawn move. In fact, dealing with the hidden counter is more ntural in a partition search setting than a conventional one, since the evaluation function is in general (although not always) independent of the value of the counter.

Second, the range of ev includes the entire unit interval [0, 1]. The value 0 represents a win for the minimizer, and 1 a win for the maximizer. The intermediate values might correspond to intermediate results (e.g., a draw) or, more importantly, allow us to deal with internal sear nodes that are being treated as terminal and assigned approximate values because no time remains for additional search.

The evaluation function ev can be used to assign numerical values to the entire set G
of positions: