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/
