# Communications of the ACM

Last byte

## Open Field Tic-Tac-Toe

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?

### Author

Dennis Shasha (dennisshasha@yahoo.com) 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.

### Footnotes

All are invited to submit their solutions to upstartpuzzles@cacm.acm.org; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html