Playing Games with Mathematica

Authors:
Robert Cowen, Queens College, CUNY
Robert Dickau, InstallShield Software Corp.

Modified for Math 213 by Christopher Hanusa, Queens College, CUNY
This file has replaced original occurrences of ListDensityPlot with ArrayPlot, and much shortened by removing visualizations, and removing functions that are defined in GamesEngine.
Make sure to run the GamesEngine before evaluating this notebook.
For the original file and the GamesEngine, visit http://qc.edu/~cowen/.

Cram

As with any other impartial two-player game that we will run using the games engine, we need to define all valid moves.  We break the moves into placing horizontal dominoes and placing vertical dominoes.  Placing a horizontal domino takes two open squares adjacent horizontally (1,1) and places a domino there by replacing the (1,1) by (0,0):

PossibleMovesHorizontal[boardstate_]:=
	ReplaceList[boardstate,{L1___,{bef___,1,1,aft___},L2___}->{L1,{bef,0,0,aft},L2}]

A vertical domino is the same thing as finding a horizontal domino in the transpose of the box.

PossibleMovesVertical[boardstate_]:=Map[Transpose,PossibleMovesHorizontal[Transpose[boardstate]]]

Take the union of both sets of valid moves to make the set of all valid moves.

PossibleMoves[boardstate_]:=
	Join[PossibleMovesHorizontal[boardstate],PossibleMovesVertical[boardstate]]

Next we construct an initial position for our game, starting with a 4×4 version of Cram. We start with a list of sixteen 1s (where a 1 indicates an empty square on the checkerboard), and then replace three of the 1s with –1s (again, numbers other than 1 indicate missing or played squares), the replacements being chosen randomly; finally we partition the list of length 16 to make a 4×4 matrix.

r1:=Random[Integer,{1,5}];
r2:=Random[Integer,{6,10}];
r3:=Random[Integer,{11,16}];
pos = Partition[ReplacePart[Table[1,{16}],-1,{{r1},{r2},{r3}}],4];

Here is the initial state of the checkerboard; the black squares are open and the white squares are missing.

ArrayPlot[pos,PlotRange->{-1,1}]

Here is the Grundy function applied to the initial state of the board:

Grundy[pos]

If the initial position has a nonzero Grundy number, the Sprague-Grundy algorithm indicates we should place the domino in a location that puts the board in a zero position. Here are the Grundy values for all possible moves.

Map[Grundy,PossibleMoves[pos]]

Below is a visualization of all possible first moves.  The grey squares are the domino that was placed.

Map[ArrayPlot[#,PlotRange->{-1,1}]&,PossibleMoves[pos]]

Assuming the initial state of the board is nonzero, here we see all first moves that lead to a win for the first player; that is, the moves that lead to a zero position.

Map[ArrayPlot[#,PlotRange->{-1,1}]&,Select[PossibleMoves[pos],Grundy[#]==0&]]

Here is one complete sample game.  You can see that each step along the game is a 4x4 matrix with -1's where squares are missing (white), 1's where squares are open (black), and 0's where squares are in use (grey).

thegame=RandomPlayTheGame[pos]

Here we display the progress of the game:

Map[ArrayPlot[#,PlotRange->{-1,1}]&,thegame]

If you visit the original file, there are better visualizations of the dominoes (blue dominoes for player 1 and red dominoes for player 2) and you can investigate those if you are interested.

A visual tour of what else is possible with extensions of Cram:

Furthermore, because the Grundy algorithm applies to any impartial two-player game, we can play variations of Cram with very little change to the original code. For example, here is a sample game played with 3×1 dominoes.

Here is Cram played with L-shaped pieces.

And here is Cram played in three dimensions.

Other variations are playing on a triangular board, playing with different shapes of pieces, and playing on a cylinder or torus.

We encourage others to use Mathematica to investigate other games as well as Cram, and we would like to hear about any progress. After all, playing games is not only instructive, it’s fun!

References

[1] E. Berlekamp, J. Conway, R. Guy, Winning Ways for Your Mathematical Plays, Academic Press, London, 1985.

[2] M. Gardner, “Mathematical Games”, Scientific American, February 1974, pp. 106–108.

[3] R. McEliece, R. Ash, C. Ash, Introduction to Discrete Mathematics, Random House, New York, 1989.

About the Authors

Robert Cowen teaches math at Queens College of The City University of New York where he gives a course in mathematical algorithms that meets in the Math Department’s Mathematica lab. It was for this course that he started programming games in Mathematica. When not playing games, he does research in logic, set theory, and graph theory.

cowen@qcvaxa.acc.qc.edu

Robert Dickau is a former member of technical staff of Wolfram Research, and is currently senior technical trainer at InstallShield Software Corporation in Schaumburg, Illinois. He holds degrees in mathematics and actuarial science from California Polytechnic University, Pomona, and University of Illinois at Champaign-Urbana. His mathematical interests include fractals and combinatorial enumeration.

pops@prairienet.org