Almost 5 years ago I described epsilon trick on this list but the pseudo-code had a bug in it, below is a correction.
The goal of epsilon trick is to reduce the amount of jumping to different parts of tree. Its main benefit for you might be reduction of number of recalculations of costly UCB formula. Also if you are short on memory and have a hash table - it will make a good use of memory. If you have a very fast program it might help you with cache trashing. The original article: http://www.mimuw.edu.pl/~lew/files/epsilon_trick.pdf The idea is simple: Instead of doing one playout in a given internal node do few before leaving. But not a constant number - we know it is inefficient. Calculate a constant fraction (for instance 1/10) of the number of visits in a current node. Do not exit that node until you make so many playout below that node. The bug: The original pseudo-code advised not to exit a given node (or equivalently: recalculate cached best node) until visis_to_go went to 0: if node.visis_to_go = 0 then // we have to set the strategy first node->child_to_visit = UCT_find_child (node) node->visits_to_go = Epsilon * node->visited_count // round up But it should be: if node.visis_to_go = 0 then // we have to set the strategy first node->child_to_visit = UCT_find_child (node) node->visits_to_go = Epsilon * node->child_to_visit->visited_count // round up Sorry about the mistake. Lukasz Lew _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
