On 12/4/06, Peter Drake <[EMAIL PROTECTED]> wrote:
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.)
For me it is probably faster to use a list of empty points (an array + length in practice). I ignore ko and allow any suicides during playout.
In any case, my profiling data indicates that choosing the random move per se is not the expensive part; playing the move is.
For me generation of random move is quite expensive as playing takes 170 CC on average (1/3 total time). With list representation eyes are biggest problem, because near the end of the playout they make the most of empty intersections. I deal with eyes by randomizing list of empty intersections before the playout, and while searching non-eye I go through them in circular manner. Best Regards, Łukasz
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/
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
