On the Behavior of UCT in Synthetic Search Spaces. Ramanujan, Sbharwal, Selman. ICAPS 2011(?)

  1. Basic point is that A-B search is good in some areas (chess), whereas UCT is good in others (go)
  2. Say failure of A-B in go is due to large branching factor and poor evaluation functions
  3. What other characteristics can make one better than the other in certain domains.  This has been done a bit on real games, but the size of real games makes real analysis difficult.  Idea here is to use synthetic trees that are easy to evaluate to determine strengths and weaknesses
  4. Corrupt (known) heuristic value by gaussian noise
  5. One key is that random sampling deeper in the subtree should produce a value similar to the true value for UCT to work well
  6. Claim that a major characteristic of games where UCT does poorly and A-B does well are games with shallow search traps, where an opponent can easily win a few moves (essentially early terminal states)
  7. Cites a number of papers that discusses various types of synthetic search trees
  8. Theres a bit of math about the particular type of tree theyre using (to show accuracy of estimations of node values) that isn’t otherwise extremely interesting
    1. All that discussion is strange because the trees they are running their algorithms on arent enormous (depth 14), so it isn’t hard to find the real minimax value
  9. Oh, its over?

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 )

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: