[computer-go] How to improve Orego

[Łukasz Lew]

On 12/4/06, Peter Drake <drake at lclark.edu> 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 at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>