6 - games and adversarial search

Question 1

Games vs. single-agent search

Answer 1

We don’t know how the opponent will act
Solution: strategy or policy + efficnecy

Question 2

Minimax value of a node

Answer 2

the utility (for MAX) of being in the corresponding state, assuming perfect play on both sides

Question 3

Minimax strategy

Answer 3

Choose the move that gives the best worst-case payoff

Question 4

Alpha-Beta Pruning

Answer 4

Avoid processing subtrees that have no effect on the result
α is used in MIN nodes, and is assigned in MAX nodes ( α= “at least”)
β is used in MAX nodes, and is assigned in MIN nodes ( β = “at most”)

Question 5

Beta cutoff

Answer 5

stop search below MAX node N (i.e., don’t examine more descendants) if alpha(N) >= beta(i) for some MIN node ancestor iof N

Question 6

Alpha cutoff

Answer 6

stop search below MIN node N if beta(N)<=alpha(i) for a MAX node ancestor iof N

Question 7

Expectiminimax

Answer 7

for chance nodes, average values weighted by the probability of each outcome

Question 8

Monte Carlo simulation

Answer 8

when you get to a chance node, simulate a large number of games with random dice rolls and use win percentage as evaluation function