> It's interesting with UCT because of the interplay between the time > management algorithm and the exploration parameter. Suppose you are > early in the game, and your time management algorithm says you should be > spending 10 seconds on a move. After six seconds, because your parameter > is skewed towards exploitation, you already have 90% more trials on the > leading move than anything else, calculate that it cannot be overtaken > and abort.
One of the main characteristics of the MCTS algorithm is that it plays to win, not to find the best move. If you are winning then exploitation makes sense - following that move deeper in the tree to confirm you are right, or discover some counter-attack that means the move is actually bad. On the other hand if your best move is losing then it makes sense to do more exploration, trying out the wild ideas, the tenuki and the moves that look like bad shape. I thought MCTS kind of did this naturally, but now I think more about it I don't think it does? It's exploration vs. exploitation rate at a given node is the same whether it thinks it is winning or losing at that node? Darren > Some things come to mind: > - If this behaviour is happening consistently, i.e. you end up spending > too little time on all your moves, is your exploitation parameter > correct? There is a reason you use a time management algorithm to > allocate a lot of time in the beginning. You may be doing pointless > searches. > - Would you rather exploit less in that case, thus spending your > allotted time to do more exploration, or would you instead keep > searching instead of aborting and reuse the tree for pondering and/or > your follow-up move? > > Given that people spend a lot of time experimenting on good > exploitation/exploration parameters, I suspect that the last option > (obey the time management, continue searching, reuse the tree) is the > better? > > Christian -- Darren Cook, Software Researcher/Developer http://dcook.org/gobet/ (The Shodan Go Bet) http://dcook.org/work/ (About me and my work) http://dcook.org/blogs.html (My blogs and articles) _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
