Adversary Search
Adversary Search
So far, we have only fought the instance
Consider a two-player game with:
Perfect knowledge (for now)
No "luck" (for now)
Turn-based
Always ends
Well-defined final score + "zero sum"
Examples: Checkers, Chess, Connect-4, Tic-Tac-Toe
We can use state-space search to find "good" or maybe even "best" plays in that game at a given state
Game State Space
State:
"Board" position (where are the checkers)
Side on move (red or black)
Maybe history of game (ugh, not checkers)
State space is directed, neighbors are states after legal moves
State space may be cyclic (which is where history rules sometimes come from)
Zero-Sum and Negamax
Minimax Theorem (Von Neumann, Nash): Any state in the game has a well-defined value assuming "best play" by both sides
Basic Negamax idea:
Choose a next state with minimum value for opponent (moves are boring)
Determine this by valuing each opponent state from opponent's point of view (recursively)
Zero-sum, so your value = negation of opponent's value
Thus, pick state that maximizes negation of opponent's value
Win Pruning
If on some search you find a move (successor state) that is a win for the side on move — no point in searching further
This is true whether the win is immediate or by forced play
Can remove an "exponential" number of states from the search
Game Value
Value of a game is value of starting state to side on move
Game's value is value of starting state
Game is "solved" if the value of every state is known (recorded or trivially calculated)
Game is "weakly solved" if the value of every state that could occur in perfect play is known
Value is known: Hex
Weakly solved: Checkers
Solved: Tic-Tac-Toe, Connect-4, Awari, many others