We have augmented the condition developed in the discussion of Figure 7 with the assumption that if a player's move in a position p is forced (so that p has a unique successor),
then the value before and after the forced move is the same.

Proposition 6.1.2 For any simple game, there are binary functions Λ and V from V to itself that are commutative, associative and idempotent 14 and such that f+{vo; · · · ; vm} = vo V · · · V vm and

$f_{-}\left\{v_{0},\cdot\cdot\cdot\cdot,v_{m}\right\}=v_{0}\wedge\cdot\cdot\cdot\wedge v_{m}$.  
Proof.  Induction on m.

L
When referring to a simple game, we will typically replace the functions f+ and f_ by the equivalent binary functions V and A. We assume throughout the rest of this section that all games are simple. 15 The binary functions V and Λ now induce a partial order ≤ , where we will say that x ≤ y if and only if x Vy = y. It is not hard to see that this partial order is reflexive ( x < x ), antisymmetric ( x < y and y < x if and only if x = y ) and transitive. The operators V and A behave like greatest lower bound and least upper bound operators with regard to the partial order.

We also have the following:
Proposition 6.1.3 Whenever S C T, f+(S) < f+(T) and f-(S) > f-(T).

口 In other words, assuming that the minimizer is trying to reach a low value in the partial order and the maximizer is trying to reach a high one, having more options is always good.

## 6.2 Shallow Pruning

We are now able to investigate α-β pruning in our general framework. Let us begin with shallow pruning, shown in Figure 8.

The idea here is that if the minimizer prefers x to y, he will never allow the maximizer even the possibility of selecting between y and the value of the subtree rooted at T. After all, the value of the maximizing node in the figure is y V evc ( T ) ≥ y ≥ x, and the minimizer will therefore always prefer x.

In order for the usual correctness proof for (shallow) α-β pruning to hold, we need the following condition to be satisfied:
Definition 6.2.1 (Shallow a-B pruning) A game G will be said to allow shallow a-B pruning for the minimizer if x Λ (y V T ) = x
(10)