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