Opinion
Last byte

Open Field Tic-Tac-Toe

Posted
  1. Article
  2. Author
  3. Footnotes
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

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More