I've spent a lot of time struggling with this; it can have a huge
impact on performance. The key thing to remember is to keep the
common case fast.
Orego currently maintains a list (technically a stretchable array,
analogous to the java.util.ArrayList class) of vacant points. I
shuffle this list at the beginning of every playout. When it's time
to choose a move, I work through this list until I find a legal move.
Since vacant points are almost always legal, this usually produces a
legal move very quickly.
I believe it's not worth maintaining a set of legal moves; when
you're choosing a move randomly, you're not going to consider most of
them, so any time spent checking their legality would be wasted.
Maintaining a set of vacant points, on the other hand, is worthwhile,
as it allows you to completely skip over verifying that the occupied
points are illegal.
If your description of libego is accurate, it introduces a bias. If
point X is vacant but illegal (say, it's inside an enemy eye), the
next vacant point is twice as likely to be selected as some vacant
point that doesn't follow an illegal one. I proposed an elaborate way
to get around this bias here:
https://webdisk.lclark.edu/xythoswfs/webui/_xy-2352013_1-t_Gct7yJ5s%22
but I now believe that shuffling a list of vacant points is faster.
Peter Drake
http://www.lclark.edu/~drake/
On May 27, 2007, at 10:21 AM, Jason House wrote:
As I get into the home stretch of rewriting the core of my bot, I
want to add a monte carlo player. I've realized that picking a
random move to play is non-trivial since it's such a key element in
playout speed.
An array of legal positions has easy lookup, but may not be easy
to maintain... I guess it'd require storing a mapping between board
position and index into the legal positions array so that a move
that becomes illegal can be quickly removed (by moving the item
from the tail of the array into the empty location).
Looking at libego, I see it does a variant on this where it
maintains an array of empty points. If the random index it picks
is disallowed, it'll scan through the array (with wrapping around
the end) until it either finds an allowed move or returns to its
starting point.
Which methods have people tried and what works best?
_______________________________________________
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/
