Go (board game) in Java

Question

Go is a board game (it looks like 5-in-a-row and plays like chess) and I tried to program it in Java.

Rules:

Two players take turn placing stones on a board. The goal is to capture teritory. Stones can be captured (removed from game) if they have no unoccupied adjacent tiles horizontaly/verticaly. Adjacent stones (horizontaly/verticaly) of one color are combined into chains which share unoccupied tiles.

If you're interested here's more.

My code:

I implemented core rules and basic input/output. My goal is to make the game scalable so I can add functionality without breaking everything.

My concerns:

• (main concern) I don't think it's expandable (enough). I had to redo (nearly) everything from scratch because it was complete mess. It works but I think that if I add more game mechanism everything will break. What can I do to avoid this?
• Is Main an acceptable name for a class? Or should it be Game/App or something completely different?
• What about my comments?

Main

package go;
import java.awt.BorderLayout;
import java.awt.Color;
import javax.swing.BorderFactory;
import javax.swing.JFrame;
import javax.swing.JPanel;
/**
 * Builds UI and starts the game.
 *
 */
public class Main {
public static final String TITLE = "";
public static final int BORDER_SIZE = 25;
public static void main(String[] args) {
 new Main().init();
}
private void init() {
 JFrame f = new JFrame();
 f.setTitle(TITLE);
 JPanel container = new JPanel();
 container.setBackground(Color.GRAY);
 container.setLayout(new BorderLayout());
 f.add(container);
 container.setBorder(BorderFactory.createEmptyBorder(BORDER_SIZE, BORDER_SIZE, BORDER_SIZE, BORDER_SIZE));
 GameBoard board = new GameBoard();
 container.add(board);
 f.pack();
 f.setResizable(false);
 f.setLocationByPlatform(true);
 f.setVisible(true);
}}

GameBoard

package go;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import javax.swing.JPanel;
/**
 * Provides I/O.
 * 
 *
 */
 public class GameBoard extends JPanel {
private static final long serialVersionUID = -494530433694385328L;
/**
 * Number of rows/columns.
 */
public static final int SIZE = 9;
/**
 * Number of tiles in row/column. (Size - 1)
 */
public static final int N_OF_TILES = SIZE - 1;
public static final int TILE_SIZE = 40;
public static final int BORDER_SIZE = TILE_SIZE;
/**
 * Black/white player/stone
 * 
 *
 */
public enum State {
 BLACK, WHITE
}
private State current_player;
private Grid grid;
private Point lastMove;
public GameBoard() {
 this.setBackground(Color.ORANGE);
 grid = new Grid(SIZE);
 // Black always starts
 current_player = State.BLACK;
 this.addMouseListener(new MouseAdapter() {
 @Override
 public void mouseReleased(MouseEvent e) {
 // Converts to float for float division and then rounds to
 // provide nearest intersection.
 int row = Math.round((float) (e.getY() - BORDER_SIZE)
 / TILE_SIZE);
 int col = Math.round((float) (e.getX() - BORDER_SIZE)
 / TILE_SIZE);
 // DEBUG INFO
 // System.out.println(String.format("y: %d, x: %d", row, col));
 // Check wherever it's valid
 if (row >= SIZE || col >= SIZE || row < 0 || col < 0) {
 return;
 }
 if (grid.isOccupied(row, col)) {
 return;
 }
 grid.addStone(row, col, current_player);
 lastMove = new Point(col, row);
 // Switch current player
 if (current_player == State.BLACK) {
 current_player = State.WHITE;
 } else {
 current_player = State.BLACK;
 }
 repaint();
 }
 });
}
@Override
protected void paintComponent(Graphics g) {
 super.paintComponent(g);
 Graphics2D g2 = (Graphics2D) g;
 g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
 RenderingHints.VALUE_ANTIALIAS_ON);
 g2.setColor(Color.BLACK);
 // Draw rows.
 for (int i = 0; i < SIZE; i++) {
 g2.drawLine(BORDER_SIZE, i * TILE_SIZE + BORDER_SIZE, TILE_SIZE
 * N_OF_TILES + BORDER_SIZE, i * TILE_SIZE + BORDER_SIZE);
 }
 // Draw columns.
 for (int i = 0; i < SIZE; i++) {
 g2.drawLine(i * TILE_SIZE + BORDER_SIZE, BORDER_SIZE, i * TILE_SIZE
 + BORDER_SIZE, TILE_SIZE * N_OF_TILES + BORDER_SIZE);
 }
 // Iterate over intersections
 for (int row = 0; row < SIZE; row++) {
 for (int col = 0; col < SIZE; col++) {
 State state = grid.getState(row, col);
 if (state != null) {
 if (state == State.BLACK) {
 g2.setColor(Color.BLACK);
 } else {
 g2.setColor(Color.WHITE);
 }
 g2.fillOval(col * TILE_SIZE + BORDER_SIZE - TILE_SIZE / 2,
 row * TILE_SIZE + BORDER_SIZE - TILE_SIZE / 2,
 TILE_SIZE, TILE_SIZE);
 }
 }
 }
 // Highlight last move
 if (lastMove != null) {
 g2.setColor(Color.RED);
 g2.drawOval(lastMove.x * TILE_SIZE + BORDER_SIZE - TILE_SIZE / 2,
 lastMove.y * TILE_SIZE + BORDER_SIZE - TILE_SIZE / 2,
 TILE_SIZE, TILE_SIZE);
 }
}
@Override
public Dimension getPreferredSize() {
 return new Dimension(N_OF_TILES * TILE_SIZE + BORDER_SIZE * 2,
 N_OF_TILES * TILE_SIZE + BORDER_SIZE * 2);
}
}

Grid

package go;
import go.GameBoard.State;
/**
 * Provides game logic.
 * 
 *
 */
public class Grid {
private final int SIZE;
/**
 * [row][column]
 */
private Stone[][] stones;
public Grid(int size) {
 SIZE = size;
 stones = new Stone[SIZE][SIZE];
}
/**
 * Adds Stone to Grid.
 * 
 * @param row
 * @param col
 * @param black
 */
public void addStone(int row, int col, State state) {
 Stone newStone = new Stone(row, col, state);
 stones[row][col] = newStone;
 // Check neighbors
 Stone[] neighbors = new Stone[4];
 // Don't check outside the board
 if (row > 0) {
 neighbors[0] = stones[row - 1][col];
 }
 if (row < SIZE - 1) {
 neighbors[1] = stones[row + 1][col];
 }
 if (col > 1) {
 neighbors[2] = stones[row][col - 1];
 }
 if (col < SIZE - 1) {
 neighbors[3] = stones[row][col + 1];
 }
 // Prepare Chain for this new Stone
 Chain finalChain = new Chain(newStone.state);
 for (Stone neighbor : neighbors) {
 // Do nothing if no adjacent Stone
 if (neighbor == null) {
 continue;
 }
 newStone.liberties--;
 neighbor.liberties--;
 // If it's different color than newStone check him
 if (neighbor.state != newStone.state) {
 checkStone(neighbor);
 continue;
 }
 if (neighbor.chain != null) {
 finalChain.join(neighbor.chain);
 }
 }
 finalChain.addStone(newStone);
}
/**
 * Check liberties of Stone
 * 
 * @param stone
 */
public void checkStone(Stone stone) {
 // Every Stone is part of a Chain so we check total liberties
 if (stone.chain.getLiberties() == 0) {
 for (Stone s : stone.chain.stones) {
 s.chain = null;
 stones[s.row][s.col] = null;
 }
 }
}
/**
 * Returns true if given position is occupied by any stone
 * 
 * @param row
 * @param col
 * @return true if given position is occupied
 */
public boolean isOccupied(int row, int col) {
 return stones[row][col] != null;
}
/**
 * Returns State (black/white) of given position or null if it's unoccupied.
 * Needs valid row and column.
 * 
 * @param row
 * @param col
 * @return
 */
public State getState(int row, int col) {
 Stone stone = stones[row][col];
 if (stone == null) {
 return null;
 } else {
 // System.out.println("getState != null");
 return stone.state;
 }
}
}

Chain

package go;
import go.GameBoard.State;
import java.util.ArrayList;
/**
 * A collection of adjacent Stone(s).
 *
 */
public class Chain {
public ArrayList<Stone> stones;
public State state;
public Chain(State state) {
 stones = new ArrayList<>();
}
public int getLiberties() {
 int total = 0;
 for (Stone stone : stones) {
 total += stone.liberties;
 }
 return total;
}
public void addStone(Stone stone) {
 stone.chain = this;
 stones.add(stone);
}
public void join(Chain chain) {
 for (Stone stone : chain.stones) {
 addStone(stone);
 }
}
}

Stone

package go;
import go.GameBoard.State;
/**
 * Basic game element.
 *
 */
public class Stone {
public Chain chain;
public State state;
public int liberties;
// Row and col are need to remove (set to null) this Stone from Grid
public int row;
public int col;
public Stone(int row, int col, State state) {
 chain = null;
 this.state = state;
 liberties = 4;
 this.row = row;
 this.col = col;
}
}

• Mathieu Guindon: I've played Go before, but never quite grasped how "owned territory" gets calculated. Did I miss something or your game can't determine a winner yet? I'm curious about that algorithm =)
• David Mašek: @Mat'sMug It can't determine a winner (yet). I also don't quite get how score is calculated (altrough I can estimate it in most cases) so this is something that I'll add later. I'll try to remember to send you the algorithm :)
• Almo: Japanese scoring says each player gets 1 point for each empty space in their "territory" minus one point for each stone of their captured by the opponent. "Territory" is an area enclosed entriely by stones of the player's color, or against the edge.
• Almo: Every implementation on computer I've seen has the two players mark their stones they consider dead before the computer counts it up. Otherwise it's a hellacious problem to solve.
• CodesInChaos: @Mat'sMug Once both players pass, they need to agree on which stones are alive. Using area scoring, you can simply resume play if they disagree since playing in your own territory doesn't cost you points. When two bots play, they typically avoid that complication and simply play until all dead stones are captured and all they could do is gouge out their own eyes. With territory scoring you need to play it out hypothetically to find out which stones are alive, but use the original board position for the scoring. In practice there is rarely a disagreement between players stronger than 20k or so.

Answer 1

You don't cleanly separate different concerns:

• GameBoard contains both game logic (e.g. who is next to move, preventing playing on an occupied point, etc.) and UI logic.
• Converting between graphical coordinates and in game coordinates should be done using a single function for each direction and not interleaved with the drawing or click logic.
• Finding neighbours should be its own function. It should never return null elements in the returned collection, but rather a collection containing fewer Points if the center Point is at the edge of the board.
• Some of your code uses the GameBoard.SIZE constant. Other code uses the Grid.SIZE instance field. GameBoard.SIZE should either be eliminated or only used a single time, when passing it to the constructor of the board.

Some other issues:

• State is a rather vague name, how about StoneColor?

• Ko doesn't get handled.

  I'd recommend having a collection/set if points-in-ko on the game state. This has two advantages over a single nullable Point: You don't need to handle null as a special case and it generalizes nicely to super-ko, where multiple points can be in ko at the same time.

• Doesn't handle suicide

  Depending on how you implemented ko, explicitly handling single stone suicide might not be necessary, since it results in an unchanged board. Multiple stone suicide is illegal under most rules, but allowed under other rules. If you want to support multiple rules, you should describe them in a Rules object (including scoring, ko and suicide).

An alternative design

This is based on my experience writing a go program in C#. It focuses on clean design, sacrificing some performance. But features that need extreme performance, mainly bots, need specialized data-structures anyways, so I don't see that as a problem.

Go game logic only depends on the coordinates of a point for a single function: determining the neighbours of a point. If you use an immutable GoPoint type, you don't need to pass around (x,y) pairs all the time.

You don't need 2D arrays to represent the board state either, you can use a simple Dictionary<GoPoint, StoneColor>. The board topology can be described using two functions Iterable<GoPoint> allPoints and Iterable<GoPoint> neighbours(GoPoint point).

To avoid creating new instances of Point all the time, you can create all points when initializing the board and add a function GoPoint pointAt(int x, int y) to obtain it.

Chains are simply a collection of points, there is little gain in representing them as their own type. I wouldn't use persistent chains updated each move either. Chains are only necessary to determine which stones will be captured, you can compute them on-the-fly for the neighbours of the point you're playing on. To compute chains, start at a point and recursively add all neighbouring points, eliminating duplicates.

Similarly I'm not fond of having a mutable Stone class. The GoPoint class together with a couple of functions on the class representing to board state should be enough.

• maaartinus: I guess that Map<GoPoint, StoneColor> might be slow for the use by the AI player, but for the current code it's surely a good idea. I like all the immutability (and everything) you propose!
• David Mašek: Great ideas, thanks. Is Dictionary<GoPoint, StoneColor> problem even for simple AI? If yes, any good alternative? I plan some not-completely-stupid AI.
• CodesInChaos: @DavidMašek The dictionary itself isn't the main cost, but recomputing everything related to chains and liberties is a bit expensive. I'd guess that this approach is limited to a million or so moves per second. An AI will need a bunch of incrementally updated data structures, but some of those will be AI specific (e.g. including some approximation of influence), so I wouldn't pollute the rest of the program with them.
• David Mašek: One more thing. "Converting between graphical coordinates...". I don't get this. I don't need to convert anything, do I?
• CodesInChaos: @DavidMašek Game coordinates are two integers between 0 and 18. But when rendering you work with pixels, borders etc. To draw them, you have to compute where each Point will be and when handling a click you need to convert those pixel coordinates into game coordinates. i * TILE_SIZE + BORDER_SIZE, is one such conversion. To avoid writing this logic several times and because this conversion is a separate concern, this should be extracted into helper functions. E.g. if you need to mirror the y-coordinate, because graphics has the origin in the top-left but most go formats in the bottom-left.

Answer 2

Not a full review, just a couple of initial thoughts:

Is "Main" acceptable name for a class? Or should it be "Game"/"App" or something completely different?

I would say "Main" is acceptable if it doesn't to anything except start the app; it doesn't contain any app logic itself. I think for your game this is pretty much true, but I would probably extract the init stuff into a MainGUI or ContainerGUI class (because it will most likely grow soon, eg by adding a menu, customizable view, etc).

What about my comments?

Your JavaDoc comments seem mostly good to me, but your inline comments are often not necessary.

• Check wherever it's valid is a bit unclear. What is it? Where is it valid? I think bounds check would be clearer, but then it becomes obvious that the comment isn't actually needed.
• @param black for State state is wrong (I'm assuming you had it as a boolean first?)
• Switch current player It's often not a good idea to write comments that just repeat the code. If you think your code is unclear/you want more structure, it's often better to create a method for it.
• what's a liberty? A comment for eg getLiberties about this would be nice.
• join(Chain chain) could use a short comment
• Row and col are need to remove (set to null) this Stone from Grid this could be clearer.

I don't think it's expandable (enough).

I think it looks pretty good. There are a couple of things I would do differently (eg separate view and controller, remove the small parts of game logic - switching players - that are in the view/controller, and some of the stuff in misc), but all in all it has a clear structure.

Misc

• Chain(State state): state is actually never used.
• don't shorten variable names, it makes code harder to read. N_OF_TILES -> NUMBER_OF_TILES/TILE_COUNT
• why are all fields of Stone public instead of having getters/setter?
• State is a very generic term. Player or PlayerColor/StoneColor may make more sense.
• I would extract the MouseAdapter to it's own class, in case it gets more complicated later on.
• you could avoid the state != null check by creating a None value for State, I think this would result in nicer code.

• Vogel612: A "liberty" is part of the fundamental game concept of go. A group of stones is considered alive only if it has 2 liberties, which is interesting for score evaluation.. but that's quite the complicated matter
• David Mašek: Thank you, I'll try to upgrade it. There were some leftovers I didn't notice (eg. Chain(State state)). About public fields - it simplified things a little bit altrough I'll probably change that. How would you separate view and controller? Do you mean one class for input and one for view? If yes, how would they "comunicate"?
• tim: @DavidMašek True, public fields simplify writing a bit (although IDEs can auto generate getter/setters), but it makes code a bit harder to maintain (you can't change the inner workings of the class without changing something else as well). And yes, a class for input, and one for output, and the communication happens via the controller (which also manages the communication between the view and the model (the Grid class)); it might be over-engineering in this case, but I always find that it does lead to cleaner structure.
• maaartinus: @DavidMašek Sometimes the MVC (at al.) gets pretty confusing, however, separating the model (game data) from the view (GUI) is always clear and should be always done. If in doubt, then ask yourself how much logic you could reuse when writing a non-swing application (and this tells you for sure that current_player belongs elsewhere).

Answer 3

It can't determine a winner (yet).

I'd suggest to use Area scoring, where you can let the players continue until it gets simple enough for your algorithm.

Is Main an acceptable name for a class? Or should it be Game/App or something completely different?

I always use a prefix for my "Mains" (like GoMain) in order to be able to tell them apart even where a simple name gets used (e.g., Eclipse run configurations).

package go;

That's wrong, unless there's a TLD "go" and you own it.

Main

public static final int BORDER_SIZE = 25;

I'd move it into the class where other view constants get defined.

GameBoard

private static final long serialVersionUID = -494530433694385328L;

You don't need it, unless you

• really want to
  • serialize GameBoard instances
  • and save them in files
  • and use them later with a different class version
• and you're determined to handle compatibility

With other words, you really do not need it (and the Eclipse warning is a non-sense and should be switched off).

public static final int SIZE = 9;

As the SIZE holds for Grid as well, I'd move it there (since the view is just an auxiliary thing).

public static final int N_OF_TILES = SIZE - 1;

The naming has been already commented on, but I'd drop this altogether as it doesn't save much.

But actually, I'd drop SIZE as a constant anyway. You'll surely want to play on bigger boards as well.

public enum State {
 BLACK, WHITE
}

Again, this IMHO belongs to Grid (as the more fundamental class).

Having two possibilities only (rather than adding EMPTY) allows you to use

private State current_player;

(which violates naming convention a lot!), but using null as the third value for stones is ugly. I might go for

private boolean isBlacksTurn;

which is ugly, too.

---

private Grid grid;

This should be final.

private Point lastMove;

Point is an ugly mutable class which I wouldn't use anywhere except where required.

public GameBoard() {
 grid = new Grid(SIZE);

I'd use (manual) DI here, simply by passing a grid to the constructor. Again, the view is not the important part. Creating the grid in Main allows you to pass it anywhere (without accessing the view).

---

The MouseListener is rather long, mainly because it does things it shouldn't do. It should compute the coordinates and call something like gameState.playAt(row, col).

protected void paintComponent(Graphics g) ...

This is a pretty long method composed of 4 main parts separated by comments. I'd probably extract the parts and drop the comments.

Grid

I'd rename it to GameState and add currentPlayer and lastMove (or a whole history).

private final int SIZE;

This is no constant and should be called size.

private Stone[][] stones;

I'm not sure if storing so much information is needed/useful. Simply storing State should do. I usually try to create a minimal model and store redundant information in other variables as needed.

You're missing a check if the move is legal, i.e., 1. your new group has at least one liberty after possible captures have been evaluated, 2. it's not a ko.

public void checkStone(Stone stone) ...

I don't like the name. What about removeGroupIfDead?

Chain

 public ArrayList<Stone> stones;
 public State state;

Avoid public variables. First try moving everything what needs to access the class members into the class itself, otherwise provide some accessors (but don't add a getter for collections as it allows the caller to modify them later).

public int getLiberties() {
 int total = 0;
 for (Stone stone : stones) {
 total += stone.liberties;
 }
 return total;
}

You're counting some liberties multiple times, which is ugly, but alright for what you're using it, namely testing if there's any. So a boolean result should do.

It looks like using Chain doesn't buy you much as you have to iterate anyway. Being able to store the liberties could make the evaluation fast (needed for a AI player), but this may be hard to do. Iterating over all neighbors every time could possibly be done without any Chain/Stone.

Stone

Again, public variables. I'd try to get rid of the whole class, but this may be hard.

• David Mašek: Thanks. Sorry for current_player, I've been doing a lot of Python lately. What should I use instead of Point? (I could use 2 ints but that seems stupid. I've never heard of DI so again, thanks. Where should gameState.playAt(row, col) be located (what class)? About private Stone[][] stones; I think it's needed because it simplifies counting of liberties, am I wrong? Rules aren't complete but this is intensional (for now). How would I iterate over neighbors without Chain/Stone? How could I get rid of Stone?
• maaartinus: @DavidMašek Make your own immutable GoPoint as CodesInChaos suggested (read his answer, it's very good). Convert Grid to GameState and put all GUI unrelated information there, call gameState.playAt from the GUI. +++ I'm sure, both Stone and Chain can be eliminated, though it makes your algorithm a bit more complicated (again, see CodesInChaos's answer). Use a recursive countLiberties(Set<GoPoint> group, GoPoint newPoint) which creates the group on the fly by traversing the neighbors.
• David Mašek: Next time I'll read all the answers before I comment... I read it but after asking, sorry.
• maaartinus: @DavidMašek No problem, I tried to expand on his answer. +++ You may want to add Set<GoPoint> liberties as an argument to countLiberties, or maybe implement removeIfDead instead (and then you can exit whenever the first liberty is found).

Answer 4

• The chain joining

  if (neighbor.chain != null) {
   finalChain.join(neighbor.chain);
  }
  

  looks simplistic. Two or more neighbours may belong to the same chain. Such chain would be added to the finalChain more than once. I cannot say if that would cause a runtime problem, but surely raises some eyebrows.

  Along the same line, the same liberty could be accounted for more than once. It is OK as long as you only interested in life vs death, but restricts the overall scope of the program.

• I don't see how the suicidal moves are getting rejected.

• Ko handling and detection is obviously missing.

• David Mašek: I understand the problem with Chain joining but I'm not sure where the problem is with liberties. Suicidal moves don't get rejected (yet), the same goes for Ko.