Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> A cautionary note about randomness
        
(Message started by: ddyer on Aug 28^th, 2012, 12:46pm)

Title: A cautionary note about randomness
Post by ddyer on Aug 28^th, 2012, 12:46pm

I was recently working on a UCT bot for Arimaa by trying to generate a random move directly, instead of generating all moves and selecting a random one. This general method sped up the random playout rate by a factor of 5, which seemed wonderful.

Unfortunately, the new faster random bot consistently lost to the older, slower bot that was getting 5x fewer playouts.

After some experimentation, I found that the problem was a bias built into my random move generator. At one point in the process, a random piece has been selected and it can move in any direction.

The "bad" code selected a random direction, then proceeded clockwise in the other directions if that one wasn't legal.

The "good" code selects a random direction among the directions not tried yet.

It's pretty shocking to me that the "bad" code still had an unacceptable bias; in fact one so severe that it always played worse, and sometimes made the obviously worst possible move.

Title: Re: A cautionary note about randomness
Post by Manuel on Aug 29^th, 2012, 2:48pm

That is interesting!

I must say I am not too surprised, though: It is known that biases come very critically. On the other hand, the severness of the problem is shocking indeed.

I wonder whether your new method is actually unbiased enough. It may also be important to choose a new piece when a selected random step is not allowed, and not just a new direction.
Furthermore I wonder about biases in selecting the pieces in the first place. Do you first select a piece type and then the piece or do you select randomly out of the whole list of particles?

Title: Re: A cautionary note about randomness
Post by ddyer on Aug 30^th, 2012, 3:57am

It's hard to diagnose problems that are the endpoint of lots of deliberate randomness. All I can say definitively is that making this small change in the randomization resulted in the obviously bad move getting a more appropriate UCT score.

Title: Re: A cautionary note about randomness
Post by clauchau on Sep 3^rd, 2012, 7:28am

Hello Dave. When a rabbit is selected, is the illegal backward direction selected (and rejected) 1/4th of the times ? Then the bad code might be biased in favor of left rabbit move. The same for any piece blocked backward.

Title: Re: A cautionary note about randomness
Post by ddyer on Sep 4^th, 2012, 4:48pm

Right, the "left rabbit" bias could be the actual problem. The point remains that the definition of "select a random move" is a subtle thing.

Title: Re: A cautionary note about randomness Part 2
Post by ddyer on Sep 7^th, 2012, 4:58pm

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.