2009/6/6 <dhillism...@netscape.net> > > -----Original Message----- > > From: Don Dailey <dailey....@gmail.com> > > To: computer-go <computer-go@computer-go.org> > > Sent: Sat, 6 Jun 2009 5:59 pm > > Subject: Re: [computer-go] Tweak to MCTS selection criterion > > > 2009/6/6 <dhillism...@netscape.net> > >> > 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. >
I had the early stop rule and didn't know if anyone else had thought of it. But I never considered the pebbles rule, which somewhat conflicts with the early stop rule. But as I layed out above I think you could do both. This is probably one of those things that adds a little bit but is difficult to measure. - Don > > > - Dave Hillis > > > > > > ------------------------------ > Wanna slim down for summer? Go to America Takes it > Off<http://www.aolhealth.com/diet/weight-loss-program/?ncid=emlcntusheal00000001>to > learn how. > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
