MathSource Reviews
n-D Noughts and Concomitant Crosses

by Matthew M. Thomas

Given the lighthearted subject of this Review, it seems appropriate that we begin with this entry from page 406 of the 1951 Oxford Dictionary of Mother Goose Rhymes [Gardner 1959]:

Tit, tat, toe,
My first go,
Three jolly butcher boys all in a row.
Stick one up, stick one down,
Stick one in the old man's crown.

Your reviewer played this game as a child; so did you. On the Continent, the game is commonly known as noughts and crosses; in the States, tic-tac-toe (or ticktacktoe). In this MathSource Reviews column, let us first delve into the background of this ancient game. We'll then examine MathSource item /Applications/Other/0209-247, TicTac.nb by Jon McLoone of Wolfram Research Europe Ltd. Even though WRI's McLoone labels his contribution "TicTacToe Game," we pay heed to his European station by using a play on the European name for this column's title; throughout the column, we shall also be using the "noughts and crosses" name. After examining TicTac.nb and running its code, we shall conclude with an overall assessment.

BACKGROUND

The conventional version of the game is played on a two-dimensional, 3x3 square board, between player O (noughts) and player X (crosses). In keeping with the convention adopted by McLoone, player O always moves first. The object of the game is to place three of one's own marks in a horizontal, vertical, or diagonal row on the board. Players O and X alternate mark placement until either a player achieves three marks in a row, or the nine spaces are filled but with neither player achieving three-in-a-row. There are 9! or 362,880 sequences for filling those nine spaces with Os and Xs. When board symmetry, rational play, and other factors are taken into consideration, the number of viable paths to completion are far fewer than 9! If one were to fill a noughts-and-crosses board with every possible sequence of five Os and four Xs, first player O would win 212,256/362,880 = .585 of the games, second player X would win 104,544/362,880 = .288 of them, and 46,080/362,880 = .127 would result in stalemates. With rational play (striving for three marks in a row; blocking similar attempts by the opponent) on both sides, however, the rational game outcome is a draw -- not one-eighth of the time, but eight-eighths of the time.

The conventional version of the game is finite (comes to a definite end), with no element of chance and with perfect information available to both players. Since the only rational game outcome is a draw, a win can occur only by one player "trapping" the other (i.e., positioning his marks such that he can achieve three-in-a-row along either of two separate paths with his next move). Of the nine board spaces, four are corners, four are sides, and one is a center: If first player O opens by taking a corner, second player X must take center to avoid a trap; if O opens by taking a side, X must take center, an adjoining corner, or the in-row side to avoid a trap; if O opens by taking center, X must take a corner to avoid a trap[Gardner 1959, p. 38]. Berlekamp, Conway, and Guy [Berlekamp et al 1982, pp. 670-671] offer a complete and thorough mapping from any board state to each possible outcome, with a total of 104 quasi-unique outcomes in which first player O wins 47 times, second player X wins 16 times, and stalemates occur 41 times.

Simple 3x3 noughts and crosses is the (3^2) entry in a set of (k^n)games (k = spaces along any side; n = dimensions of the hypercubic game board). It has been shown [Moser 1948] that for (k^n) noughts and crosses, there are ((((k + 2))^n) - (k^n))/2 paths to k-in-a-row. So, for conventional 3x3 play, there are eight such paths (three horizontal, three vertical, two diagonal); for 4x4x4 (k = 4, n = 3), there are seventy-six (48 orthogonal, 24 planar diagonal, 4 main cube diagonal). For both 3x3 and 4x4x4 play, draw positions exist, but for 3x3x3 play, the first player O can always force a win (and, in fact, no draw sequence exists): The original theorem was that if k ≥ (3^n) - 1 (odd k) or k ≥ (2^(n + 1))- 2 (even k), then the second player X can force a tie, but if n is sufficiently large compared to k, then the first player O can force a win [Hales and Jewett 1963]. A subsequent theorem implies that the second player X  can force a draw if k > c n log n or (2^([(({{k}, {2}}))-1])) > (({{n}, {k}})) [Erdös and Selfridge 1973]. Beck in turn theorizes that if k ≥ ((log 3)/(log 2)) n + 4 (Sqrt[n log n]) + 4 and n ≥ 100 (100-dimension tic-tac-toe!), then the second player can force a draw [Beck 1981]. Paul provides an alternate proof to the 1948 work by Moser et al regarding k-in-a-row paths in (k^n)noughts and crosses, and asserts that even when draw positions exist, first player O might still be able to force a win [Paul 1978]; it was later proved that draw positions exist whenever k ≥ n  and n ≥ 4 . . . though the existence of such positions is no guarantee that second player X can force a draw [Paul 1979].

Tying together these trails of (k^n)noughts and crosses theory is an exemplary work from Oren Patashnik of Bell Laboratories [Patashnik 1980]. Rather than put forward yet another theory relating the sizes of k and n to whether second player X can force a draw, Patashnik presents a 75-element grid for 1 ≤ k ≤ 15 and 1 ≤ n ≤ 5: For each of the 75 (k^n)noughts and crosses game arrangements, the grid lists number of spaces in the game board, number of paths to k-in-a-row, number of "strongest-point-lines" (a parameter corresponding to Hales and Jewett's work), and whether the game is class 1 (no draw position exists; first player O can force a win), class 3 (second player X can force a draw), or class 2 (draw positions exist; first player O can nevertheless force a win). Patashnik labels 4x4x4 noughts and crosses "Qubic". Using 1500 computer hours on a PDP10 in the Yale University computer science department (and despite "wasting" half of them on bad strategic moves), Patashnik proved Paul's [1978, p. 46] conjecture that (4^3)noughts and crosses both allowed a forced win by first player O and contained draw positions. As such, Qubic became the first known member of what Patashnik labeled class 2. Others initially criticized but ultimately accepted the findings of Patashnik's work [Berlekamp et al 1982, p. 674].

The 3x3 version of noughts and crosses is a natural test case for artificial intelligence programs. For example, it is used to illustrate application of "minimax" tactics [Nilsson 1980]. The first step of such application is to define an evaluation function e(p) of position p  as +∞ (when p is a winning position for first player O), -∞ (when p is a winning position for second player X, or {number of three-in-a-row paths still available to O}-{number of three-in-a-row paths still available to X} (when p is not a winning position). As such, a first move by O to center produces e(first O = center) = 8 - 4 = +4; likewise, e(first O = corner) = 8 - 5 = +3 and e(first O = side) = 8 - 6 = +2. A minimax approach directs first player O to take the center first. Once second player X makes his first move, the strategy for O considers all possible responses by X to all possible second moves by O. The strategy computes e(p) for all possible X responses to each possible O second move, and assigns the minimum of those values to each possible second move; O then chooses the proposed second move with the maximum assigned e(p) value. The strategy is applied in this lookahead fashion for O after each countermove by X. In contrast to the minimax strategy, which directs first player O to take the center first, Gardner [1959, p. 38] would take a corner first, since of the eight first moves available to second player X, only one (center) avoids a trap; taking center first allows X trap avoidance via four of eight available first moves. What does Jon McLoone's MathSource contribution advise?

HOW IT WORKS

As mentioned earlier, our MathSource item for review is /Applications/Other/0209-247/TicTac.nb, a 62 kB Mathematica notebook labeled "TicTacToe Game" by Jon McLoone, who had been with Wolfram Research Europe Ltd. at least at the time of his item's submission to MathSource. This notebook is optimized for version 3.0 of Mathematica -- if you have any doubt about that, let the "Mathematica 3.0" banner at the top of TicTac.nb lift your doubt to faith. Unlike pre-3.0 notebooks, TicTac.nb offers you a control panel by way of a 2x2 buttons grid: These four buttons are labeled (clockwise from upper left) Human-Human, Computer-Human, Computer-Computer, and Human-Computer. Two such panels appear: One under "Start 2D Game"; the second under "Start 3D Game". As such, you the TicTac.nb user have eight options for noughts-and-crosses play. The labels on the buttons explain those options for the most part. The "A-B" format for each label means that A becomes first player O, while B is second player X. Extensive use is made of StyleBox[], ButtonBox[], RowBox[], GridBox[], and related functions and their options . . . functions and options which debuted with Mathematica 3.0. Here is the aforementioned 2x2 buttons grid as it actually appears in TicTac.nb:

Beneath the 2-D and 3-D control panels is a section labeled "Modification notes". Within the section is an explanatory paragraph: Read it and learn that $InitialRunningOrder = {"O", "X"} assigns noughts to the first player and crosses to the second, that default values are k = 4 for n = 3 and k = 3 for n = 2 (i.e., 4x4x4 and 3x3 game boards), that varying k produces forced win game boards (generally the case only upon shrinking k for a given n), that computer-controlled tactics are based on maximizing TotalScore[], which in turn is based on ScoreOnDimension[], and that the algorithms behind these tactics are "ex[t]remely simple" and have a one-move lookahead constraint. A request for better tactical algorithms is also made in this section. Note: If it drives you crazy to follow the convention of noughts playing first, you need only set $InitialRunningOrder to {"X", "O"}; doing so, however, causes a computer-first move upon clicking "Human-Computer", and likewise a human-first move when "Computer-Human" is chosen.

The Mathematica code itself in TicTac.nb comprises four sections (all of which could have benefited from more (* in-line comments *) to explain the code). "Set Up" sets $InitialRunningOrder, and creates $RunningOrder to keep track of whose turn it is to mark the game board throughout the contest. "Playing & displaying" uses PlaceAt[], MakeDisplayCall[], and new (to version 3.0) built-in functions such as Notebook[] and Cell[] and variants thereof to create, update, and maintain the active game board. This board is shown in a separate Window, as a grid in the n = 2 case and as a row of k grids (each k x k) in the n = 3 case. These TicTac.nb functions do not implement tactics, but do show the results of both such tactics and human responses. "Scoring & choosing moves" is where tactical decisions are made, through functions such as OneInGameGridQ[], InGameGrid[], SameDimension[], WhatsOnDimension[], CountOnDimensionRule[], ScoreOnDimension[], TotalScore[], and FindBestScore[]. FindBestScore[] returns the best next move, based on the highest TotalScore[] value for all available positions. TotalScore[] in turn relies upon ScoreOnDimension[], which for an available game board position and vector (four vectors for n = 2; thirteen for n = 3) assigns a position value based on the six tests (below). ScoreOnDimension[] uses the other aforementioned functions in "Scoring & choosing moves" to handle various and sundry bookkeeping chores. Finally, the "End" section (somewhat paradoxically) carries out instructions that begin a new game.

The critical ScoreOnDimension[] function in TicTac.nb is written around a Which[] conditional function. Six tests/values (and a default value of zero) are built into this use of Which[]. For a given game board space and vector, here are those six tests and corresponding values:
1) if a player has k marks in a row, value = ∞ (player has won)
2) if the opponent has k marks in a row, value = ∞ (opponent has won)
3) if a game board space is free, and filling it would make k-in-a-row for the player, value = 20,000 k
4) if a game board space is free, and filling it would block k-in-a-row for the opponent, value = 10,000 k
5) if, along a vector, the sum of spaces filled by a player's marks plus free spaces equals k, value = 1 + (((spaces filled by player' s marks))^2)
6) if, along a vector, the sum of spaces filled by the opponent's marks plus free spaces equals k, value = (((spaces filled by opponent' s marks))^2).
For a given game board space, once ScoreOnDimension[] has been applied for all four n = 2 vectors (or all thirteen n = 3 vectors), TotalScore[] adds the ScoreOnDimension[] output for each vector, and FindBestScore[] takes the available game board space with the highest TotalScore[] output.

PLAYING THE GAME

A true benefit to working with TicTac.nb is learning about version 3.0 functions such as ButtonBox[]. In presenting the eight "user interface" buttons described above, and in creating the new Window in which the game board is presented, TicTac.nb makes extensive use of such functions. Alas, upon opening this notebook and first running a 2-D or 3-D "Computer-Computer" game, one gets a Mathematica error message about a string that causes a problem. A bit of probing reveals this problem to be with ScoreOnDimension[]. When your reviewer copied the functions in TicTac.nb  and pasted them into a word processor file, all but one took on a normal appearance in that file. The exception was ScoreOnDimension[]: It was encased within the "\!\(. . .\)" feature, and replete with RowBox[] and StyleBox[] functions . . . functions having nothing to do with the duties of ScoreOnDimension[]. The "\(. . .\)" feature uses the textual input it contains to specify boxes for construction, and the "\!" feature calls for interpreting the boxes (see p. 984 of the Mathematica book, third edition). But these features are clearly out of place in ScoreOnDimension[]. Their effect seems to be to prevent initial evaluation of ScoreOnDimension[]. With this vital function disabled, FindBestScore[] can recommend only the next available game board space it encounters, and MakeDisplayCell[] cannot recognize k-in-a-row for X or O. "Computer-Computer" play in 2-D thus merely places alternating O and X marks in spaces from right to left, bottom to top. Here is the 2-D result (integers denote order of moves):

TicTac.nb flags neither the diagonal O5-O3-O1 three-in-a-row nor the O2-O3-O4 three-in-a-row for first player O, and "mindlessly" continues play even after O wins with upper-right corner move O4.

Fortunately, fixing ScoreOnDimension[] seems to require as little as adding a superfluous space to one of its comment lines, and evaluating the resulting cell. What actually ails this function in TicTac.nb your reviewer still does not know, but at least the function can be made to work properly easily. And with its most important function now working properly, TicTac.nb plays (3^2) and (4^3) noughts and crosses as intended. For "Human-Human" play, ScoreOnDimension[] is not needed, as two users place their marks in available spaces by clicking on those spaces; MakeDisplayCell[] uses a red background to highlight k-in-a-row marks, declare a winner, and end the game. When playing for both O and X, TicTac.nb does not offer much variety to a spectator. Here are the outcomes of every single 2-D and 3-D "Computer-Computer" game played by TicTac.nb (the numbers denote the order played; the first player is O):

({{X4,  ,  , O4}, { ,  ,  ,  }, { ,   ,   ,  }, {X3,  ,  , O3}})({{ ,  ,  ,  }, { ,  ,  , X6}, { ,   ,   , X7}, {  ,  ,  , X8}})({{ ,  ,  , O9}, { ,  ,  , O7}, { ,   ,   , O6}, {  ,   ,  , O8}})({{X2,  ,  , O2}, { ,  ,  , X5}, { ,   ,   , O5}, {X1,   ,  , O1}})

That TicTac.nb follows the same path with each game should not evoke surprise. No randomizing mechanism is built into its functions, and the rules followed by ScoreOnDimension[] are static. Of course, two players rigidly following a minimax strategy [Nilsson 1980] would likewise follow the same path for each game (with possible allowances for symmetric spaces). In "Computer-Human" 2-D play, the program unfailingly takes center with the first move of each game, as would a player following a minimax strategy. Second player X can only respond by taking a corner or a side. For each response, here are the TotalScore[] outputs for each space available for the second move of first player O:

({{X,  ,  }, { , O,  }, { ,  ,  }})({{ , 3, 4}, {3,  , 3}, {4, 3, 2}})    ({{ , X,   }, { , O,  }, {  ,   ,  }})({{4,  , 4}, {3,  , 3}, {4, 1, 4}})

Except for the bottom right corner in the first case, the corners come highly recommended for the second move by O. In the first case, O will then take the bottom left corner, forcing an upper-right corner block by X, forcing a top side block by O, forcing a bottom side block by X, allowing a left or right side move by O, and forcing a side move stalemating block by X. In the second case (since TicTac.nb evaluates available spaces right to left, bottom to top), O will take the bottom right corner, forcing a top-left corner block by X, forcing a top-right corner block by O which is also a winning trap for O. Note in the first case that had the second move by O been to the lower right corner (the "weakest" available space, given its lowest TotalScore[] value), and had X responded by taking any side for its second move, the third move by O could have been a winning trap. Tactics such as those of minimax and ScoreOnDimension[] are incapable of such subtlety.

In "Human-Computer" 2-D play, this lack of subtlety leads to the defeat of TicTac.nb. Let's say that, as first player O, the human follows Martin Gardner's advice and takes a corner for a first move. The highest TotalScore[] then corresponds to the center, so second player X takes center. At this point, here are the game board and the TotalScore[] values for the available board spaces:

({{O,  ,  }, { , X,  }, { ,  ,  }})({{ , 3, 4}, {3,  , 2}, {4, 2, 2}})

If the human player disregards these values and takes the bottom right corner as a second move, our situation becomes:

({{O1,  ,  }, { , X1,  }, { ,  , O2}})({{ , 3, 4}, {3,  , 3}, {4, 3,  }})

TicTac.nb will now force X to take a corner for its second move, allowing O to take the remaining corner for the block and the winning trap. But even the minimax strategy would have put X in a corner for its second move. As is shown both in this case and in the case where second player X takes a corner in response to a first player O center opening, these tactics have difficulties with defending against and setting up the cornerstone move of rational noughts and crosses -- the trap. As part of his work with Qubic, Patashnik has amassed a sizable collection of successful moves and countermoves for this 4x4x4 version of noughts and crosses [Berlekamp et al 1982]. A creative exercise would be to inflict this collection upon 3-D "Human-Computer" and "Computer-Human" TicTac.nb -- as well as upon a minimax-driven program -- and observe how this trap-blindness manifests itself given the added spatial dimension.

ASSESSMENT

Jon McLoone's TicTac.nb has a befuddling (though easily "solved") problem with its cornerstone function, ScoreOnDimension[], and it is a problem with which MathSource users should not have to deal. Within and in addition to ScoreOnDimension[], the code within TicTac.nb contained far too few (* comments *) to constitute good documentation, especially for an author in the employ of Wolfram Research. The notebook's playing tactics are admittedly suspect. But the simple TicTac.nb strategy in no way discredits Jon McLoone, for his Modification Notes within TicTac.nb disclaim any sophistication on behalf of the simple tactics; in fact, those Notes actually invite more sophisticated tactics to be sent to McLoone. To his explicit credit, McLoone has built an excellent showcase for the new (to 3.0) "box"-based and Windows-manipulation functions: Mathematica workers wishing to build a "user interface" within a notebook have a very useful model in TicTac.nb.

To the cynical "The basic [noughts and crosses] strategy is sufficiently simple that bright chimpanzees have been trained to play with credible performance" [Epstein 1977, p. 338], we offer Martin Gardner: "I have observed that many ticktacktoe players are under the mistaken [emphasis added] impression that because they can play an unbeatable strategy they have nothing more to learn about the game" [Gardner 1959, p. 45]. This legend from the pages of Scientific American was referring primarily to the 3x3 game, but his words certainly also apply to Qubic and higher-dimension versions of the game. Given Mathematica's charter support of higher-dimension arrays, an enhanced version of TicTac.nb can help with this learning: Its 3-D features are ready-made for Qubic, and it can be readily made to address the k,n versions in the 1980 table from Patashnik. Perhaps it can even be extended to address the ≥100-dimension version of the game to which Beck's 1981 theorem applies. That extension, however, is left as an exercise for those singularly dedicated to "stick[ing] one in the old man's crown".

REFERENCES

Beck, József. "On Positional Games", Journal of Combinatorial Theory, Series A, 30(2), 117-133 (1981).

Berlekamp, Elwyn R., Conway, John H. and Guy, Richard K. "Lines and Squares", Chapter Twenty-Two of Winning Ways for Your Mathematical Plays (Volume 2: Games in Particular). Academic Press, London, 667-693 (1982).

Epstein, Richard A. The Theory of Gambling and Statistical Logic. Academic Press, New York (1977).

Erdös, P. and Selfridge, J.L. "On a Combinatorial Game", Journal of Combinatorial Theory, Series B, 14(3), 298-301 (1973).

Gardner, Martin. "Ticktacktoe", Chapter Four of The Scientific American Book of Mathematical Puzzles & Diversions. Simon and Schuster, New York, 37-46 (1959).

Hales, A.W. and Jewett, R.I. "Regularity and Positional Games", Transactions of the American Mathematical Society, 106(2), 222-229 (1963).

Moser, Leo. "Noughts and Crosses", American Mathematical Monthly, 55, 99 (February 1948). [Note: The Moser contribution is a solution to Elementary Problem 773 proposed by A.L. Rubinoff in the same journal, 54, 281 (May 1947). Not only Moser but also Rubinoff and N.J. Fine are credited with solving E773 in February 1948; alas, only Moser's name seems to live on in association with that solution.]

Nilsson, Nils J. Principles of Artificial Intelligence. Tioga Publishing Co., Palo Alto, CA, 115-121 (1980).

Patashnik, Oren. "Qubic: 4x4x4 Tic-Tac-Toe", Mathematics Magazine, 53(4), 202-216 (1980).

Paul, Jerome L. "Tic-Tac-Toe in n-Dimensions", Mathematics Magazine, 51(1), 45-49 (1978).

Paul, Jerome L. "Partitioning the Lattice Points in (R^n)", Journal of Combinatorial Theory, Series A, 26(3), 238-248 (1979).

ABOUT THE AUTHOR

Matthew M. Thomas completed his doctorate in chemical engineering at Washington University in St. Louis in December 1995. In early 1995, he co-wrote the "Intelligent Control of Product Quality in Composite Manufacturing" chapter of Processing of Composites, edited by Raju S. Davé and Alfred C. Loos (Hanser Gardner Publishing, Cincinnati, 2000).

thomas@wuche2.wustl.edu