Sign In

Communications of the ACM

Last byte

Open Field Tic-Tac-Toe

Open Field Tic-Tac-Toe, illustration

In the spirit of Gomoku, two people play a version of the classic paper-and-pencil game tic-tac-toe but on an infinite checkerboard. In it, a player wins by getting four pieces in a row—vertically, horizontally, or diagonally.

Warm-up. Can the first player—blue—force a win in seven turns or less, where a turn consists of both blue and red placing pieces.

Solution to warm-up. The first player can force a win in five turns. Blue moves. No matter where red moves, blue can, in the second move, have two in a row.


Red must now respond to prevent blue from having three in a row that is open on both ends. So R blocks, giving us something like


Blue can now force a two-by-two fork with


No matter where red goes, blue can force an open-ended vertical or horizontal line with three blues, as in


So... now that we know how it works, let us try it for some other problems.

Suppose we have a board with a nine-by-nine grid with the following configuration, and red is about to take the next turn. Can either side force a win?


Solution. Yes, red can force a win. Red threatens...


Blue then red then blue...


Red continues to threaten...


Blue responds...


Red now gets three in a row...


Upstart. Suppose the board is a six-by-six grid with a red exactly in every corner? Blue moves first. There is no limit on the number of turns. Can either side force a win?

Back to Top


Dennis Shasha ( is a professor of computer science in the Computer Science Department of the Courant Institute at New York University, New York, as well as the chronicler of his good friend the omniheurist Dr. Ecco.

Back to Top


All are invited to submit their solutions to; solutions to upstarts and discussion will be posted at

Copyright held by the author.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account
Article Contents: