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)

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:

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

Enough to get you started.