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!

andrew cooke · Accepted Answer · 2012-04-10 17:22:08Z

2

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)

edited Apr 10, 2012 at 17:22

answered Apr 10, 2012 at 11:21

andrew cooke

47.1k10 gold badges102 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

BlueRaja - Danny Pflughoeft Over a year ago

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 Over a year ago

yes, i agree - i was just trying to keep things relatively simple. the code i gave identifies a group.

Shayan_Aryan · Accepted Answer · 2016-09-17 09:09:49Z

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)

xlm · Accepted Answer · 2017-02-11 02:42:03Z

0

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.

edited Feb 11, 2017 at 2:42

xlm

7,72415 gold badges59 silver badges60 bronze badges

answered Feb 10, 2017 at 17:37

user1928473

411 gold badge4 silver badges10 bronze badges

Comments

bvdb · Accepted Answer · 2021-11-29 13:56:10Z

-1

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.

edited Nov 29, 2021 at 13:56

answered Apr 12, 2019 at 7:27

bvdb

25.2k11 gold badges123 silver badges135 bronze badges

2 Comments

Folkert van Heusden Over a year ago

That person wants to implement it themselves. Using a library is not implementing it yourself.

bvdb Over a year ago

@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.

Collectives™ on Stack Overflow

JAVA - Go game algorithm

4 Answers 4

2 Comments

Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related