## 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 sidesBasic 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