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

Basic point is that A-B search is good in some areas (chess), whereas UCT is good in others (go)

Say failure of A-B in go is due to large branching factor and poor evaluation functions

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

Corrupt (known) heuristic value by gaussian noise

One key is that random sampling deeper in the subtree should produce a value similar to the true value for UCT to work well

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)

Cites a number of papers that discusses various types of synthetic search trees

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

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

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here:
Cookie Policy