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.

- Quiescence search
- Shape of game space