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