acm-header
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.

ins01.gif

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

ins02.gif

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

ins03.gif

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

ins04.gif

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?

ins05.gif

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

ins06.gif

Blue then red then blue...

ins07.gif

Red continues to threaten...

ins08.gif

Blue responds...

ins09.gif

Red now gets three in a row...

ins10.gif

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

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.

Back to Top

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


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: