[Computer-go] A cautionary tale about randomness, Part 2
Kahn Jonas
jonas.kahn at math.u-psud.fr
Fri Sep 7 15:14:49 PDT 2012
Your final algorithm is still slightly biased, towards moves of cells
with few moves, but that's a second-order effect.
You can make it completely unbiased by the following modification:
Pick A random Starting Cell,
> Pick A random Direction not tried yet for this cell,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> If that's a legal move, return it,
> otherwise continue with the rest of the cells
The ^^^ should be suppressed. Each try should be independent on the
history of tries.
Notice that this is unbiased if you test for each cell potentially in
any driection, even if they are on the edge; or if you never test a
priori impossible directions, you should weight the initial choice of
the cell by the number of 'a priori' possible directions. Notice that
the second option allows another unbiased algorithm: exactly the same as
yours, with the ^^^, but where the initial random cell is selected
with a weight depending on the number of (a priori possible) not-yet-tested
directions.
Jonas
>
> Applying random move generation to another game, Dvonn this time. The
> original random move algorithm, which was
>
> Generate All Moves
> Pick a Random one and return it.
>
>
> I wrote a simple "Random Move" function, by modifying the existing move generator. The generator that resulted is essentially
>
> Pick A random Starting Cell,
> Pick A random Direction,
> If that's a legal move, return it,
> otherwise loop randomly through all directions,
> otherwise continue randomly with the rest of the cells.
>
> This looked pretty reasonable, but to my surprise, getting 50% more playouts, it still played lots weaker than the original.
>
> I decided this required a more systematic investigation, so I incorporated a Chi Square test into the random move generators, with shocking results. The "original" hit right on the money, with only 5% of the playouts below the 5% probability level. The new algorithm scored in the 80% range.
>
> After some thought, I decided the problem was selecting all directions for a random cell. In Dvonn, some starting cells have 4-5 legal moves, while others have only 1. This leads to over representing the cells that have fewer moves. The next take inverted the directions and the cell choice.
>
> Pick A random Direction,
> Pick A random Starting Cell,
> If that's a legal move, return it,
> otherwise continue randomly with the rest of the cells.
> otherwise loop randomly through all directions,
>
> This scored Chi Square in the 60% range.
>
> Thinking again, I realized that if for example there was only one move on the board that moved "left", it would certainly be chosen when the random direction was left, which is 1/6 of the time, so if the board itself became unbalanced, the random distribution would be skewed too.
>
> So, take next
>
> Pick A random Starting Cell,
> Pick A random Direction not tried yet for this cell,
> If that's a legal move, return it,
> otherwise continue with the rest of the cells
>
> This scores at the desired 5% level, and also plays better due to more playouts.
>
>
> ---
>
> So, hoping I haven't bored you too much with my lessons: My intuition even as an experienced programmer was not good enough, even after several "aha" moments. Biases are subtle. If my second algorithm had played even a little bit better than the first one, there would have been no more investigation.
>
> Bottom line: You need to verify that your randomness really is random enough.
>
>
> _______________________________________________
> 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