New Advances in Alpha-Beta Searching. Schaeffer, Plaat

  1. Ah.   Move ordering means the order in which nodes are expanded in AB search.  Optimally, the best node is selected to be expanded and no other nodes have to be expanded, so getting a good approximation of this is extremely helpful.
  2. Also, this explains windows, which are the difference between the lower and upper bounds used (alpha, beta, respectively).  Narrowing the window (bounds) increases the likelihood of a cutoff.  The narrowest window occurs when alpha = beta-1 when int valued
  3. Early depth cutoffs of actions that quickly seem bad helps
  4. Aspiration search means calling alpha-beta with bounds centered close to the expected (optimal?) value, it can be called with the loosest bounds of +/- infinity.  Using aspiration search is ok as long as the value is in the specified values or if a search value is better than expected, but is bad if it fails low (this is opposite of my expectations, need to think about it more)
  5. If the search fails low, the search window can be adapted and then search can happen again
  6. A series of minimax searches with minimal windows allows convergence on the optimal value.  The search starts with an upper bound of inf and lowers it iteratively, which results in the same performance as SSS*.  Another algo searches from -inf.  MTD(f) searches in both directions simultaneously
  7. The memoization thats used is the depth to (from?) which the node was searched, the best move and its score.  When a node is visited, the best move recorded is searched first before others
  8. They also talk about something called enhanced transportation cutoff which is another optimization
  9. “This unsatisfactory state of affairs [problems with SSS*] has left many researchers in the field with a nagging feeling. Although Alpha-Beta-based programs achieve good results, it could be that depth-first strategies are missing out on some fundamental notion, and that best0first is a better way”

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 )

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: