On Tue, May 13, 2008 at 3:08 PM, Mark Boon <[EMAIL PROTECTED]> wrote: > > On 13-mei-08, at 15:44, Álvaro Begué wrote: > > > > On Tue, May 13, 2008 at 2:28 PM, Mark Boon <[EMAIL PROTECTED]> > wrote: > > > > > > > > On 13-mei-08, at 15:08, Jason House wrote: > > > > > > The range of the random number is reduced by one after each failed > lookup. > > > Shuffled data has no impact on future use of the array of empty points. > > > > > > OK, I understand now why a point at the end (or beginning) is a little > less > > > likely to be picked. Although I still have doubts whether that will lead > to > > > a noticable bias, I'll try to think about it. > > > > > > > I don't care much about it being noticeable. This thread is about > > putting bots on CGOS that use a reproducible algorithm, to help people > > detect bugs in their implementations. As part of specifying what these > > bots do, we should all pick the next move in a playout using the same > > criteria. If we agree to use uniform distribution among empty > > non-eyeish points, that's what should be implemented. > > > > > > Indeed it seems I misunderstood. I thought the general algorithm needed to > be the same, not necessarily the exact implementation. Why not publish some > pseudo-code with the exact statements then? Seems a bit less prone to errors > then by talking about it.
No, we don't need to all use the same implementations. You can implement uniformly picking a random non-eyeish point any way you like. I actually don't use the method we've talked about. The problem with the other method is that it implements something else. > > > I would imagine moving an illegal point towards the end and only start > > > including it when the other 'legal' moves run out can lead to terrible > bias > > > however because they may not remain illegal for very long and actually > > > become important points to play. A ko-point is probably the most extreme > > > example of that. > > > > > > > I don't think you understood the algorithm. The eyeish point is > > removed from the lottery only for picking this particular move, not > > for the rest of the playout. > > > > Yes, again I misunderstood. So you do another random lookup each time you > hit an illegal point? That could turn out very expensive, especially by the > end of the game. You can try it. It's actually not that expensive. A long time ago I modified libego to use this method and it didn't slow it down much (sorry, I can't remember the fraction of speed lost). > > > Anyway, I don't bother to order the empty-point-list or scramble them in > any > > > way prior to the game. So the first point is the 1-1 point and the last > is > > > the 19-19 point (or whatever boardsize you're playing) so I have no > qualms > > > about those moves being a little less likely to be played. Or even a lot > > > less. I think it would actually be beneficial. > > > > > > > Reproducibility was the point, not strength of the bot. > > > > I'd say, share the source if that's the objective. I doubt you'll get real > reproducibility any other way. Why not? The only things we haven't clearly specified are the UCT formula to use and how we end playouts (although there is only one natural choice for this last part, I believe). > > > If this asymmetry really bothers you, you could very easily fix this by > > > wrapping the search around. There's no asymmetry in a circle. > > > > > > > That doesn't fix anything. > > > > Why not? The whole argument is about a bias against points towards the end. > In a circular list there is no 'end'. No, the whole argument is about bias towards points that happen to be immediately after eyeish or illegal points. Álvaro. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
