Fission

Combinatorial games played on a two-dimensional grid are extremely common.  Examples of grid-based games that have been studied extensively include Amazons, Clobber, Domineering, Konane, and Toads and Frogs.  For this reason, cgsuite provides special machinery for handling such games, so that they can be implemented with a minimum of effort.

In this section we will implement one such game, Fission.  Fission is a simple game invented by Michael Albert, played on a grid with black and white stones.  Left, on his turn, removes any black stone from the board and replaces it with two black stones.  Left may choose one of two placements for the new stones: either one stone to the left of the removed stone and one to the right; or one stone above the removed stone and one below.  Right plays likewise, but using the white stones.  The first player unable to move loses.

Here's a typical starting position:

And Left's two possible opening moves:

     or    

AbstractGridGame

Recall that for partizan nim, we subclassed AbstractShortGame.  While this is always an option, for grid-based games it is usually more convenient to use a specialized class, cgsuite.plugin.AbstractGridGame.  This class has a predefined data structure - the protected field grid - with many of the standard methods, such as equals and hashCode, already implemented.

In fact, AbstractGridGame takes care of everything except the constructors; the standard methods getLeftOptions, getRightOptions, and getInverse; and an optional toString method.  It also defines three standard integer constants, EMPTY = 0, BLACK_STONE = 1, and WHITE_STONE = 2, which we can use to represent values the values at grid locations.

Let's start with the constructors.  First, all subclasses of AbstractGridGame must have a Grid constructor:

import java.util.Collection;
import java.util.List;
import cgsuite.util.Grid;

public class FissionPosition extends cgsuite.plugin.AbstractGridGame
{
    public FissionPosition(Grid grid)
    {
        this.grid = (Grid) grid.clone(Grid.BITS_PER_ENTRY_2);
    }

    // ...
}

Note that we clone the grid to guarantee immutability.  The cgsuite.util.Grid class is used to store a two-dimensional integer array of arbitrary size.  The array is stored in a memory-efficient manner, packing several entries into each byte.  The argument to Grid.clone specifies how many bits the copy should use per grid entry.  Since each entry in our grid assumes one of just three possible values (EMPTY, BLACK_STONE, WHITE_STONE), we choose two bits per entry.

The Grid class is quite powerful, and contains methods for building symmetries, decomposing grids into disconnected components, and so forth.  We'll see some of these operations in the course of this tutorial.

Another constructor is useful; this one takes a String[] argument, and is used to parse user input:

    public FissionPosition(String[] rows) throws cgsuite.plguin.MethodInvocationException
    {
        grid = cgsuite.plugin.PluginUtilities.stringsToGrid(rows, ".lr", Grid.BITS_PER_ENTRY_2);
    }

Notice that we don't really have to do anything: We just pass all the work along to the stringsToGrid method, which assembles a grid based on the array of strings.  Each string in the array corresponds to a row, and the ".lr" parameter specifies the mapping from characters to grid values: '.' corresponds to value 0 in the grid, l to value 1, and r to value 2.  The mapping is not case-sensitive.  If the user enters a string containing characters other than those specified, then stringsToGrid will throw a MethodInvocationException containing a useful error message.  Notice also that, as before, we specify two bits per entry.

Finally, we privatize the no-arg constructor and add a toString method, which again sends most of the work to cgsuite:

    private FissionPosition()
    {
    }

    public String toString()
    {
        return "Fission(" + grid.toString(".lr") + ")";
    }

The Options and Inverses

Our code for getLeftOptions and getRightOptions is reasonably straightforward, but take note of how Grid.getAt and Grid.putAt are used to access and modify grids:

    public Collection getLeftOptions()
    {
        return getOptions(BLACK_STONE);
    }
    
    public Collection getRightOptions()
    {
        return getOptions(WHITE_STONE);
    }
    
    private Collection getOptions(int stoneType)
    {
        List options = new java.util.ArrayList();
        for (int row = 0; row < grid.getNumRows(); row++)
        {
            for (int col = 0; col < grid.getNumColumns(); col++)
            {
                if (grid.getAt(row, col) == stoneType)
                {
                    addOption(options, row, col, row-1, col, row+1, col);
                    addOption(options, row, col, row, col-1, row, col+1);
                }
            }
        }
        return options;
    }
    
    private void addOption(List options, int oldRow, int oldCol, int newRow1, int newCol1, int newRow2, int newCol2)
    {
        if (newRow1 >= 0 && newCol1 >= 0 && newRow1 < grid.getNumRows() && newCol1 < grid.getNumColumns() &&
            newRow2 >= 0 && newCol2 >= 0 && newRow2 < grid.getNumRows() && newCol2 < grid.getNumColumns() &&
            grid.getAt(newRow1, newCol1) == EMPTY && grid.getAt(newRow2, newCol2) == EMPTY)
        {
            FissionPosition option = new FissionPosition();
            option.grid = (Grid) grid.clone();
            int type = grid.getAt(oldRow, oldCol);
            option.grid.putAt(oldRow, oldCol, EMPTY);
            option.grid.putAt(newRow1, newCol1, type);
            option.grid.putAt(newRow2, newCol2, type);
            options.add(option);
        }
    }

Finally, for getInverse, we call grid.mapEntries, which reassigns grid values according to a specified mapping.  In this case, we can use the mapping COLOR_INVERSION_MAP, which is predefined by AbstractGridGame and simply switches the black and white stones:

    public cgsuite.Game getInverse()
    {
        FissionPosition inverse = new FissionPosition();
        inverse.grid = grid.mapEntries(COLOR_INVERSION_MAP);
        return inverse;
    }

Type and Method Declarations

Our type and method declarations look pretty similar to those for Partizan Nim:

        context.registerType(FissionPosition.class, "FissionPosition");
        context.declareMethod(
            "Fission",
            new Class[] { String[].class },
            new MethodInvoker() {
                public Object invoke(String name, Object[] args, java.util.Map optionalArgumentMap)
                throws MethodInvocationException {
                    return new FissionPosition((String[]) args[0]);
            }},
            true
            );

There is one significant difference: The optional fourth parameter with value true.  This tells CGSuite that the user can enter several String parameters in place of the single String[] parameter.  In other words, the user can type (for example):

Fission(".l..","..r.",".l..")

instead of:

Fission([".l..","..r.",".l.."])

Adding an I/O Handler

We now have a fully functional Fission plug-in.  However, entering a Fission position into the Worksheet produces some rather ugly text output - essentially identical to what the user just typed in.  It would be nice for the Worksheet to display the actual position graphically.  Further, although we can examine Fission positions in the Explorer (via the Worksheet command Explore(G)), we can't edit them, which makes the whole task of analyzing Fission somewhat cumbersome.

Fortunately, for grid-based games such as Fission, it's extremely easy to add graphical support.  In fact all we need is to add the following to the plug-in's initialize method:

        if (context.isGUI())
        {
            context.registerIOHandler(FissionPosition.class, new GridIOHandler(5, 5));
        }

This tells CGSuite that when displaying or editing objects of type FissionPosition, it should use a GridIOHandler with a default grid size of 5x5.  The call to isGUI() isn't strictly necessary, but it's generally advisable if you want your plug-in to be usable in CGSuite's text mode.  (Loading graphics components in text mode not only consumes extra system resources; on some Java installations it might throw exceptions.)

That's it!  Now if you enter a Fission position in the Worksheet, you'll receive a nice graphical representation.  Further, you can create a new editor, with the default 5x5 grid, by selecting File/New/Explorer and choosing "FissionPosition" from the dialog that pops up.

The simplicity of the GridIOHandler constructor masks a flexible graphics/editor system that can handle just about any game.  There are several levels of flexibility:

For details on the options available, see the API documentation for the cgsuite.plugin class.

A final word of caution: AbstractGridGame is suitable only for games where all information relevant to the position is stored in the grid.  If additional parameters might affect the value of the position, then it's usually better to fall back on AbstractShortGame.  Such games can still implement cgsuite.plugin.GridEditable directly to take advantage of some of the Explorer features; see the API for more details.

Continue on to Clobber