Łukasz Lew wrote:
> 2009/4/8 Gunnar Farnebäck <[email protected]>:
>> Łukasz Lew wrote:
>>>>> ...
>>>>> For a reference you can take a look for a libego implementation:
>>>> Ah, so you already use this idea in libego?
>>> libego uses this idea only for list of stones in chain.
>>> list of liberties are not implemented.
>>> but I guess I will implement it sometime soon.
>> You can find this idea in the GNU Go montecarlo board implementation,
>> although with doubly linked lists, see for example
>> http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c
>> starting at line 43. This code is doing quite a lot of book-keeping to
>> support tunable pattern-based heavy playouts, however, so it may be
>> easier to start with a previous iteration of the code at
>>
http://git.savannah.gnu.org/cgit/gnugo.git/tree/engine/montecarlo.c?id=67cc097ed8c7e326d3b1659ca668326e23f65c3b
>
> Indeed that's almost exactly what I meant.
> I can see that you are using doubly linked list to have a constant
> time liberty_edge removal. Is there any other reason?
To be honest I don't really remember but that was probably the most
important reason. Another possibility is that I became annoyed by the look
of the code needed to traverse around a single linked cyclic list. :-)
> Have you considered amortized constant time (we remove it when we have
> an occasion) approach?
No, not seriously at least. Actually this code hasn't been optimized
at all, so there should be some gains left to be made.
> Lukasz
> PS
> This is nice code to read :)
Thanks.
/Gunnar
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
