Author |
Topic: A cautionary note about randomness (Read 1495 times) |
|
ddyer
Forum Guru
Gender: 
Posts: 66
|
 |
A cautionary note about randomness
« on: Aug 28th, 2012, 12:46pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
Manuel
Forum Guru
Arimaa player #4020
Gender:
Posts: 58
|
|
Re: A cautionary note about randomness
« Reply #1 on: Aug 29th, 2012, 2:48pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: A cautionary note about randomness
« Reply #2 on: Aug 30th, 2012, 3:57am » |
Quote Modify
|
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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: A cautionary note about randomness
« Reply #3 on: Sep 3rd, 2012, 7:28am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: A cautionary note about randomness
« Reply #4 on: Sep 4th, 2012, 4:48pm » |
Quote Modify
|
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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: A cautionary note about randomness Part 2
« Reply #5 on: Sep 7th, 2012, 4:58pm » |
Quote Modify
|
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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print