homework 6 CMPUT 355 Prof Hayward fall 2019
1. Recall: In alphabeta search, at each MAX node, alpha tracks the best (so, maximum) score
so far that MAX can get. Similarly, at each MIN node beta tracks the best (so, minimum)
score so far that MIN can get.
Assume that x is a MIN node with current beta value β obtained by picking a child y of x.
Assume that minimax search now starts at child z of x, so a MAX node. If at z the alpha
value α grows so that α ≥ β then we can stop searching at z, since MIN can always prefer
child y (with value β) to child z (with value ≥ α ≥ β).
( fill in the blanks) Assume that x is a MAX node with current alpha value α obtained by
picking a child y of x. Assume that minimax search now starts at child z of x, so a
node. If at z the beta value β drops so that β ≤ α then we can stop searching at z, since
.
2. Trace alphabeta search on this game tree. (MAX
plays first, leaf scores are for MAX.) At each
node, show the alpha and beta values each
time they change. Does the search cut off
any branches? Check your answer by run-
ning python3 alphabeta.py < t1.in in direc-
tory /simple/alphabeta/alphabeta.py .
A
B C
7 5 3 1 9
3. (i) Repeat the previous question after relabelling the 5 leaves left to right in order 5 7 9 3 1.
Is the minimax value the same? How many branches are cut off? (ii) Repeat after relabelling
1 3 5 7 9.
4. In tic-tac-toe, assume that a player scores 1, 0, −1 respectively for a win, loss or draw. For
the three non-isomorphic first moves in tic-tac-toe, what is the first player’s minimax value
for each move? (Use any of the programs from class to answer this question.)
5. Recall that a proof tree is a subtree of the minimax tree that is sufficient to prove the minimax
value, or some bound on the minimax value. i) For x to play from the position below left,
give a proof tree that shows that x can win (answer on the class webnotes). ii) For x to play
from the position below middle, give a proof that shows that o can win. (Give all possible
first moves for x, then for each give a winning replay for o, then for each give all next moves
for x, then for each a winning reply for o, etc.). Check your answer using a program from
/simple/ttt/.
x . o . . . . . .
x . . x o x . o .
o . . . o . x o x
6. Modify tic-tac-toe: the first player x wins if she gets 3-in-a-row, otherwise the second player
o wins. What is the first-player minimax value for this game (win, lose)? For this game, give
a proof tree for x to play from the position above right.