A game progresses as the odd player makes a move to level 2, the even player moves to level 3, and so on. The *active* player is player *Odd* on odd levels and player *Even* on the others. The value of a node is the value of it to the player who moves *from* that node. A leaf node represents a final configuration of the game and hence a win or loss for some player. The value of a leaf node is the *payoff* for some player, and the convention is:

The value of node *p* for the player moving from it is:

v=Maximum{ - p .Child[i] .Valuefor alli}

Maximum( - ( + 5), - ( - 10)) = + 10

*Exercise EW. 1 and problem PW. 1 are appropriate at this point.*

The player in opposition always makes the move that is optimal for him or her.

functionNodeValue(gt, Choice) {O(n)

ChoiceNIL

NoChildTRUE

MaxValueTooSmall{less than any possible node value

fori=1toMaxChilddo

pgt.Child[i]

ifpNIL

thenNoChildFALSE

v-NodeValue(p,Choice)

ifv>MaxValue

thenMaxValuev

Choicep.Child[i]

endif

endif

nexti

ifNoChild

thenvLeaf Value(gt)

elsevMaxValue

endif

gt.Valuev

returnv

end{NodeValue

*Problems **PW.2 and PW.3 are appropriate at this point.*

P>

A procedure like *NodeValue* examines every subtree of a child, but that may not be necessary. Consider the tree fragment in Figure W.2.

An additional phase of pruning can be initiated by passing the alpha value of a node *p* to a grandchild, *gcp*, as a lower bound, *Bound*. As soon as it is known that a grandchild of *gcp* has a value lower than *Bound*, the child *cgcp* in which it is rooted will not allow the value it passes up to *gcp* to be as large as *Bound*, and so the remaining children of *cgcp* can be pruned. Figure W.3 illustrates this phase.

Alpha-beta pruning, bounding, and level-limiting can all be incorporated into *NodeValue* to form:

functionPruneValue(gt,Choice,Bound,Level)

ifLevel=0then return endif

ChoiceNIL

NoChildTRUE

MaxValueBound

fori=1toMaxChilddo

pgt.Child[i]

ifpNIL

thenNoChildFALSE

v-PruneChild(p, Choice,-Bound,Level - 1)

ifv>MaxValue

thenMaxValuev

Choicep.Child[i]

endif

endif

nexti

ifNoChild

thenvBound

elsevMaxValue

endif

p.Valuev

returnv

end{PruneValue

Exercise immediate application of text materials

**EW.1** Show how the values of the interior nodes of GT_{1 }are derived from the values of terminal nodes.

**PW.1** Draw the game tree for the game of NIM when *n* = 6. NIM is played by two alternating players, each of whom may pick up 1, 2, or 3 toothpicks from a pile that initially holds *n*. The player who empties the pile loses.

**PW.2** Redesign *NodeValue* to be depth-limited.

**PW.3** Write a search procedure that calls *NodeValue*.

Program for trying it yourself

**PGW.1** Write a program that creates 32 random leaf-node values in the range [ - 10 . . 10], builds a game tree from them, prunes it with *PruneValue*, and displays the pruned tree.

Project for fun; for serious students

**PJW.1** Make PGW.1 a procedure, *n* leaf nodes a variable, and study the mean and standard deviation of the nodes in the pruned trees as a function of *n*.