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
- 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.
- 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.
- 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: