On Jun 5, 2007, at 12:58 PM, Don Dailey wrote:
On Tue, 2007-06-05 at 12:28 -0700, Peter Drake wrote:
Don't maintain the list of legal moves -- maintain the list of vacant
points (almost all of which are legal). When it's time to pick a
move,
pick a random point in the list and iterate through checking each
move
for legality. As soon as you find a legal one, play it.
But you can do both. It's simpler than it sounds. I'm essentially
doing what you suggest, but it's perfectly random, no bias. And I
doubt there is any cost that can be easily measured.
So I'm only temporarily maintaining a list of illegal but unoccupied
points - this list gets "discarded" as soon as a legal move is tried.
Does that mean you have to regenerate the list every move?
What you are doing is to avoid the call to the random number generator
by
trying the moves as a circular list. This may be faster, but it's
biased, perhaps the bias is insignificant enough that it doesn't have
an impact on the strength.
No, I pick a random point in the list every time, so there's still a
call to the random number generator. Just proceeding through the list
would be horribly biased (unless the list were pre-shuffled, as I was
doing previously).
You might improve the bias by "shuffling on the fly", perhaps when you
find a legal move in the un-occupied point section of the list you
could
do a swap with the first move and a random move.
I did something like this in an earlier version.
I'm wondering if the
biased ordering of the list persists from move to move?
Maybe I benchmark your idea at some point.
Feel free...
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
