[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