## Ticktacktoe Games

"It's as simple as tit-tat-toe, three-in-a-row, and as easy as playing hooky. I should hope we can find a way that's a little more complicated than that, Huck Finn."

—Mark Twain, The Adventures of Huckleberry Finn

Ticktacktoe (the spelling varies widely) is not nearly so simple as Tom Sawyer thought. When Charles Sanders Peirce wrote his Elements of Mathematics, a textbook that was not published until 1976, he included a 17-page analysis of only the side opening of this ancient game. It was one of Peirce's many anticipations of "modern math." Today's progressive teachers frequently use ticktaktoe to introduce their pupils to such concepts as the intersection of sets, rotational and mirror-reflection symmetry, and higher Euclidean space. In this chapter we consider some unusual aspects of the game not covered in two earlier columns reprinted in The Scientific American Book of Mathematical Puzzles & Diversions (Chapter 4), and Mathematical Carnival (Chapter 16).

The traditional game, as most readers surely know, is a draw if both players do their best. From time to time pictures of a ticktacktoe game appear in advertisements and cartoons, and sometimes they provide pleasant little puzzles. For example, on May 13, 1956, in the New York Herald Tribune, there was an IBM advertisement with the unfinished game at the left in Figure 52. Which player went first, assuming that the players were not stupid? It takes only a moment to realize that 0 could not

 X X 0 ,o_ x X 0 X "Öl X 0 0 0 x 0 X 0 X

Three easy ticktacktoe puzzles

Three easy ticktacktoe puzzles have gone first or X would have played the top left corner on his second move. The other two patterns are almost as trivial. Does the center one, from a Little Lulu cartoon in The Saturday Evening Post (January 16, 1937), depict a possible game? At the right is a pattern from an advertisement by publisher Lyle Stuart in The New York Times (June 1, 1971). In which cell must the last move have been made?

If the first player, say X, opens in the center cell, he can force a draw that always ends with the same basic pattern. This underlies several prediction tricks. For example, the magician draws the finish of a game, with all cells filled, on a square sheet of paper that he turns face down without letting anyone see it. He then plays a ticktacktoe game with someone, writing on another square sheet. After the game ends in a draw he turns over his "prediction." The two patterns match cell for cell.

The technique is explained in Figure 53. X plays the center opening. If O marks any corner cell, X forces the draw shown at the left in the illustration (moves are numbered in order of play). It is only necessary for X to remember where to make his second move, since all moves are forced from then on; a simple rule for the second move is to consider the corner opposite O's first move and then play adjacent to it on the clockwise side. If O responds to the opening with a side cell, X forces the draw shown at the right. In this situation only O's moves are forced

 02 °4 X5 08 02 X X1 08 x5 X, 0 X3 X9 04 X9 X

A ticktacktoe prediction trick

A ticktacktoe prediction trick and X must remember how to play his next four moves. The following simple rule was proposed by a magician who signed himself "Thorson" when he described this trick in the September 1960 issue of M.U.M., official organ of the Society of American Magicians: X makes his second, third and fourth moves adjacent and clockwise to O's previous moves, and his fifth move in the only remaining empty cell.

Note that the two final results are identical. Of course, each game can be played in any of four different orientations. The magician, recalling which corner of his inverted prediction has the O surrounded by three X's, casually turns over the square sheet along the proper axis—orthogonal or diagonal—so that his predicted pattern matches the orientation of the game just completed.

The trick can even be repeated. This time X substitutes counterclockwise for clockwise in the rules, having drawn a prediction that is a mirror image of the preceding one. The two predictions will not match in any orientation and few people will realize that they are mirror reflections of each other.

Dozens of variations of planar ticktacktoe have been analyzed. Standard games on squares of higher order than 3, when the goal on an order-n board is to get n in a row, are uninteresting because the second player can easily force a draw. My first column on ticktacktoe discussed games in which counters are moved over the board (one such version goes back to ancient Greece), and toetacktick, in which the first to get three in a row loses.

A. K. Austin's "wild ticktacktoe," in which players may use either X or O on every move, was shown to be a first-player win in my Sixth Book of Mathematical Games, Chapter 12, Problem 3. What about "wild toetacktick," in which players can choose either mark on each move and the first three-in-a-row loses? In 1964 Solomon W. Golomb and Robert Abbott independently found that the simple symmetry strategy by which the first player can force at least a draw in standard toetacktick also applies to the wild version. A center opening is followed by playing directly opposite the other player's moves, always choosing X if he played O and 0 if he played X. The question remains: Does the first player have a winning strategy in wild toetacktick? Abbott made an exhaustive tree diagram of all possible plays and proved that the second player too can force a draw. Tame toetacktick also is a draw if both sides play rationally.

An amusing variation appears in David L. Silverman's book of game puzzles, Your Move. The rules are the same as in standard ticktacktoe except that one player tries to achieve a draw and the other player wins if either of them gets three in a row. Can the reader show that no matter who plays first the player trying to force a row of three can always do so? Silverman does not answer this in his book, but I shall give his solution in the Answer Section.

It is impossible to describe all the other planar variants that have been proposed, such as using numbers or letters as marks for the goal of forming a certain sum or spelling a certain word; playing on the vertexes of curious nine-point graphs (for a game on one such graph see my Mathematical Magic Show, Chapter 5, Problem 5); using counters with X on one side and 0 on the other, with the counters turned over according to specified rules. Games have been marketed in which flip-overs are randomized by concealed magnets that may or may not reverse a counter or by tossing beanbags at a board to cause cubical cells to alter their top symbols by rotating.

If ticktacktoe is played on an unlimited checkerboard, it is a trivial win for the first player if the goal is to get four or any smaller number of one's marks in an orthogonal or diagonal row. When the goal is five in a row, this game is far from trivial. It is the ancient Oriental game known as go-moku (five stones) in Japan, where it is played on the intersections of a go board. (The game is sold in the U.S. by Parker Brothers under the name of Pegity.) Although it is widely believed that a first-player winning strategy exists, this has not yet, to my knowledge, been proved.

There is no doubt about the first player's strong advantage in unrestricted go-moku. Indeed, it is so overwhelming that in Japan the standard practice is to weaken the first player by not allowing the following moves:

(1) A move that simultaneously creates a "fork" of two or more intersecting rows of open threes. By "open three" is meant any pattern in which a play will form a row of four adjacent stones that is open at both ends. There is one exception. A fork move is permitted if it is the only way to block an opponent from completing a row of five.

(2) A move that forms a row of more than five. In other words, the winning move must be exactly five.

In master play, both rules are usually applied only to the first player. Under these rules, the game is commonly called "renju" in Japan.

It has been conjectured that if there is a winning strategy for the first player in unrestricted go-moku, on a large enough board, there will be a winning strategy on a sufficiently large board even if the prohibitions are observed, but this is far from established. Even if a winning strategy is found for unrestricted go-moku, difficult questions will remain. What is the smallest board on which the first player can win? What is the shortest way to win? The two questions may or may not be answered by the same line of play.

It is not possible that the second player has a winning strategy in unrestricted go-moku or similar games in any dimension. The bare bones of the simple reductio ad absurdum proof, first formulated by John Nash for the game of hex, are as follows. Assume that a second-player winning strategy exists. If it does, the first player can make an irrelevant, random first play—a play that can only be an asset—and then, since he is now in effect the second player, win by appropriating the second player's strategy. Because this contradicts the assumption, it follows that no second-player winning strategy exists. The first player can either win or at least force a draw if the game allows draws.

Go-moku is a stimulating game. To catch its special flavor the reader is urged to study a position from Silverman's book [see Figure 54] and determine how O can play and win in five moves. Note that X has an open-end diagonal of three, which he threatens to lengthen to an open-end row of four.

 0 X 0 X X 0 X X 0 0 0 X 0 X X X 0

Go-moku problem: 0 to play and win

When ticktacktoe is extended to three dimensions, the first player wins easily on an order-3 cube by first taking the center cell. As Silverman points out, if the first player fails to open with the center cell, the second player can win by taking it; if the center is permanently prohibited to both players, the first player has an easy win. Three-dimensional toetacktick (the first row of three loses) is also a win for the first player. He plays the same strategy used for forcing a draw in planar toetacktick: He first takes the center and then always plays symmetrically opposite his opponent. Since drawn positions are impossible on the order-3 cube, this technique forces the second player eventually to form a row of three. Daniel I. A. Cohen, in a paper listed in the bibliography, proves that, as in the case of planar toetacktick, this is a unique winning strategy. The first player loses if he does not open by taking the central cell, and also loses if, after making this first move, he does not follow antipodal play.

Draw games are possible on the order-4 cube, but whether the first player can force a win is not, as far as I know, positively established. (There cannot, of course, be a second-player win because of Nash's proof.) As with go-moku, the first player has a strong advantage and a winning strategy is believed to exist. Many computer programs for this game have been written, but the complexity of play is so enormous that I do not think a first-player win has yet been rigorously demonstrated. About a dozen readers have sent me what they consider winning strategies, but detailed formal proofs are still unverified. Most of the strategies involve first taking four of the eight central cells and then proceeding to a forced win. Virtually nothing is known about three-dimensional games where counters are allowed to move from cell to cell.

Another unexplored type of 3-space game is one in which two players alternately draw from a limited supply of unit cubes of two or more colors to build a larger cube with some winning objective in view, for example, using cubes of n colors and trying to get a row, on an order-n cube, in which all n colors appear. For such games gravity imposes restraints, since cubes cannot be suspended in midair.

Because drawn games of standard ticktacktoe are possible in 2-space on an order-3 board, and in 3-space on an order-4 board, it was once conjectured that in a space of n dimensions the smallest board allowing a draw was one with n + 1 cells on a side. It turned out, however, that although in w-space a board of order n+1 or higher always allows a draw, it is sometimes possible for an n-space board of fewer than n+1 cells on a side to allow a draw. This was first established about 1960 by Alfred W. Hales, when he constructed a draw on the order-4 hyper-cube, or fourth-dimension cube.

Several readers have sent informal but probably valid proofs that the first player can always win on the order-4 hypercube. Whether or not he can force a win on the order-5 hypercube is yet another of the many unanswered questions about extensions and variants of what most people, like Tom Sawyer, regard as a "simple" game.

0 0