Re: [Computer-go] A cautionary note about randomness
Hi Dave. This sounds like a similar problem to the poor performance observed as a result of clustering when using linear probing to resolve collisions in hash tables. Steve On Tue, Aug 28, 2012 at 7:44 PM, Dave Dyer dd...@real-me.net wrote: 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. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go -- Steve Kroon | Computer Science Division, Stellenbosch University (021) 808 9375 (Office) | (084) 458 8062 (Cell) | (086) 655 4386 (Fax) http://www.cs.sun.ac.za/~kroon | kr...@sun.ac.za | kroonrs (Skype) ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] A cautionary note about randomness
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. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] A cautionary note about randomness
If you use bitboards, you can generate all the moves without making an explicit list of them: You simply have four 64-bit numbers that indicate the pieces that can be moved in each direction. Population count is very fast, so you can figure out how many moves you have, then you pick a random index and then you have to find what direction and what location correspond to that index. Is that what you were doing? In any case, I imagine heavy playouts are very important in this game, so I don't know if being clever about making light playouts fast makes much sense. On Tue, Aug 28, 2012 at 1:44 PM, Dave Dyer dd...@real-me.net wrote: 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. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
