[Computer-go] A cautionary note about randomness

Steve Kroon kroon at sun.ac.za
Wed Aug 29 02:29:50 PDT 2012


Hi Dave.

This sounds like a similar problem to the poor performance observed as a
result of clustering when using linear probing to resolve collisions in
hash tables.

Steve

On Tue, Aug 28, 2012 at 7:44 PM, Dave Dyer <ddyer at real-me.net> wrote:

>
> I was recently working on a UCT bot for Arimaa by trying to generate
> a random move directly, instead of generating all moves and selecting
> a random one.  This general method sped up the random playout rate by
> a factor of 5, which seemed wonderful.
>
> Unfortunately, the new faster random bot consistently lost to the
> older, slower bot that was getting 5x fewer playouts.
>
> After some experimentation, I found that the problem was a bias built
> into my random move generator.  At one point in the process, a random
> piece has been selected and it can move in any direction.
>
> The "bad" code selected a random direction, then proceeded clockwise
> in the other directions if that one wasn't legal.
>
> The "good" code selects a random direction among the directions not tried
> yet.
>
>
> It's pretty shocking to me that the "bad" code still had an unacceptable
> bias;
> in fact one so severe that it always played worse, and sometimes made the
> obviously worst possible move.
>
>
>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>



-- 
Steve Kroon | Computer Science Division, Stellenbosch University
(021) 808 9375 (Office) | (084) 458 8062 (Cell) | (086) 655 4386 (Fax)
http://www.cs.sun.ac.za/~kroon | kroon at sun.ac.za | kroonrs (Skype)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20120829/913e1d01/attachment.html>


More information about the Computer-go mailing list