Hello,
I am looking for an efficient data structure and algorithm to calculate the
number of stones in the same group.
I believe this should've been done by someone else earlier.
But I couldn't find anything directly related so far when I searched the web
and the archives.
My closest guess of others' work is GNU Go, and I found something related to
what I'm looking for.
If I understood correctly, (a worm)=(a string)=(a group of stones) in GNU Go.
So, a function to calculate the number of stones in the same worm should be
able to calculate what I want.
Function countstones(int str) in engine/board.c is used in function build_worm
in order to compute the number of stones in the same group. Is my understanding
correct?
Well, I read the source codes and the manual, and understood how it works to
some levels.
But I don't fully understand to the level I can write my own program or use the
exisiting codes.
Does anybody have any pointers to help this situation?
Just in case, I'd like to describe the problem I'm attacking below.
This problem is described the best in a figure given below.
a b c d e f g h j
1 . . . . . . . . . 1
2 . . . . . . . . . 2
3 . . O . . . . . . 3
4 . . O . . . . . . 4
5 . . O O . . . . . 5
6 . # O # . . . . . 6
7 . # # # . . . . . 7
8 . . # . . . . . . 8
9 . . . . . . . . . 9
a b c d e f g h j
In above example, both black (#) and white (O) have a group of stones,
respectively.
Black's group has six stones, and white's group has five stones.
I'd like to compute the number of stones incrementally as a new stone is placed.
Say, a white stone is placed at 3b as given below.
Then the number of stones in the white's group should be recalculated, starting
from the the location 3b.
a b c d e f g h j
1 . . . . . . . . . 1
2 . . . . . . . . . 2
3 . O O . . . . . . 3
4 . . O . . . . . . 4
5 . . O O . . . . . 5
6 . # O # . . . . . 6
7 . # # # . . . . . 7
8 . . # . . . . . . 8
9 . . . . . . . . . 9
a b c d e f g h j
This is a simple example to exmplain the problem.
The data structure and algorithm should handle more complex situations with a
multiple number of groups and more complicated shapes of stones.
Could you provide me a pointer to solve this problem?
Thanks!
Best regards,
Tae-hyung D. Kim
!!!
Friends are angels who lift us to our feet when
our wing have trouble remembering how to fly.
!!!
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
