Playing Games with Mathematica

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

Impartial Games

Much can be learned by playing games. The beginnings of probability and statistics derive from questions asked by gamblers from their experiences at the gaming tables. Here we consider games where reasoning, not chance, is paramount. In particular, we consider the class of so-called impartial games, defined below. The basic mathematical theory of such games is easily explained and there is an algorithm, known as the Sprague-Grundy algorithm, that enables a player with sufficient computational resources to win, when confronted with a winnable position. Many interesting questions can be asked and answered by students, at all levels, about particular impartial games. We will show how Mathematica can be used to play various games and to investigate which player will win (assuming proper play). In this way, we can make and test conjectures, and can discover and prove new theorems. All this while playing games!

Mathematica is an ideal environment in which to implement the Sprague-Grundy algorithm for playing two-player impartial games. This is largely because the algorithm is recursively defined, and Mathematica allows the user to program recursions on many types of objects. In this paper, we illustrate a particular game called “Cram”, which is played on an m×n checkerboard, optionally with some squares removed. The two players alternate placing dominoes on adjacent pairs of uncovered squares, and the last player able to place a domino wins. (The game has been called various names, including “Plugg” and “Dots and Pairs”; and discussions of the game can be found in [1] and [2].)

As described, Cram is an example of an impartial two-player game. In such a game, there is a finite set of positions, each of which has associated with it a finite set of possible moves—positions that can be obtained from the given position by a single legal move. If the set of possible moves from a position is empty, the position is called an end position. The game is “impartial” because the set of possible moves for a position is the same for each player.

The Sprague-Grundy algorithm is based on the following recursive numbering scheme: positions are assigned the smallest nonnegative integer not already assigned to one of its possible moves. (The name Mex, or Minimal Excludant, is often used for the smallest nonnegative integer not a member of a set of nonnegative integers.)  It should be noted that, under this definition, end positions are numbered 0, since the Mex of the empty set is 0. The function that assigns these numbers to positions is called the Grundy function.

There are two important properties of this numbering scheme:

1. Any nonzero position must have a zero position as one of its possible moves.

2. A zero position cannot have a zero position as a possible move.

Both properties are easy to prove. In the case of property 1, if a position does not have a zero position as a possible move, the Mex of its possible moves is 0, that is, the number of the position would be zero. For property 2, if a position does have a zero position as a possible move, the Mex of its possible moves would be nonzero. 

The winning strategy is to move, whenever possible, from a nonzero position to a zero position. If a player can achieve a nonzero position this strategy will win, since one can always move from a nonzero position to a zero position, and the opponent must then move to a nonzero position. Since this process cannot continue forever, it must terminate in an end position, and since end positions are numbered zero, the player using this strategy will have won.

Programming the Sprague-Grundy Algorithm

The Mex function, which accepts a list of nonnegative integers and returns the smallest nonnegative integer not in the list, can be rendered as follows.

Mex[L_List] := Min[Complement[Range[0, Length[L]], L]]

Assuming for the moment we have a PossibleMoves function—that is, a function that returns for a given position, all positions attainable with a single legal move—we can recursively compute Grundy numbers for possible board states in the following way.

Grundy[boardstate_] := 
      Grundy[boardstate] = Mex[Map[Grundy, PossibleMoves[boardstate]]]

(We cache intermediate values of the Grundy function using the form Grundy[boardstate_] := Grundy[boardstate] = ⋯, which saves time in future computations, but which greatly increases the memory used while playing a game. If memory becomes tight, it may be necessary to execute the command Clear[Grundy] from time to time.)

This recursive definition instructs Mathematica to construct a tree of positions with boardstate as the root and with each position on the tree branching to all its possible moves, until, finally, all positions at the end of branches have no possibles moves (i.e., are end positions). The function then numbers the positions on the tree, using the Mex function, starting from the end positions, which are numbered 0, and working backwards to the root.

We can now define a function PossibleMoves, which, if not given an end position, moves to a zero-numbered position (the optimal move); and otherwise selects a nonzero move. This definition will depend, of course, on how we choose to “represent” the positions. For Cram it is natural to represent the positions as matrices with entries: 0s, 1s and -1s; “1” represents an uncovered square, “0” a covered square, and “-1” a square that has been (optionally) removed at the outset. The PossibleMoves function, then, searches for adjacent pairs of 1s and replaces them by 0s. It is convenient to split the search into a horizontal and a vertical component.

The function that tests for possible horizontal moves, called PossibleMovesHorizontal, searches for horizontal adjacent pairs of empty squares in the current board state, returning a list of all possible board states after a single legal play; PossibleMovesVertical finds all possible vertical moves by finding the horizontal moves for the transpose of the current board state; and PossibleMoves simply joins the two lists.

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

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

\(PossibleMoves[boardstate_] := 
	
      Join[PossibleMovesHorizontal[boardstate], 
        PossibleMovesVertical[boardstate]]\)

There are several ways we can select a particular move from a list of all possible moves. The simplest is to take the first possible move, using the following function.

\(ChooseFirstMove[boardstate_] := 
		
      If[Grundy[boardstate] == 0, 
		First[PossibleMoves[boardstate]], 

        		First[Select[PossibleMoves[boardstate], Grundy[#] == 0&, 1]]]\)

To make repeated playings of a game more interesting, we can select one move at random from the complete list of possible moves, using our functions ChooseRandomMove and ChooseMove.

ChooseRandomMove[choices_] := 
      Part[#, Random[Integer, {1, Length[#]}]]&[choices]

\(ChooseMove[boardstate_] := 
		
      ChooseRandomMove[
        If[Grundy[boardstate] == 0, PossibleMoves[boardstate], 
          Select[PossibleMoves[boardstate], Grundy[#] == 0&]]]\)

Next we construct the initial position in 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 partitioning the list 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]; \)

To avoid retyping the same graphics options for each plot, we use SetOptions.

SetOptions[ListDensityPlot, Frame -> None, 
      AspectRatio -> Automatic];

Here is the initial state of the checkerboard.

ListDensityPlot[pos];

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]]

Here we see all possible first moves.

\(\(ShowOpts[boardstate_] := 
\ \ 
      Show[GraphicsArray[
\ \ \ \ \ \ 
          \(Partition[#, Floor[Length[#]/2]]&\)@
\ \ \ \ \ \ \ \ 
            Append[Map[
                ListDensityPlot[#, DisplayFunction -> Identity]&, 

                \ \ \ \ \ \ \ \ \ \ \ \ PossibleMoves[boardstate]], 
              Graphics[{}]]]]; \)\)

ShowOpts[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.

ShowGoodOpts[boardstate_] := 
      Show[GraphicsArray[
          Map[ListDensityPlot[#, DisplayFunction -> Identity]&, 
            Select[PossibleMoves[boardstate], Grundy[#] == 0&]]]];

ShowGoodOpts[pos];

An entire game is encapsulated in a single list by accumulating the successive states of the playing board, using FixedPointList.

\(PlayTheGame[initialstate_] := 
	
      FixedPointList[ChooseMove, initialstate, 
        SameTest -> \((PossibleMoves[#2] == {}&)\)]\)

Here is one complete sample game.

thegame = PlayTheGame[pos]

Here we display the progress of the game in a graphics array.

Show[
      GraphicsArray[
        ListDensityPlot[#, DisplayFunction -> Identity]&/@thegame]];

Visualization

It is possible to display each move more clearly by using different colors for each player, as well as graphics that emphasize the placement of each domino.

The following variables store colors in which to display dominoes placed by the respective players.

\(color[0] = RGBColor[1, 0, 0]; 
color[1] = RGBColor[0, 0, 1]; 
    
$Player = 0; \)

The following definition of domino generates graphics primitives for a domino placed on the checkerboard.

domino[M_?MatrixQ] := 
      Module[{L}, 
        L = Reverse/@Sort[M]; $Player = 1 - $Player; {color[$Player], 
          Rectangle[L[[1]] - {3/4, 3/4}, L[[2]] - {1/4, 1/4}]}]

Here we begin a new game.

$Player = 0; 
    start  =  
      Partition[ReplacePart[Table[1, {16}], -1, {{r1}, {r2}, {r3}}], 4];

Here we tell Mathematica to play the game, and display its progress using ListDensityPlot.

thegame = PlayTheGame[start];

Show[
      GraphicsArray[
        ListDensityPlot[#, DisplayFunction -> Identity]&/@thegame]];

The variable board stores graphics showing the original state of the checkerboard, where the squares that have been removed are blacked out.

board = First[Graphics[ListDensityPlot[start]]];

The variable dominoes stores the graphics primitives representing each domino. (We “reverse engineer” the game to reveal the placement of a domino on each successive turn by subtracting adjacent board states and finding the positions of 1s.)

dominoes = 
      Map[domino, 
        Map[Position[#, 1]&, 
          Map[#[[1]] - #
                  [[2]]&, 
            Partition[thegame, 2, 1]]]];

Show[
      GraphicsArray[
        Map[Graphics[{board, #}, AspectRatio -> Automatic]&, 
          Table[Take[dominoes, turns], {turns, 0, Length[dominoes]}]]]];

Here are the Grundy numbers for each state of the board.

Map[Grundy, thegame]

A straightforward combination of the previous steps into a single function gives the following. The function ShowTheGame displays the progress of a game, and then returns a list of the successive Grundy numbers for each state of the game.

\(ShowTheGame[initialstate_] := 
	
      With[{thegame = PlayTheGame[initialstate], 
          board = First[
              Graphics[
                ListDensityPlot[initialstate, 
                  DisplayFunction -> Identity]]], 
          dominoes = 
            Map[domino, 
              Map[Position[#, 1]&, 
                Map[#[[1]] - #
                        [[2]]&, 
                  Partition[PlayTheGame[initialstate], 2, 1]]]]}, 
        Show[GraphicsArray[
            Map[Graphics[{board, #}, AspectRatio -> Automatic]&, 
              Table[Take[dominoes, turns], {turns, 0, Length[dominoes]}]]]]; 
        Map[Grundy, thegame]]\)

ShowTheGame[
      Partition[ReplacePart[Table[1, {16}], -1, {{r1}, {r2}, {r3}}], 4]]

Here is a larger board.

board5x5 = Partition[Table[1, {25}], 5]; 
    Do[board5x5[[i, i]] = 
        board5x5[[6 - i, i]] = 
          -1, {i, 5}]

ShowTheGame[board5x5]

The following game may initially take a good deal of time to compute, but because the Grundy values are cached the game can be replayed quickly.

board5x5 = Partition[Table[1, {25}], 5]; 
    Do[board5x5[[i, i]] = -1, {i, 5}]

ShowTheGame[board5x5]

Larger Computations

Although it is theoretically possible to determine which player wins on any board by calculating its Grundy number, the computation quickly becomes daunting, even for fast computers, as the board size increases. However, for a rectangular board with no squares removed, simple symmetry arguments tell us that the first player will win on a (2  n + 1)×2  m board by playing in the “center” and then answering symmetrically about the center; while the second player wins on a 2  n×2  m board by answering symmetrically the first player’s move. However, the (2  n + 1)×(2  m + 1) case is largely unknown (except when n = 0, in which case the Grundy numbers are “periodic”—see [3]). In [2], even the 5×5 board is listed as unsolved.

We shall use Mathematica to show that the 5×5 board is a win for the second player. Simply using our program to compute the Grundy number of the board proves inadequate, and so we must modify our approach.

First, we need to compute the Grundy numbers of only six representative first moves, because all other first moves made on the board are identical to one of these six by symmetry :

firstmoves=With[{w = {{{1}, {2}}, {{2}, {3}}, {{6}, {7}}, {{7}, {8}}, {{11}, {
                      12}}, {{12}, {13}}}},
	Table[
						Partition[ReplacePart[Table[1, {25}], 0, w[[i]]], 5],
			{i, Length[w]}]];

Show[
      GraphicsArray[
        ListDensityPlot[Reverse[#], Frame -> None, 
              DisplayFunction -> Identity]&/@firstmoves]];

The next thing we do is use a “primitive” Grundy numbering which replaces all nonzero numbers by the number 1. Thus a position will now have the number 1 if and only if one of its possible moves is numbered 0. This numbering has the two properties listed above for the ordinary Grundy numbering, and hence the first player wins if and only if the board has number 1. Moreover, it often allows us to compute the number of a position without knowing the numbers assigned to all its possible moves! For as soon as one of the possible moves for a position has Grundy number 0, we can assign the number 1 to the position. Of course, it is possible that all the possible moves have number 1 (in which case it is necessary to compute them all), which means the position has Grundy number 0.

An added benefit to the primitive Grundy numbering is that we don’t have to use the Mex function—we can simply play Throw and Catch: as soon as one of the possible moves of a position is found to have number 0, we immediately Throw a 1 to the enclosing Catch; while if all of the possible moves have number 1, we Throw a 0. (Note that there are some drawbacks to this simplified numbering. In particular, it lacks the “bogus nim property” which makes it easy to compute the sum of games—see [3].) We thus define the QuickGrundy function.

\(QuickGrundy[u_] := 
      \(QuickGrundy[u] = 
			
        With[{p = PossibleMoves[u]}, 
				
          Catch[
				
            Do[
					
              If[QuickGrundy[p[[j]]] == 
                  0, Throw[1]], 
						{j, 1, Length[p]}
					]; 
            
					Throw[0]
			]]\)\)

An additional complication is that each first move in the 5×5 board has itself over 30 possible moves; caching values for all of these and their possible moves, etc., is too large a strain on the computer’s memory, even when extended with virtual memory. Therefore we break up the calculation by testing each of the possible moves separately, reintroducing the QuickGrundy function between calls (which clears out the stored function values each time!). This is our function BreakUpQuickGrundy, which is thus a tradeoff: decreased speed for lower memory requirements.

We handle the re-definition of QuickGrundy inside BreakUpQuickGrundy by saving the original definition in the variable QuickGrundyOriginalDefn. The complete definition of any function, including all of its cached values, is stored in the list DownValues[FunctionName]; to restore the original definition, we simply set DownValues[QuickGrundy] equal to QuickGrundyOriginalDefn before testing each separate possible move.

QuickGrundyOriginalDefn = DownValues[QuickGrundy];

\(BreakUpQuickGrundy[boardstate_] := 
	
      With[{p = PossibleMoves[boardstate]}, 
	
        Catch[
		
          Scan[\((DownValues[QuickGrundy] = QuickGrundyOriginalDefn; 
			
                If[QuickGrundy[#] == 0, Throw[1]])\)&, 
			p]; 
		
          Throw[0]
		]]\)

Finally, Compute5by5 uses each of the six representative first moves for the 5×5 board, and computes their respective Grundy numbers using BreakUpQuickGrundy.

Compute5by5[] := Map[BreakUpQuickGrundy, firstmoves]

Compute5by5[]

It works. All of the six representative first moves have Grundy number 1 (which means all first moves have Grundy number 1) and thus the 5×5 board has Grundy number 0: hence it is a win for the second player. The computation takes under 2 hours on a PowerMac clone (PowerCenter Pro 210).

Final Remarks

Other “odd-by-odd” cases can also be investigated with Mathematica for the game of Cram. The 3×5 and 3×7 boards can be computed without difficulty and are wins for the first player; we have not tried the 3×9 and 3×11 boards, but they should be readily computable as well. The 5×7 should prove more difficult. We feel the 7×7 will need some further breakthrough before it can be done, even on a much faster computer. Perhaps sharing the computation among several computers (distributive processing) will be necessary. As we pointed out earlier, much can be learned from these games—not the least of which is learning which Mathematica programming techniques are most effective in carrying out these calculations.

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