[computer-go] Chains and liberties

["Mark Boon" <tesuji@xxxxxxxxx>]

There have been some discussions here before related to chain (or also
called 'block')and liberty administration.

In the Go library I made available it's not included, which seems a rather
serious caveat for a Go library. The reason I didn't include it was because
the one I have is a bit restrictive. It's fast in itself, but has the
restriction it doesn't keep stone-lists and liberty lists. This meant that
the 'on-demand' functions that I have that retrieve these lists started to
take up a considerable percentage of the total time taken by the tactical
reader and the life-and-death reader.

Now several ideas have past by in this list to address this issue. It's such
a basic thing that every Go program needs it. It's also one of those things
that are simple enough to 'solve' once and for all, make a basic reference
implementation and be done with it.

What I want to do here is describe exactly what the liberty and chain
administration needs to do exactly. And I'll try to analyse what minimal
computational work is required to acomplish this based on the ideas I've
seen here and the ones I had myself.

I hope then that people can either point out mistakes in my thinking, or
provide a more optimal solution. Whichever way, I can then make an
implementation based on these ideas and make it public in my library. I know
some have suggested looking at the implementation in GNU Go, but I don't
want anything in my library that is restricted by the GNU license.

OK, so what do we need.

- A board array, it records what color stone is at what point.
- A chain array that points to a chain data object at each point of the
board where there's a stone.
- The chain data object holds basic information like its number of
liberties, its color (although maybe redundant in respect to 'board'), a
list of its liberties and a list of the stones in the chain. Other
information can be added at will of course.
- A method that plays a move, resulting (usually) in a stone to be added.
- A method that reverses the playing of a move, called takeback. Moves can
only be taken back in the order they were played.

Let's first look at playing a move. I distinguish three possible cases:
1) playing a single stone that results in a new chain, with one stone in it
and up to four liberties.
2) adding a stone to an existing chain, increasing the stone list by one. It
could reduce the number of liberties by one, or increase by up to two.
3) merging two or more existing chains.

Case 1.
This is the simplest case and should take constant time.

Case 2.
Adding the stone takes constant time.
Removing the liberty occupied by the added stone takes O(n) where n is the
number of liberties in the existing chain. (Is there a way to do it in
constant time?)
The empty points next to the added stone need to be merged into the existing
liberty list. David mentioned he kept the liberty-lists sorted so adding
would take O(n). This can be done in constant time at the cost of using
considerably more memory per chain. Would that be worth it? Theoretically a
chain can have up to 229 liberties, but in practice the average is probably
more in the neighbourhood of 4. Does David store the existing liberty-list
for easy reversal? In that case a copy of the liberty-list needs to be made,
taking O(n)?

Case 3.
I like Davids idea of keeping the existing data-structures for easy
reversal. So I assume the way to go is to create a new Chain data-structure
and keep te old ones.
Adding all the stones and marking the Chain object in the chain array takes
O(n) where n is the total number of stones involved. If we use Davids method
of sorted liberty lists, making the new liberty-list also takes O(n) where n
is the cumulative liberty count of the chains involved. If we use the more
memory intensive solution I have in mind, it also takes O(n) but probably
with less code (and therefore faster?).

All three cases have in common that the added stone can take away a liberty
of chains of the opposing color. This takes O(n) where n is the cumulative
liberty count of the opponents neighbouring chains. When any of these chains
now have liberty-count of 0 we get an expensive operation of removing this
chain from the chain array (but keep it for reversal) and increasing the
liberties of the chains next to the captured chain. This would really
benefit from being able to add a liberty to a chain in constant time, but
captures are relatively rare.

There's one case that I'll skip for now, as it's extremely rare and by some
rules illegal, and that is the case of multiple suicide.

Now taking back a move. We can distinguish the same three cases as with
playing a move.

Case 1.
Removing a single stone and its chain datastructure should take constant
time.

Case 2.
Removing a single stone from the existing chain-datastructure takes constant
time.
If we saved the liberty-list, restoring it will also take constant time.
Otherwise we have to remove empty points next to this stones from the
liberty-list (which takes O(n) for each) IF they're not next to another
stone in the chain. And we need to add as a liberty the point this stone was
occupying.

Case 3.
Restoring the chains and liberty-lists takes constant time, but marking the
chain array with the proper references to the chain data-structure takes
O(n) where n is the total number of stones in the split chains.

In the case of captured chains, we can restore the chains saved for reversal
and mark the chain array which takes O(n). Any point in these chains need to
be removed from opposing neighbouring chains as liberties which takes O(n*m)
where n is the number of stones and m is the average number of liberties of
the neighbouring chains.

Well, quite long for something that seems so basic. The two open questions
are:
- is there a liberty-removal procedure possible that takes constant time?
- is it worth the extra memory (a bit-map of the full board per chain) to be
able to add a liberty in constant time?

Did I miss anything? Any errors in my thinking?





_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/