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
• 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.
• 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:
• Tic-Tac-Toe
• Chess