It's not clear whether this is faster. Determining that a move is
illegal because the point is occupied is very fast; determining that
a move IS legal (i.e., not a suicide or ko violation) is the slow
part, and I avoid that by taking the first legal move I find. (Of
course, once all moves have been tried from a given move, UCT takes
over.)
In any case, my profiling data indicates that choosing the random
move per se is not the expensive part; playing the move is.
Thanks for the suggestion,
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 4, 2006, at 7:52 AM, Chrilly wrote:
In the Orego paper the problem of selecting a move when the board
is filled with stones is mentioned. Orego uses a sort of double-
hashing scheme.
But isn't it trivial to keep a list of empty intersections?
Before the MC-run is started, one builds up this list. If a stone
is placed now on the board, the entry is removed from the list and
the last entry is copied into this slot. In this way the list is
always dense. One can of course not run linearly trough the list to
find the entry which should be removed. Instead one builds at the
beginning another array which is indexed by the board-point and
which contains the index of the point in the empy-point-list. This
second array has to be changed too when the last entry is copied
into the removed slot. With a few operations one gets the big
advantage to sample all the time only the empty points.
I think this solution is much simpler and more efficient than the
double-hashing scheme of Orego.
Chrilly
_______________________________________________
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/