CS 410/510 Games: Getting Started

# Search In Games

PSU CS442/542GAMES Lecture 2

- Single Agent Search
- Some solitaire games
- n-puzzle
- Sokoban
- Rubik's Cube

- Search and ``Branching Factor''
- Heuristic Search
- Pruning and guidance
- Depth-First Branch and Bound
- A*
- LDS

- Relation to two-player case

- Some solitaire games
- Adversary Search
- Reminder: conditions
- two player
- zero sum
- perfect information
- deterministic
- alternating, terminating

- Minimax Search
- Terminology: first player is ``maximizer'', opponent is ``minimizer''.
- Completed game has a definite score. (Intervals [-1.0 ... 1.0] or [-1000 ... 1000] are popular.)
- Maximizer wants to make outcome of the game as positive as possible, minimizer as negative as possible.
- Symmetry: can negate scores and switch minimizer w. maximizer. This leads to negamax search.

- The "easy" minimax theorem
- base case: choose the winning option
- inductive case
- choose the option damaging opponent since zero sum
- know this option since perfect info deterministic
- induction terminates since game terminates
- induction step: compute opponent minimax value since alternating

- Search space is too large for real games. Limit by
- Depth:
- Instead of recursive call, try using
*heuristics*to estimate quality of*state*(not best*move*). - Prove upper or lower bound on value of game below state.

- Instead of recursive call, try using
- Breadth:
- Use heuristics to take moves from best to worst for player on move. Use more heuristics to avoid recursive calls for ``bad'' moves.
- Prove that some move is strictly worse than a move already considered.

- Opponent Modeling (expectimax): If your opponent
would not consider this move and its consequences,
you
*need*not either.

- Depth:
- Evaluation Function
- Heuristic for estimating minimax value of a state.
- Typically just a number, but may also estimate confidence of estimate, or be some fancy (total-orderable) datum.
- ``Real'' backed-up values vs. heuristic values: risk aversion.
- No perfect formula. Sanity checks:
- Does a maximizer winning state get a maximum positive score? Does a minimizer winning state get a minimum negative score? A draw 0?
- Does the value assigned in real games have some relationship to human estimates?
- Are there obvious game features missing?
- In games with
*material*as a state feature, is it domininant in the game? In the evaluator?

- Cost of evaluation vs. cost of extra search.
- Examples:
- Tic-Tac-Toe
- Chess

- Reminder: conditions