1

I am currently writing some code to deal with Go boards. A Go board is represented as an array of colors. The array has size × size entries and represents a two-dimensional square board.

enum color {
    EMPTY,
    BLACK,
    WHITE,
};

struct go_board {
    unsigned int size;
    enum color intersections[];
};

When enum color player moves, the following procedure applies: (See rules)

  1. [...]
  2. a point P, not colored C, is said to reach C, if there is a path of (vertically or horizontally) adjacent points of P's color from P to a point of color C.
  3. Clearing a color is the process of emptying all points of that color that don't reach empty.
  4. [...]
  5. A move consists of [...] clearing the opponent color, and then clearing one's own color.

I am looking for a fast (in terms of noth computational complexity and actual speed) algorithm to clear a board. Can you help me?

fuz
  • 88,405
  • 25
  • 200
  • 352
  • 3
    Have you measured your "slow" method and determined it is a bottleneck in your application? First: make it work correctly; don't worry about performance. – pmg Feb 12 '13 at 11:03
  • @pmg The "slow" method I am thinking of is so uggly that I have not yet tested it. The computational complexity is O(nˆ4) where n is the size of the board. – fuz Feb 12 '13 at 11:05
  • @pmg I am interested in how to solve it efficiently, not just in how to solve it at all. If just solving a problem would be sufficient, we could just use stoogesort all the time... – fuz Feb 12 '13 at 11:09
  • @pmg Also, consider a Go AI. It has to clear the board after every move. Clearing the board therefor might be a bottleneck. – fuz Feb 12 '13 at 11:11
  • I welcome the baduk tag :) But it should maybe have been weiqi or weichi (as the game probably originated in china)... anyway, less ambiguous than "go". – Olivier Dulac Feb 12 '13 at 11:13
  • @Olivier The problem with weiqi is the ambiguity in the spelling. Anyway, we could make tag synonyms. – fuz Feb 12 '13 at 11:18
  • @FUZxxl: If you'd like to clear the board after every move, incremental algorithms would be much more useful. – thiton Feb 12 '13 at 11:22
  • @thiton Maybe it is a good idea to keep track of a groups liberties. – fuz Feb 12 '13 at 11:25

2 Answers2

3

Use image processing's flood-filling algorithms. First, seed with the empty points and fill all positions that are white or empty; all non-filled positions with white stones will be dead. Repeat with black.

thiton
  • 35,651
  • 4
  • 70
  • 100
  • This seems to be like a O(n²) algorithm and looks pretty nice. I am gonna look at this. Thank you! – fuz Feb 12 '13 at 11:10
  • this could work but I have to admit I'm not sure I understand. And it may not work : in Go, some groups are unconditionally alive (2 or more eyes, or several false eyes between interconnected groups), some others are "interdependently" alive (seki, ...). I'm not sure this can trivially be put back to a simple filling algorithm. – Olivier Dulac Feb 13 '13 at 09:32
  • @Olivier I just ask about groups that shall be removed because they have no liberties left. More calculations are not needed in my usecase. – fuz Mar 13 '13 at 17:40
0

You can keep a reference to each group on the board, and keep track of their liberties. For each added stone, you just merge/update at most 4 groups together. Is it me or this sounds like O(k)?:)

(edited)

okw
  • 3
  • 1
  • 5