JAVA - Go game algorithm

Question

I am trying to implement an algorithm to clear dead stones in my Go game.

I hear that floodfill is the best to achieve this as using it recursively would be most effiecient and easier to implement.

I am having trouble using it within my code and was wondering how I should go about implementing it.

This is one of my classes, it is pretty self explanatory.

import java.io.*;
public class GoGame implements Serializable {
 int size;
 char[][] pos; // This is the array that stores whether a Black (B) or White (W) piece is stored, otherwise its an empty character.
 public GoGame(int s){
 size = s;
 }
 public void init() {
 pos = new char[size][size];
 for (int i=0;i<size;i++) {
 for (int j=0;j<size;j++) {
 pos[i][j] = ' ';
 }
 }
 }
 public void ClearAll() {
 for (int i=0;i<size;i++) {
 for (int j=0;j<size;j++) {
 pos[i][j] = ' ';
 }
 }
 }
 public void clear(int x, int y) {
 pos[x][y]=' ';
 }
 public void putB(int x, int y) { //places a black stone on the board+array
 pos[x][y]='B';
 floodfill(x,y,'B','W');
 }
 public void putW(int x, int y) { //places a white stone on the board+array
 pos[x][y]='W';
 floodfill(x,y,'W','B');
 }
 public char get(int x, int y) {
 return pos[x][y];
 }
 public void floodfill(int x, int y, char placed, char liberty){
 floodfill(x-1, y, placed, liberty);
 floodfill(x+1, y, placed, liberty);
 floodfill(x, y-1, placed, liberty);
 floodfill(x, y+1, placed, liberty);
 }
}

x and y are the coordinates of the square, placed is the character of the stone put down, liberty is the other character

Any help would be amazing!

Answer 1

while the other answers are technically correct, you are also missing a lot more logic related to go. what you need to do is, i think (on a B move):

for each W neighbour of the move:
 check that W group to see if it has any liberties (spaces)
 remove it if not

flood fill is useful for finding the extent of a group of stones, but your routine needs a lot more than that (i'm simplifying here, and also trying to guess what this routine is used for - see comments below this answer).

given the above, a flood fill that identifies all the stones in a group would be something like this (note that it uses a second array for the fill, because you don't want to be changing pos just to find a group):

public void findGroup(int x, int y, char colour, char[][] mask) {
 // if this square is the colour expected and has not been visited before
 if (pos[x][y] == colour && mask[x][y] == ' ') {
 // save this group member
 mask[x][y] = pos[x][y];
 // look at the neighbours
 findGroup(x+1, y, colour, mask);
 findGroup(x-1, y, colour, mask);
 findGroup(x, y+1, colour, mask);
 findGroup(x, y-1, colour, mask);
 }
}

you can call that to identify a single group (and copy it into mask), so it will help you identify the members of a W group that neighbour a B move (for example), but it is only a small part of the total logic you need.

finally, note that if you want to do something with every stone in a group you have two options. you can call a routine like the one above, and then loop over mask to find the group, or you can put the action you want to do directly inside the routine (in which case you still use mask to control the extent of the flood fill in the test && mask[x][y] == ' ' but you don't use it as a result - all the work is done by the time the routine returns).

(programming something to handle go correctly, following all the rules, is actually quite complex - you've got a lot of work ahead... :o)

• BlueRaja - Danny Pflughoeft: The term "dead" can refer to a group of stones which has no liberties, but more often a "dead" group is simply one whose removal can be forced. These stones will still have liberties, but are removed at the end of the game regardless. There is no absolute way to tell which stones are dead, as the rules are not actually well-defined on the matter - so it's simply up to the players to agree which stones are dead. But they still need to be able to identify which groups are dead - so I think what OP is really asking is, how to identify groups of stones.
• andrew cooke: yes, i agree - i was just trying to keep things relatively simple. the code i gave identifies a group.

Answer 2

I'd use false proof for that. Here is how I find captured stones:

private static final int SIZE = 8;
private static final int VACANT = 0; //empty point
private static final int MY_COLOR = 1; //Black
private static final int ENEMY_COLOR = 2; //White
private static final int CHECKED = 50; //Mark for processed points
private static final int OUT = 100; //points out of the board
private static boolean isCaptured(int col, int row, int[][] board) {
 boolean result = !isNotCaptured(col, row, board);
 cleanBoard(board);
 return result;
}
private static boolean isNotCaptured(int col, int row, int[][] board) {
 int value = board[col][row];
 if (!(value == MY_COLOR || value == CHECKED))
 return true;
 int top = row < SIZE - 1 ? board[col][row + 1] : OUT;
 int bottom = row > 0 - 1 ? board[col][row - 1] : OUT;
 int left = col > 0 ? board[col - 1][row] : OUT;
 int right = col < SIZE - 1 ? board[col + 1][row] : OUT;
 if (top == VACANT || right == VACANT || left == VACANT || bottom == VACANT)
 return true;
 board[col][row] = CHECKED;
 return (top == MY_COLOR && isNotCaptured(col, row + 1, board))
 || (bottom == MY_COLOR && isNotCaptured(col, row - 1, board))
 || (left == MY_COLOR && isNotCaptured(col - 1, row, board))
 || (right == MY_COLOR && isNotCaptured(col + 1, row, board));
}
private static void cleanBoard(int[][] board) {
 for (int i = 0; i < SIZE; i++) {
 for (int j = 0; j < SIZE; j++) {
 if (board[i][j] == CHECKED)
 board[i][j] = MY_COLOR;
 }
 }
}

Then you can call method like this:

isCaptured(5, 4, board)

Answer 3

I think that BFS will be better for this case because you need to explore the neighbors first, so that if any of them is captured then the point is captured.

Answer 4

As others pointed out, there is also a "ko rule" in Go which roughly means that you are not allowed to capture back immediately when a single stone is captured (simplified). In summary, you may want to use an existing library for this.

I recommend the brugo repository, which is available in maven.

<!-- https://mvnrepository.com/artifact/be.brugo/brugo -->
<dependency>
 <groupId>be.brugo</groupId>
 <artifactId>brugo</artifactId>
 <version>0.1.0</version>
</dependency>

It roughly works like this. (warning: code not tested)

// create a starting position
Position position = new Position(boardSize, komi);
// play a move
Intersection whereToPlay = Intersection.valueOf(4,4);
IntStatus colorToPlay = IntStatus.BLACK;
Position position2 = position.play(whereToPlay, colorToPlay);
// watch the result.
IntStatus[][] matrix = position2.getMatrix()

It also contains objects to export to Load/Save SGF. The loading of SGF files does not only support UTF-8 but also Asian encodings. Here is a screenshot that shows how difficult this is to implement yourself:

A picture of some of the code

If you also plan to use javafx, then run this demo: brugo.go.ui.javafx.goban.GobanComponentDemo

Enough to get you started.

• Folkert van Heusden: That person wants to implement it themselves. Using a library is not implementing it yourself.
• bvdb: @FolkertvanHeusden I disagree on that. He wrote "I am trying to implement ...". That states what he is doing, but not WHY. Your assumption is that he does it because he WANTS to do it. However, I don't think this is the case. He could be unaware of existing solutions, or scared of their complexity. He is stating what he has tried so far to solve his problem. (as any good question should) - My opinion: he can save 2 weeks by using a lib. Writing your own, is as crazy as writing your own XML parser.