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
  • 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