Clobber

Clobber is another grid-based game played with black and white stones.  The rules are quite simple: The only move is to capture an orthogonally adjacent stone of the opposite color.  In addition to being quite playable, Clobber is theoretically quite interesting, giving rise to a dizzying variety of infinitesimals.  It's bundled with CGSuite as part of the Basics plug-in, and the Game class looks pretty similar to Fission's.  Nevertheless, it's introduced in this tutorial because it illustrates two useful techniques not relevant to Fission: directional iteration and decomposition.

In case you don't have a copy of the CGSuite source handy, you can grab a copy of the Clobber source here:

• ClobberPosition.java

Directional Iteration

The rules for many games, including Clobber, involve the players acting in any orthogonal (or in some cases diagonal) direction.  Naively, we'd need to consider all four (or eight) possible moves individually.  CGSuite has a convenient shortcut for simplifying the task of iterating over the directions.  Notice the following snippet from ClobberPosition.java's getOptions method:

                    for (int dir = 0; dir < 4; dir++)
                    {
                        if (grid.isValidShift(row, col, dir, 1) &&
                            grid.getAt(newRow = row + Grid.getRowShift(dir, 1),
                                       newCol = col + Grid.getColumnShift(dir, 1)) == them)
                        {
                            ClobberPosition newPosition = new ClobberPosition(grid);
                            newPosition.grid.putAt(newRow, newCol, us);
                            newPosition.grid.putAt(row, col, EMPTY);
                            options.add(newPosition);
                        }
                    }

Here we let dir range from 0 to 3.  The important methods are:

public boolean Grid.isValidShift(int row, int col, int dir, int distance)
Returns true if the location reached by moving distance squares away from (row,col) in the direction dir is still in the grid.

public static int Grid.getRowShift(int dir, int distance)
Gets the number of rows away the target location would be if we moved distance squares in the direction dir.

public static int Grid.getColumnShift(int dir, int distance)
Gets the number of columns away the target location would be if we moved distance squares in the direction dir.

Values of dir between 0 and 3 represent the orthogonal directions; between 5 and 8, the diagonal directions.  So if we wanted to code up a clobber variant ("Diagonal Clobber") in which the pieces could capture either orthogonally or diagonally, the only change we'd need to make here is to replace

for (int dir = 0; dir < 4; dir++)

with

for (int dir = 0; dir < 8; dir++)

Likewise, if we wanted to constrain pieces to move only diagonally, we'd use

for (int dir = 4; dir < 8; dir++)

Decomposition

Many games, including Clobber, decompose in the endgame into several non-interacting components.  Usually these are given by disconnected regions of the grid: areas that are separated by impassable barriers.  In Clobber, the only moves are captures, so these impassable barriers are just regions of empty space.  Unless two stones are connected by some continuous path of stones, they can never interact.

The Grid class provides methods for detecting decomposable grids and breaking them into components.  For games that decompose, it's usually best to override the canonicalize method and exploit the decomposition there.  Witness Clobber:

    public CanonicalGame canonicalize()
    {
        Grid[] decomposition = grid.decompose(EMPTY, Grid.DECOMPOSITION_TYPE_ORTHOGONAL);
        if (decomposition.length == 1 && decomposition[0] == grid)
        {
            return super.canonicalize();
        }
        CanonicalGame sum = CanonicalGame.ZERO;
        for (int i = 0; i < decomposition.length; i++)
        {
            ClobberPosition newPosition = new ClobberPosition();
            newPosition.grid = decomposition[i];
            sum = sum.add(newPosition.baseCanonicalize());
        }
        return sum;
    }
    
    private CanonicalGame baseCanonicalize()
    {
        return super.canonicalize();
    }

Grid.decompose takes two arguments: a boundary type, in this case empty space, and a decomposition type: orthogonal or diagonal.  It will return an array of Grids such that:

• Each component contains at least one non-boundary entry (in this case, at least one stone);
• Within each component, all non-boundary entries are orthogonally (or diagonally) connected;
• Within each component, every row and every column contains at least one non-boundary entry.

In other words, each grid in the array has exactly one connected component, and no excess "white space".  If the original grid has this property, then decompose is guaranteed to return a one-element array whose single element is equal to the original grid (reference equality).

Notice how, in the Clobber position, the grid is first decomposed, each component is evaluated (bypassing an extraneous call to decompose), and the values are then added together using CanonicalGame.add.

If we wanted to implement the "Diagonal Clobber" variant, all we'd need to do is change

Grid[] decomposition = grid.decompose(EMPTY, Grid.DECOMPOSITION_TYPE_ORTHOGONAL);

to

Grid[] decomposition = grid.decompose(EMPTY, Grid.DECOMPOSITION_TYPE_DIAGONAL);

Continue on to Further Topics