[computer-go] Another beginner question: string management

[Michael Williams]

I thought Libego used this:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure


Carter Cheng wrote:
> Thanks for pointing to the existence of this document. It clarifies some things about a conventional light playout UCT design(It also answered a question about pseudo-liberties I guess they are equivalent to what I term |multi set liberty|). From the code I gather Orego (thus libEgo) does update all the pointers to the chain record.
> 
> There are still a few design tradeoffs I dont quite understand such as caching adjacent vertex properties in the vertex. How much and why does this result in a speedup?
> 
> Regards,
> 
> Carter.
> 
> 
> 
> --- On Fri, 5/16/08, Peter Drake <drake at lclark.edu> wrote:
> 
>> From: Peter Drake <drake at lclark.edu>
>> Subject: Re: [computer-go] Another beginner question: string management
>> To: "computer-go" <computer-go at computer-go.org>
>> Date: Friday, May 16, 2008, 4:39 PM
>> Carter:
>>
>> It might help to look at the Orego code. In the doc
>> directory,  
>> there's a file called
>> Board-data-structures-explained.pdf.
>>
>> Orego's current board-handling data structures are
>> basically a Java  
>> "translation" of Lukasz Lew's Library of
>> Effective Go Routines (EGO),  
>> although I've gone to somewhat greater length to
>> explain them. If you  
>> find C++ easier to read than Java, by all means use
>> Lew's code.
>>
>> Orego is here (you'll have to download and unpack the
>> latest .jar):
>>
>> http://www.lclark.edu/~drake/Orego.html
>>
>> Peter Drake
>> http://www.lclark.edu/~drake/
>>
>>
>>
>> On May 16, 2008, at 4:29 PM, Carter Cheng wrote:
>>
>>> I am having some difficulties deciding on a string
>> management  
>>> scheme which copes gracefully with merging groups. A
>> first glance  
>>> for me this seems like it is quite a slow operation
>> akin to  
>>> capture. The problem is how to have each stone vertex
>> know which  
>>> chain record to look up for information. I am curious
>> how this is  
>>> done in the current generation of MC bots.
>>>
>>> Is the naive way the best i.e. going through each
>> stone and  
>>> updating the pointer to the record?
>>>
>>> Regards,
>>>
>>> Carter.
>>>
>>>
>>>
>>> _______________________________________________
>>> 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/
> 
> 
>       
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>