Adversarial Search

Question 1

Simple Games

Answer 1

Environment with multiple agents that keep most other restrictions in place (chess, poker, monopoly)

Question 2

Two-player Games

Answer 2

Classic game with two players

Question 3

Perfect Information Games

Answer 3

All players know exact state of the game

Question 4

Zero-sum Games

Answer 4

The result/utility for each player at the end of the game is exactly the opposite of the opponent (summed result, tournament)

Question 5

Search tree for 2-player, zero-sum games

Answer 5

• opponent makes every other move
• form tree in alternating layers
• choose actions that maximize our utility and minimize opponent utility
• result of tree is a single move

Question 6

Minimax

Answer 6

Function used in 2-player, zero-sum games
- if terminal, return utility
- if max player, return max of all options
- if min player, return min of all options

Question 7

Alpha-Beta Search Algorithm

Answer 7

If we can move to ‘m’ which has better minimax value then ‘n’, don’t need to expand path with ‘n’.
a = value of highest value choice along max path
b = value of lowest value choice along min path