AB and TTables

PSU CS442/542GAMES Lecture 4

• AB: Alpha-Beta Pruning
  • Idea: Your opponent knows as much as you, and won't give you a cheap win.
  • Implementation: keep track of best provably achievable score so far for self, opponent (from earlier siblings). If you find you can achieve better than the negation of opponent's provable best score, you're never getting here: stop searching.
  • Corollary: For maximum pruning, order moves by best-first to get tight bounds early. Leads to narrow "AB window".
  • Pending: "Zero-window" search.
  • Effectiveness: 1/2 branching factor best case, 3/4 random case, doesn't hurt in worst case.
• TT: Transposition Tables
  • Ideas: Moves transpose. Search is expensive.
  • Implementation: Remember the value of a state to avoid re-computing it when encountered again. Create a reasonable hash function (fast yet good) and do random replacement. Allocate as much storage for the ttable as you can.
  • Danger: states are distinguished by
    • Board
    • Side to move
    • Search depth
    • AB window
  • Danger: odd termination rules will mess you up. (Graph-History Interaction [Campbell 1985])
• 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]