Partizan Nim is a partizan variant of the classic game nim. Like nim, the game is played with several heaps of varying sizes. At the start of the game, each player is assigned a finite set of integers, called his subtraction set. On his turn, a player must choose a heap and remove some number of coins from that heap; the number of coins removed must be in his subtraction set. The first player unable to move loses.
Obviously the heaps are non-interacting, so the game decomposes; and in our implementation we need only model a single heap.
Game InterfaceThe first task in designing a plug-in is to write a class that implements the cgsuite.Game
interface. All games recognized by cgsuite must implement this interface -
it contains methods that expose crucial information such as the left and right
options of a position. Our implementation of Game, PartizanNimPosition,
represents a single heap in partizan nim.
Since partizan nim is a short game - meaning no position can occur
twice in a single line of play - we can subclass AbstractShortGame
instead of implementing Game directly. This generally
involves substantially less work, since Game contains several
methods that are useful only in rare circumstances.
import java.util.Collection;
public class PartizanNimPosition extends cgsuite.AbstractShortGame
{
// ...
}AbstractShortGame has just three abstract methods we'll need to
implement; their names are self-explanatory:
public abstract Collection getLeftOptions();
public abstract Collection getRightOptions();
public abstract cgsuite.Game getInverse();First, though, let's set up the data structure. To define a partizan nim position, we need to know which moves are available to each player, as well as the size of the heap. We can specify the players' options as integer arrays, and the heap size as a single int:
private int[] leftSubtractionSet, rightSubtractionSet;
private int heapSize;Now let's implement the getOptions methods. We can avoid some code
duplication by writing a single getOptions method which takes a
subtraction set as a parameter.
public Collection getLeftOptions()
{
return getOptions(leftSubtractionSet);
}
public Collection getRightOptions()
{
return getOptions(rightSubtractionSet);
}
public Collection getOptions(int[] subtractionSet)
{
java.util.List options = new java.util.ArrayList();
for (int i = 0; i < subtractionSet.length; i++)
{
if (subtractionSet[i] <= heapSize)
{
PartizanNimPosition p = new PartizanNimPosition();
p.leftSubtractionSet = leftSubtractionSet;
p.rightSubtractionSet = rightSubtractionSet;
p.heapSize = heapSize - subtractionSet[i];
options.add(p);
}
}
return options;
}It's quite easy to specify the inverse for partizan nim: just switch the subtraction sets!
public cgsuite.Game getInverse()
{
PartizanNimPosition inverse = new PartizanNimPosition();
inverse.leftSubtractionSet = rightSubtractionSet;
inverse.rightSubtractionSet = leftSubtractionSet;
inverse.heapSize = heapSize;
return inverse;
}Finally, let's add a public constructor. Instances of Game are
required to be immutable; to be safe, we enforce this by cloning the array
arguments. We also sort the subtraction sets - this will be useful later - and do some simple argument validation.
public PartizanNimPosition(int[] leftSubtractionSet, int[] rightSubtractionSet, int heapSize)
{
this.leftSubtractionSet = (int[]) leftSubtractionSet.clone();
this.rightSubtractionSet = (int[]) rightSubtractionSet.clone();
this.heapSize = heapSize;
java.util.Arrays.sort(this.leftSubtractionSet);
java.util.Arrays.sort(this.rightSubtractionSet);
if (this.leftSubtractionSet.length == 0 || this.rightSubtractionSet.length == 0 ||
this.leftSubtractionSet[0] <= 0 || this.rightSubtractionSet[0] <= 0)
{
throw new IllegalArgumentException("Invalid subtraction sets.");
}
}It's also useful to privatize the default constructor. Note that our getOptions and getInverse methods use the default constructor, and not the constructor with arguments - this is to avoid excessive cloning and validation, which would negatively impact performance.
private PartizanNimPosition()
{
}equals and hashCodeWe now have a functional implementation, but it's quite inefficient.
Partizan Nim, like most games, contains frequent transpositions - positions that
can be reached by two or more distinct lines of play. As it stands, we
haven't told cgsuite how to tell when two instances of PartizanNimPosition
represent the same position, so it will assume that every instance is
distinct. As a result, transpositions will be evaluated multiple times,
leading in some cases to exponential slowdown.
To remedy this, we override Java's equals method, which tests
whether two objects are equivalent.
public boolean equals(Object obj)
{
return obj instanceof PartizanNimPosition &&
((PartizanNimPosition) obj).heapSize == heapSize &&
java.util.Arrays.equals(leftSubtractionSet, ((PartizanNimPosition) obj).leftSubtractionSet) &&
java.util.Arrays.equals(rightSubtractionSet, ((PartizanNimPosition) obj).rightSubtractionSet);
}Using java.util.Arrays.equals to compare the arrays works fine,
since we sorted them during construction.
Finally, if we override equals, we must override hashCode.
A hash code is an integer representation of an object. If two objects are
equivalent in the sense of equals, then they must return the
same hash code. On the other hand, distinct objects are permitted to have
the same hash code - in fact, the number of game positions one might consider
typically exceeds the available number of integer hash codes. Generally
speaking, though, better resolution in distinguishing positions via hash codes
yields improved performance.
We'll use a simple hash strategy for this example: the hash code of a position is just its heap size. This fails to distinguish between equal-sized heaps with different subtraction sets, so performance might suffer during a large-scale analysis involving many different subtraction sets. For the purposes of this example, though, the naive hash code suffices.
public int hashCode()
{
return heapSize;
}Our implementation contains one additional method, toString,
which you can view by opening the PartizanNim.java file. This
is not essential to the implementation, but it's generally a nice thing to have.
At this stage, you might wish to test the game class before proceeding.
A simple approach is to write a main function that runs a test case. To
obtain the canonical form of a partizan nim position, we just call its canonicalize
method. Notice that we never had to implement this method directly - we
simply specified the left and right options of each position. AbstractShortGame
takes care of the rest!
public static void main(String[] args)
{
PartizanNimPosition p = new PartizanNimPosition
(new int[] {1,3,5}, new int[] {2,4}, 9);
cgsuite.CanonicalGame g = p.canonicalize();
System.out.println("Canonical form of a size 9 heap in [1,3,5] vs. [2,4] partizan nim:");
System.out.println(g);
}You can run the test by typing (for example):
java -cp "cgsuite.jar;." PartizanNimPosition
Continue on to The Plugin Interface