On Wed, Apr 8, 2009 at 09:12, Darren Cook <dar...@dcook.org> wrote: >>> Do you have some code demonstrating the above idea? It sounds >>> interesting, but I cannot grasp what the data and algorithm look like. >> >> 4*19*19*4 is around 5.5 kB >> On 9x9 it will be less than 1.5 kB >> >> Are you still interested? > > My own method is a large pre-allocated pool of Chain objects, which use > std::vector, or fixed-size arrays, to store liberties. So I'm using a > lot more memory. If your idea actually works and is just as quick then > of course I'm interested.
The problem is similar to the problem of storing lists of stones in one group. For a reference you can take a look for a libego implementation: The file is in the spirit one class for all including unit tests, so it's big. But just ignore it and track chain_next_v http://github.com/lukaszlew/libego/blob/00264d126ef6aa909dd7f52a668e8fe33e62aeb4/ego/board.cpp chain_next_v is essentially a map vertex -> next_vertex (vertex is board location). chain_next_v implements cyclic linked lists. The trick is that it is implemented as an array of size 19*19*sizeof(vertex). This is possible because one vertex can be always only in one group. Now merging groups is as simple as crossing the lists (line 500). If you have any questions so far, go ahead and ask :) Now the liberties. One liberty can be in many groups. But in only as many as 4. Let's call links between neighboring vertices "pseudoliberties". Now we can create a structure similar to chain_next_v that track all pseudo-liberties of a group. It would be again map implemented as an array indexed by vertex and direction (N,W,S,E). Now when you merge you just go over this list and throw away duplicates. This can be done in linear time using another map-array vertex -> bool. That will have info whether particular liberty (vertex without direction) was already in visited. Hope this helps :) Lukasz > > Darren > > -- > Darren Cook, Software Researcher/Developer > http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic > open source dictionary/semantic network) > http://dcook.org/work/ (About me and my work) > http://dcook.org/blogs.html (My blogs and articles) > _______________________________________________ > 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/
