CS 410/510 Games: Advanced Search

Advanced Search

PSU CS410/510GAMES Lecture 5
May 1, 2007

  • ID: Iterative Deepening (again)
    • Ideas: Hard to predict search time. Need to order moves well.
    • Implementation: Use ID to time limit. Note convergence of root value? Use ttable to order moves effectively (via values from previous iteration).
    • Problem: Want to leverage transposition table to decrease search, but how?
    • Idea: Horizon effect is a nightmare. Search deeper where it matters
    • Implementation: AB already prunes out-of-bounds leaves. Use secondary heuristic to estimate accuracy of primary heuristic ("quietness"), extend search where necessary.
    • Problem: Hard to build/tune.
  • Putting it all together: zero-window search
    • Idea: Could prove a known value quickly.
    • Implementation: Start the AB window closed on some guessed value. At some point, may find that no line achieves this value. Can track "fail-low" vs. "fail-high".
    • Advantage: Goes very fast if you have good estimates.
    • Disadvantage: Goes very slowly if you have bad estimates.
    • Modern implementation: MTD(f) [Plaat 1996]
  • Search Extensions
    • Quiescence search
      • Horizon Effect is classic problem; don't stop in middle of exchange and guess
      • Determine quiescence by seperate heuristics or by variance in root value
    • Principal Variation Search (PVS) = Korf: ``best-first minimax''
      • Idea: trust eval in interior of tree to prune ``bad'' moves early
      • Trick: always extend (leftmost) path determining root value (variant of AB)
      • Suffers from ``early mistake'' problem: fix by depth cutoff (common), weighting, sampling, etc.
  • Shape of game space