A Minimax Algorithm Better than Alpha-Beta? No and Yes. Plaat, Schaeffer, Pijls, de Bruin


(Note: This is a tech report from Alberta, so unrefereed, I wont be going through it thoroughly.  Perhaps a better thing to read is New Advances in Alpha-Beta Searching)

(Schaeffer is the guy that did Chinook, and solved checkers)

  1. Need to find out what a null-window is
  2. 2 main contributions are:
    1. New formulation of SSS* based on alpha beta (AB) is presented, which is basically AB+transposition tables/memoization.
    2. Present a framework that helps classify existing several best-first fixed-depth search algorithms, and uncovers some new methods as well
  3. SSS* provably expands less nodes than AB, and empirically does so as well
  4. But is complex/difficult to implement and is also generally slower than AB due to the very large priority queue that it builds/maintains (including purging), which has size exponential in depth of the search tree explored.
  5. SSS* functions quite differently from AB, but works only in the fixed-depth setting.  It does a best-first search (like A*) visiting the most promising nodes first, whereas AB uses left to right traversal of the tree.
  6. Claimed in practice, the conditions for the proof of SSS* don’t hold, seems like iterative deepening is sometimes attempted but with this addition it is no longer guaranteed to expand less nodes than AB
  7. AB-SSS* seems to be much simpler than SSS* but is equivalent.  It basically involves using memoization and lying to AB about the min value that can be achieved; an extremely simple loop on top of AB.  This outer loop is a way of transforming depth-first to best-first searches. Mentions other algorithms have been presented that are SSS* but easier to understand.
  8. Transposition tables a generally used to:
    1. improve the quality of the move ordering
    2. detect when different paths through the search space transpose into the same state, to prevent the re-expansion of that node.
  9. In the case of an algorithm in which each ID iteration performs multiple passes over the search tree, like AB-SSS* and AB-DUAL*, there is an additional use for the TT:prevent the re-search of a node that has been searched in a previous pass, in the current ID iteration.
  10. Some operations on the priority queue of SSS* are superpolynomial (purge of exponential sized queue, sometimes up to 90% of running time)
  11. Good “move ordering” achieved by using iterative deepening and memoization increase the pruning power of AB and SSS*.  I think the move ordering refers to the estimated values of moves from the previous iteration of iterative deepening
  12. Using transposition tables is helpful because it turns the tree search into a graph search, gets rid of need for priority queue and uses hashing instead.  Also, using transition tables makes the algorithm able to use set amounts of memory (using more just makes it more efficient), whereas SSS* can’t run on limited memory
  13. Seems like size of transposition tables in common games (othello, chess, checkers) isn’t a huge issue (at least based on the processing that was done when the paper was written in the mid 90s).
  14. Says AB-SSS* is only a few percent faster than just running AB
  15. Show MTD framework that can represent a number of search algorithms
  16. AB-SSS* refines a max solution tree, AB-DUAL* refines a min solution tree
  17. If iterative deepening is used with SSS*, it doesn’t necessarily dominate AB with iterative deepening.  In this case the overall performance of AB is better
  18. MTD(f) does 5-10% better than the most commonly used negascout.
  19. Whereas AB-SSS*, AB-Dual search from opposite extremes of the tree, MTD(f) searches around the middle, is more efficient, early guesses are closer to true minimax value
  20. They discuss some differences between real-life game trees vs those that are commonly simulated:
    1. Variable branching factor in real life; some algoritms leverage this in a least-work-first manner
    2. In real applications, evaluation of a shallow search is often a very good estimate of the value of a deeper search
    3. Global move ordering: moves that are good in one position tend to be good in another as well
    4. Trees remerging to graphs come up often in real life, so memoizing is useful
  21. AB-SSS* uses null window searches only
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: