[Computer-go] A cautionary note about randomness

Álvaro Begué alvaro.begue at gmail.com
Tue Aug 28 11:03:56 PDT 2012


If you use bitboards, you can generate all the moves without making an
explicit list of them: You simply have four 64-bit numbers that
indicate the pieces that can be moved in each direction. Population
count is very fast, so you can figure out how many moves you have,
then you pick a random index and then you have to find what direction
and what location correspond to that index. Is that what you were
doing?

In any case, I imagine heavy playouts are very important in this game,
so I don't know if being clever about making light playouts fast makes
much sense.


On Tue, Aug 28, 2012 at 1: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



More information about the Computer-go mailing list