Best-First Fixed-Depth Minimax Algorithms. Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin. Journal of AI 1996.

  1. “Interesting alternatives to depth-first searching, such as breadth-first and best-first strategies, have been largely ignored in practice”
  2. SSS* is best-fist, while A-B is depth-first
  3. Here they dont use the name AB-SSS*, they call it MT-SSS*?
  4. “MTD can be used to construct a variety of fixed-depth best-first search algorithms using depth-first search.
  5. They say that the assumptions for SSS*’s dominance of A-B aren’t met in practice (due to move reordering and use of iterative deepening).  Empirical results have A-B actually beating MT-SSS* in checkers at some plies for this reason
  6. Talk about significant differences between real-world, and synthetic game trees
  7. MTD(f) is the newest as of the time of writing.  It beats a state of the art implementation of Negascout in terms of total nodes, leaves, and clock time.   I think this is AB-SSS* or very very similar.
  8. They say the connection between A-B and SSS* starts with an upper bound on the minimax value, and the max-solution tree, which is the minimal search tree that proves an upper bound
  9. Most game playing programs use iterative deepening “It is based on the assumption that a shallow search is a good approximation of a deeper search.”  “Among the benefits of iterative deepening (ID) in game-playing programs are better move ordering…, and advantages for tournament time control information.”
  10. “Transposition tables are often used in conjunction with iterative deepening to achieve a partial move ordering.  The search value and the branch leading to the highest score (and best move) are saved for each node.  When iterative deepening searches on level deeper and revisits nodes, the move suggested by the transposition table (if available) is searched first”
  11. Transposition tables are also used to recycle computation when it exists in a graph structure
  12. In emprical results they use very strong programs for comparisons, and modify them as little as possible
  13. The states from games used are states that acutally came up from tournament play; they mention sometimes states used are contrived
  14. They are concerned with node/leaf re-expansions, but in pure trees this isn’t an issue
  15. They say that in practice, memory actually isn’t an issue – and this was written a long time ago
  16. They keep referring to MT-SSS*, but I don’t see where its described explicitly…
  17. The MT (Memory-enhanced Test) framework allows depth-first procedures to implement best-first algorithms

Memory-enhanced Test: a Framework

  1. MT(n,gamma) = A-B(n, gamma-1, gamma) when using transposition tables
  2. One method is to start with gamma = inf and move down from there
  3. Talk about “drivers” for MT, which specify:
    1. n: the root of the tree
    2. first: the starting bound for MT
    3. next: after the completion of a search, how the bounds are updated. This is a function.
  4. MTD would be an algorithm using the MT framework.  They list a number of instantiations of algorithms in the framework.
    1. AB-SSS* = MT-SSS* = MTD(n, inf, bound = g)
    2. Another searches from -inf, then one tries to do a binary search on the true minimax value, they call this MTD(bi)
      1. Mention an equivalent algorithm C* that is also guaranteed to dominate A-B
    3. Can also specify a specific step size to move the bounds by, called MTD(step)
    4. Say MTD(bi) and step seem inferior
  5. Transposition tables prevent waste of reexpansion
  6. MTD(f) is consistently the best algorithm.  They say in practice in these agents, it actually uses less memory than A-B
    1. Says SSS*/MTD(inf) is optimistic (paper seems to be very inconsistent with names, which is even worse across papers
    2. DUAL*/MTD(-inf) is pessimistic
    3. and MTD(f) is realistic
  7. Difference between the algorithms is just a few percent, though (mainly because of the excellent move ordering and other tricks the game programs do aside from the searching itself)
  8. Number of nodes expanded in experiments depends on whether the number of plies is odd or even, which we didn’t see in our synthetic results
  9. If you have a guess as to what the minimax value actually will be, initializing the null window to around that area seems to help (for MTD(f))
  10. “…if MTD(f) is to be effective, the f obtained from the previous iteration must be a good indicator of the next iteration’s value”
  11. Keep in mind the empirical results are relative to very effective game programs that do excellent move ordering and other tricks
  12. Argue against reporting results on synthetic trees:
    1. Real trees have variable branching factor
    2. Value interdependence from parents to children – usually parent values are good predictors for children (a shallow search is a good approximation of a deeper one).  This is probably why UCT can perform so well at Go.
    3. Existence of graph structure, allows for use of transposition table

Appendix on MT-SSS*

  1. Every top-level call to MT fails low and builds a max-solution tree.  The last call to MT (stops the search) fails high and builds a min-solution tree
  2. In the first pass, the left-most solution tree with finite g-value (value of the tree rooted at specified node n) is constructed
  3. During following passes, the following conditions hold:
    1. Before each pass, the tree exposed is the left-most max solution tree with upper bound = gamma.  The children to the left of the min node (child of the root) has already been searched and the lower bound on that subtree is > gamma
    2. During each pass, every node visited belongs to the max solution tree with upper bound = gamma.  For min nodes, children to the left of the child of n (there is only one in the max-solution tree) has a lower bound > gamma and will never be revisited
    3. Whenever nested calls to MT(n, gamma) fail low, a max-solution tree is created where children of min-nodes have property 1

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: