Addendum

John Selfridge reports that a solution has been found for his "4 x 4 infinity" ticktacktoe. This is played on a strip that is four cells high and infinitely wide, the winner being the first to get four of his marks in an orthogonal or diagonal row. Carlyle Lustenberger, in his master's thesis in computer science at Pennsylvania State University, developed a computer program with a winning strategy for the first player on a four-by-30 board. The actual lower bound for the width is a few cells shorter, but I have not obtained the details.

The three-by-infinity board is a trivial win for the first player on his third move; indeed, the same win can be achieved if only one cell is added to the side or corner cell of the traditional order-3 ticktacktoe field. The five-by-infinity board remains unsolved. If a win for the first player could be found on this board, it would, of course, solve the go-moku game when it is played on an arbitrarily large square, with no restrictive rules.

Owen Patashnik, of Bell Laboratories, was the first to write a computer program that establishes a first-player win in 4 x 4x4 ticktacktoe. I had the honor of announcing the verification of his 1977 program in my Scientific American column of January 1979. It required 1,500 hours of computing time, and has been likened to the computer proof of the four-color map theorem in its length and complexity. I will say no more about it here because Patashnik has so thoroughly and amusingly reported on it in his paper listed in the bibliography. The program's set of 2,929 strategic moves for winning is probably far from minimal, but I know of no program that has reduced them.

In 1973 the Netherlands issued a 30+ 10 cents stamp depicting a drawn pattern in a ticktacktoe game.

Shein Wang, a computer scientist at the University of Guelph, Guelph, Ontario, Canada, has been publishing a monthly Gomoku Newsletter since 1979, and the university has, since 1975, been sponsoring a North American computer gomoku tournament. The programs have been steadily improving.

A popular variation of go-moku is on sale in the United States under the trade name Pente. Invented by Gary Gabel, it combines go-moku with elements of go. (See Newsweek, May 10, 1982, page 78.)

Several readers wrote to emphasize that Nash's proof applies only to unrestricted go-moku. The proof rests on the irrelevance of an extra stone, but in restricted go-moku the rules permit situations in which an extra stone can damage the player who owns it.

Henry Pollak and Claude Shannon apparently were the first to prove that the second player can force a draw in unrestricted n-in-a-row ticktacktoe on a large enough board when ra = 9 or more. Their 1955 proof has not been published. It is given by T. G. L. Zetters in his answer to a problem, American Mathematical Monthly, Vol. 87, August—September 1980, pages 575—576. Zetters goes on to show how the proof can be extended to n = 8 or more. So far as I know, the question is still open for n = 5, 6 and 7.

W. F. Lunnon, writing in 1971 from University College, in Cardiff, gave a simple pairing strategy of unknown origin that guarantees a draw for the second player in 5 x 5 ticktacktoe. Number the cells as shown in Figure 57. Whenever the first player occupies a numbered cell, the second player takes the other cell of the same number. Since every line of five has a pair of like-numbered cells, the first player cannot occupy all five. If the first player takes the unlabeled center, the second player may take any cell, and if the cell he is required to take by the pairing strategy is occupied, he may play anywhere.

Lunnon also reported that he and Neil Sloane, of Bell Labs, had together found a remarkable second-player drawing strategy, based on cell pairing, for the 6x6 board. Not only does it

Figure 57

2

10

5

5

1

6

9

12

8

9

6

11

11

4

7

10

12

7

4

1

3

3

8

2

W. F. Lunnon's pairing strategy

W. F. Lunnon's pairing strategy block wins on any row, column or main diagonal, it also blocks a win on any broken diagonal! The cells are numbered as shown in Figure 58. As before, the strategy is to take the cell with the same number as the cell just taken.

Figure 58

1

13

2

13

3

12

6

14

5

14

4

12

7

8

15

9

10

15

16

3

11

1

16

2

17

4

11

6

17

5

7

8

18

9

10

18

Lunnon-Sloane second-player drawing strategy

Lunnon-Sloane second-player drawing strategy

There is more. The Lunnon-Sloane numbering leads to an elegant proof that 9-in-a-row unrestricted go-moku is a draw. Cover the infinite board with copies of the 6x6 matrix. The second player can force a draw by always taking the nearest cell with the same number as that of the previous play. It is easy to see that the first player can obtain no line longer than 8.

For nXn boards, n equal to 6 or higher, it is trivially easy to put a unique pair of numbers in each row of n cells and so provide a drawing strategy for the second player. For n equal to 3 or 4, no such labeling is possible, and the draw has to be established in uglier ways.

0 0

Post a comment