[computer-go] How to improve Orego

[Peter Drake]

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 at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/