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
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
