[Computer-go] A cautionary tale about randomness, Part 2
Dave Dyer
ddyer at real-me.net
Fri Sep 7 14:57:18 PDT 2012
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.
More information about the Computer-go
mailing list