Here is another MC speedup trick. I think it may have been mentioned
before but it's worth repeating.
This applies to the case where my program is going to run N playout games
and then select the most visited node as its move for that turn (which will not
always be the node with the highest percentage of wins). It is rarely necessary
to run all N playout games.
After more than half of the playout games have been completed, some moves
may become mathematically eliminated because they have been visited too few
times for them to be able to catch up to the leader. So, at regular intervals
thereafter, I can perform a popularity pruning operation at the root. If there
are M playout games to go, and a move at the root would need more than M more
visits to catch up with the most popular (visited) move, then any further
playout games through that move would be wasted. I might as well prune it now.
When all but one move at the root has been pruned away, no further playout
games are needed for this turn. Popularity pruning averages to about a 20%
speedup free and clear.
Of course, one can prune a move at the root a little earlier, or prune
moves beyond the root, but then you have moved into a different regime.
- Dave Hillis
antminder on KGS
________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam
and email virus protection.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
