Don Dailey wrote:
Jason House wrote:
On May 13, 2008, at 1:51 PM, Mark Boon <[EMAIL PROTECTED]> wrote:
On 13-mei-08, at 14:10, Álvaro Begué wrote:
What others do is the right thing to do. Your method will introduce
some biases.
Could you elaborate what bias it could lead to? I also do the same
as Jason. I did consider the possibility of a bias but couldn't
immediately think of one.
And I was thinking "let's not repeat this topic"...
The probability of picking a point is proportional to 1 + number of
illegal points before it.
In practice, illegal moves are pretty rare until endgame. At that
point, it's a trade off between bias and speed. Random number
generation is not cheap. I have yet to see empirical proof that the
pick and scan is bad. I've tried both methods in the past and saw no
measurable difference in strength.
I may perhaps take a look at this myself. I think there is a way to
deal with this issue and get the best of both worlds or at least
approach it. If this method does not degrade the quality, it's a
moot point. Otherwise, here is an idea:
1. For each move list size, pre-compute N tables of move list
traversal orderings.
2. At move selection time alternative between them.
So you would have something in the C language like:
int *order[S][C]
I forget to mention that S is the move list size (number of empty points
you are interested in) and C is the number of list orderings you want to
alternate between. And a list is returns that is of size S-1 (since
your first move is selected by calling the random number generater.) A
number like 8 or 16 is good (a power of two) because each time you using
the list to select a move, you can increment a counter so that you use a
different move list ordering the next time you are confronted with a
move list of this same exact size.
Your first move is selected randomly, then from then on you use the
array returned to form an offset from this.
This would pay off if you really wanted something very close to
uniform random and your random number generator was clearly expensive.
I think there is a great deal of chaos that would make this "almost"
perfectly uniform. The first move would be selected as you already
do, using the random number generator but after this you traverse the
list in random order as specified by this pre-computed table. Even
though the bias is still there for any given move, it's basically
non-predictable. On the very next move you will using a different
table which you choose from in round robin fashion.
Don't know how flawed this idea is. I believe it is would come close
to uniformly random but wouldn't be perfect. There would be a minor
bias when measured over a lot of games, it would probably occur that
a certain move was being chosen slightly more often, but nothing like
the bias in the current method.
Is it worth it? Probably not, but just a crazy idea. Likely there
are simpler ways to eliminate most of the bias while still minimizing
the number of random move generations.
- Don
What good does moving it to the end of the list do? Next time around
it's just as likely to be picked as when left in place. Or do you
only process the 'end' after the 'front' moves are all tried?
The range of the random number is reduced by one after each failed
lookup. Shuffled data has no impact on future use of the array of
empty points.
Mark
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
