Opinion
Last byte

# Open Field Tic-Tac-Toe

Posted

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?

### 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.