[Artificial Intelligence] Adversarial Search

Adversarial Search

Games vs. search problems

• “Unpredictable” opponent  specifying a move for every possible opponent reply
• Time limits  unlikely to find goal, must approximate

Optimal decisions

Game Tree

• 2-player, deterministic, turns

Minimax

• Perfect play for deterministic games
• Idea: choose move to position with highest minimax value
  • best achievable payoff against best play
• E.g., 2-ply game:

α-β pruning

Why is it called α-β?

• α is the value of the best (i.e., highest-value) choice found so far at any choice point along the path for max
• If v is worse than α, max will avoid it  prune that branch
• Define β similarly for min

Imperfect, real-time decisions

Evaluation Function

• For chess, typically linear weighted sum of features

• e.g., w1 = 9 with f1 (s) = (number of white queens) – (number of black queens), etc.
• 4-ply lookahead is a hopeless chess player! – 4-ply ≈ human novice – 8-ply ≈ typical PC, human master – 12-ply ≈ Deep Blue, Kasparov

Deterministic games in practice

• Checkers: Chinook ended 40-year-reign of human world champion Marion Tinsley in 1994. Used a precomputed endgame database defining perfect play for all positions involving 8 or fewer pieces on the board, a total of 444 billion positions.

• Chess: Deep Blue defeated human world champion Garry Kasparov in a six-game match in 1997. Deep Blue searches 200 million positions per second, uses very sophisticated evaluation, and undisclosed methods for extending some lines of search up to 40 ply.

• Othello: human champions refuse to compete against computers, who are too good.