> -----Original Message----- > From: Don Dailey <[email protected]> > To: computer-go <[email protected]> > Sent: Sat, 6 Jun 2009 5:59 pm > Subject: Re: [computer-go] Tweak to MCTS selection criterion
> 2009/6/6 <[email protected]> > I think this is?one of those?design decisions that nobody takes on faith. We > all wind up testing it both ways and in > various combinations. > > An additional advantage of using the number of visits is that branches at the > root become mathematically > eliminated and can be pruned away. It often also allows the search to be > stopped early. It can save a lot of time > for forced moves. > Let me see if I understand what you are saying here.??? > If you have set a goal time for thinking of 10 seconds,? and let's say 6 > seconds have progressed,?? then it might be > possible to stop the search early if you do the math and see that it's not > possible for any other move to have more > visits given an additional 4 seconds??? > So when there is a position that has only a single clearly best move, perhaps > a capture that cannot wait or a > necessary atari defense,? then you can probably save as much (or close to) as > half the thinking time on that move.? >??? Is this correct?????? Yes. (Although, in practice, it's lucky to shave a third off the time.) There is an additional, hard to qualify, benefit. Long before the winning move has it locked up, some moves may be mathematically eliminated, so any playouts through them would be totally wasted (assuming we can ignore RAVE). > So if this understanding is correct, then it still makes sense to do the > "pebbles" test at this point and check to see > if another move has a higher score before stopping the search.??? If the move > really is forced and necessary,? then ?> the answer will be no and you can stop early.? If there is a move that currently appears better but with a "too small" > sample,? then it seems foolish to stop early.??? If the move is a result of > just a few lucky playouts, then it will quickly > be revealed and you can still stop early. Sounds plausible... But I've tested this. You've tested this. Any benefit seems to be pretty hard to measure. - Dave Hillis ?
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
