[computer-go] 10k UCT bots

[Mark Boon]

On 13-mei-08, at 15:44, Álvaro Begué wrote:

> On Tue, May 13, 2008 at 2:28 PM, Mark Boon  
> <tesujisoftware at gmail.com> 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.

>> 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.

>
>> 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.

>
>> 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'.

Mark