It is currently Thu Mar 28, 2024 10:37 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
Offline
 Post subject: Efficient algorithm for counting liberties?
Post #1 Posted: Wed May 18, 2022 12:09 am 
Beginner

Posts: 6
Liked others: 3
Was liked: 2
I'm writing a program to analyze life & death problems, and certainly it involves counting liberties.

If the input to the function is,
Code:
. . X X X O O .
X X . X . X O X
. X X X X X O X
X X . O O X . X

(0, 2) //(row, column)

The output should be 7, as the group (chain) including the stone at (0, 2) has 7 liberties.

My current approach is recursively tracking the 4 possible directions and incrementing the count whenever there's an empty space, and put a mark on the vertex at which the counting has been done to not count twice.

The problem of this approach is that it has branches for seeking the different directions and recursion to apply the same operation to the next linked stone. Each step has dependency on the one before, so it has to run sequentially.

It is still fast enough for a one-go, but since this has to be done millions of times in a tree search, I want to make it as fast as possible.

Could you help me on what is an efficient algorithm to count liberties?

Here is a link to my code if you're interested.

Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #2 Posted: Wed May 18, 2022 8:21 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
If the current approach is fast enough for one-go, is it feasible to cache what you've already counted?

E.g. have a hash table keyed by (row/column) pair and as you count the liberties for the first time, store a "group" object that contains a liberty count. Each row/column in the hash table that's part of the same group would have a value of a single group reference. Then when you play a stone in tree search, you can infer if the move joins two distinct groups, and update the reference/liberty count as needed.

Anyway, some sort of caching seems possible.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #3 Posted: Wed May 18, 2022 1:00 pm 
Lives in sente
User avatar

Posts: 914
Liked others: 391
Was liked: 162
Rank: German 2 dan
Some thoughts:

Usually the overhead from parallelizing such computations is significant, so you shouldn't worry too much about parallelizing the algorithm itself. I think it's much more promising to parallelize independent runs.

The most efficient approach is dependent on what you search for what. If you always have only one group that you count, your approach will maybe be the best. If you always count every group on a big board, it is maybe better to do a 3×3 sliding window over the entire board and unify groups afterwards.

_________________
A good system naturally covers all corner cases without further effort.

Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #4 Posted: Wed May 18, 2022 7:19 pm 
Lives in sente

Posts: 757
Liked others: 114
Was liked: 916
Rank: maybe 2d
A decent approach is to approach the entire thing from an incremental-update perspective. Below is how KataGo does it. There are probably much more efficient implementations (e.g. fancy bitboards), but I've been reasonably satisfied with the efficiency of this so far:

* In addition to the normal NxN array whether each board location is black/white/empty, every chain of stones also has a circular singly linked list enumerating its stones.
* An arbitrary stone in the chain is designated as the "head" stone, and all stones in a chain also have a pointer directly to the head in addition to the next stone in the circular chain.
* The head stone also holds a data structure that records the total number of stones in the chain, and how many liberties the chain has.
* This means you always can tell the number of liberties of any chain in constant time, and also you can also always check if any two stones belong to the same chain or not in constant time by seeing if they point to the same head.

* To place a new stone, create a new 1-element list that circularly points to itself, and is the head stone for itself. Count how many liberties it has immediately adjacent and record it. Also decrement one liberty from every unique chain adjacent to the stone (comparing heads to tell if some of the N/S/E/W chains are actually the same chain). Then merge it with every adjacent chain of the same color. Then capture every adjacent opponent chain with 0 liberties. And then maybe capture yourself, if you allow self-capture.

* To merge two chains, find the head stone of both chains and query how many stones are in each chain. Iterate through the *smaller* chain in linear time. For each stone in the smaller chain:
* For each liberty of that stone, if that liberty is NOT adjacent to any stone whose head is the larger chain's head, increment the larger chain's liberties by one.
* Then set that stone's head to be the head of the larger chain.
* Finally after iterating, complete the merge by doing the pointer swapping so that the two circular lists are now a single circular list.

* To capture a chain, it is very similar. Iterate over the circular list, setting each location on the board to empty, and on each location increment one liberty to each unique adjacent chain (comparing heads again to check for uniqueness) as you do so.

* Note that everything above does not use any dynamic memory allocation. I only talk about linked lists conceptually, actually all data is stored as elements of fixed-size arrays based on the board size. All "pointers" in the linked list are simply integer indices indicating the index in the array of the other list element being linked to, rather than being an actual C/C++ pointer. Etc.

A note about liberty counts: you can make the implementation much faster if you use *pseudoliberty* counts instead. The pseudoliberty count of a chain is the same as the liberty count, except that if a chain borders an empty space from more than one side, it counts that empty space once *per* side that it borders it from. If you use pseudoliberty counts, then you can skip all the uniqueness checks and simply increment/decrement once in each direction when a location transitions between filled/empty. And even better, when merging two chains you can skip all liberty management when iterating over the shorter chain. This is because the pseudoliberty count of a merged chain is always simply the sum of the pseudoliberty counts of the two chains being merged. So the only thing you have to do is update the head pointers on the shorter chain, then sum the pseudoliberty counts.

However, there is a big drawback. The liberty count is much more useful than the pseudoliberty count if plan to do any sort of tactical analysis, whether to search for forced captures (i.e. ladders/snapbacks), to provide as an input feature for a neural net, etc. So it can be worth it to go the extra cost of doing real liberty count instead of pseudoliberty count.

Even with true liberty counts, the above is still decently fast, because the majority of merges are between a large group and 1 stone, and so iterating over the shorter chain means you iterate only over 1 stone.


Last edited by lightvector on Wed May 18, 2022 7:39 pm, edited 1 time in total.

This post by lightvector was liked by 4 people: Harleqin, jeromie, Joaz Banbeck, xiver77
Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #5 Posted: Wed May 18, 2022 7:34 pm 
Lives in sente

Posts: 757
Liked others: 114
Was liked: 916
Rank: maybe 2d
Also another note: regardless of what you do, you should strongly consider using an array that is slightly larger than the actual board size you are running on. For example, for a 19x19 board you can use a 21x21 array (actually you can get away with a 20x21, or a 20x21+2 array). Fill the extra border space in this slightly larger array with a special "off-board" value that is none of white/black/empty.

Doing so lets you skip all out-of-bounds checks in all your algorithms. For example, instead of "if (x+1,y) is within bounds and (x+1,y) is empty, increment one liberty" you can simply do "if (x+1,y) is empty, increment one liberty". Because the "off-board" value is not the empty value, everything works. Similarly, because the "off-board" value is also neither black nor white, you will never walk off the board as you trace a chain of a given color even without bounds checks.


This post by lightvector was liked by 4 people: Akura, Harleqin, jeromie, xiver77
Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #6 Posted: Thu May 19, 2022 3:14 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
lightvector wrote:
A decent approach is to approach the entire thing from an incremental-update perspective. Below is how KataGo does it. There are probably much more efficient implementations (e.g. fancy bitboards)


I use bitboards in q5go, and I'll post an outline of the idea here just for reference. I've not made any speed measurements beyond being able to load large sgf files reasonably quickly, I use this method not so much because of speed considerations but because it seems natural to me.

Boards are represented as one set of bits for white stones, one set of bits for black stones. Finding strings of stones and their liberties is essentially a kind of flood-fill operation. When you have a bit mask representing a string of stones, you can find the neighbouring intersections with four shifts: shift up by the board size, shift down by the board size, and shift left/right one after masking out the leftmost/rightmost column. You or all of these together, then you perform an and with the bitmask of stones you are interested in, and you found the neighbouring stones. Repeat until no additional stones of the same colour are found and you have the complete string of stones. Finding the liberties then is another flood step. And-not away all the black and white stones, and your liberties are the popcnt of the resulting bitmask.


This post by bernds was liked by 2 people: Harleqin, xiver77
Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #7 Posted: Fri May 20, 2022 10:20 pm 
Beginner

Posts: 6
Liked others: 3
Was liked: 2
Thank you for all those interesting and helpful ideas. Another approach I was implementing didn't go well, so I'll definitely have a serious read of the replies.

Although it failed, it was interesting enough that I'd like to share the idea. It's not my idea. I got it from here.

The code is this single line of APL.
Code:
⍴⍴,+.<∘.(2>+⍥|.-)⍨⍤,⍤⍳⍤⍴∨.∧⍨⍣≡⍤∧,∘.(=≠0=⊣),

For an input of,
Code:
|0 1 0│
│2 1 0│
│0 2 0│

the output is,
Code:
│0 3 0│
│2 3 0│
│0 2 0│

The positive integers in the input each represents a color mapped to a single positive integer, and there could be more than 2 colors.

The output is the liberty count for all groups in the arbitrarily sized input board.

Since the given input has 3x3 = 9 entries, we will do some operations with 9x9 boolean matrices.

(step-1) The first boolean matrix is the adjacency matrix defining solid connection between stones.
Code:
│1 1 0 1 0 0 0 0 0│
│1 1 1 0 1 0 0 0 0│
│0 1 1 0 0 1 0 0 0│
│1 0 0 1 1 0 1 0 0│
│0 1 0 1 1 1 0 1 0│
│0 0 1 0 1 1 0 0 1│
│0 0 0 1 0 0 1 1 0│
│0 0 0 0 1 0 1 1 1│
│0 0 0 0 0 1 0 1 1│

(step-2) The second boolean matrix is the adjacency matrix that connects the stones of the same color and connects all empty points to all stones.
Code:
│0 1 0 1 1 0 0 1 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 1 1 0 0 1 0│
│0 0 0 1 0 0 0 1 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 1 1 0 0 1 0│
│0 1 0 1 1 0 0 1 0│
│0 0 0 1 0 0 0 1 0│
│0 1 0 1 1 0 0 1 0│

(step-3) Do a bitwise-and of these matrices.
Code:
│0 1 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 0 0 0 0 0│
│0 0 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│

(step-4) Compute the transitive closure of step-3. I honestly have no idea what this is, but to compute this we have to do ∨.∧ with two step-3 matrices. ∨.∧ is the inner product of bitwise-and and bitwise-or. In other words, it's a generalized matrix multiplication with multiplication changed to bitwise-and and addition change to bitwise-or.
Code:
│0 1 0 1 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 1 0 0 1 0 0 0 0│
│0 0 0 1 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│
│0 0 0 0 0 0 0 1 0│

(step-5) Count the liberties by applying ,+.< to step-4. I haven't investigated what this is yet because I couldn't think of an efficient way to do step-4.
Code:
│0 3 0 2 3 0 0 2 0│

I'm currently dealing with 4x8 boards, and this will produce a 32x32 boolean matrix for each step. I actually wrote reasonable AVX optimized code up to step-3. However, the inner product (∨.∧) operation scales badly as the input size gets bigger.

Although it may not be the fastest solution, I still think it's somewhat elegant.

Top
 Profile  
 
Offline
 Post subject: Re: Efficient algorithm for counting liberties?
Post #8 Posted: Fri May 20, 2022 10:50 pm 
Beginner

Posts: 6
Liked others: 3
Was liked: 2
bernds wrote:
When you have a bit mask representing a string of stones, ...

I like your approach, then I'm thinking how it is possible to efficiently get a bit-mask for a string of stones.

Hmm, after writing, I think I can get that bit-mask in a similar way to step 1~3 in the post right before. I'll have a think.

Nope, I had a bit of misunderstanding to your writing. I think I got your algorithm now.

The thing is both the Katago and q5go algorithm has dependency to the previous step, but so does the other algorithms to this problem I skimmed through. Probably, that's the nature of this problem.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group