Index Home gPress Hyperlinks About This Site Preferences Register Login

Categories


Computing
(posts: 9)

Design
(posts: 2)

English
(posts: 1)

Games
(posts: 4)

gPress
(posts: 3)

History
(posts: 2)

Logic
(posts: 5)

My Works
(posts: 7)

Puzzles
(posts: 1)

Releases
(posts: 8)

Theology
(posts: 3)

Updates
(posts: 6)

Writing
(posts: 2)

n-in-a-row Games, Part III

n-in-a-row Games, Part II

n-in-a-row Games, Part I

Some New Works

sort:

Post

n-in-a-row Games, Part II

Considering the ubiquity of regular Tic-Tac-Toe, it is curious that few have thought to take their game to the next level. In this article, we will explore the next step in n-in-a-row play, larger boards and larger row requirements.

It is evident after a brief look that an expanded Tic-Tac-Toe game is going to require more than three-in-a-row. For a thought experiment, consider the play of Tic-Tac-Toe+1. This game is exactly like Tic-Tac-Toe, except that an extra square is added onto the edge of the board: next to any of the existing squares, either horizontally or diagonally.

If the new square is anywhere but to the diagonal of a corner square, the game becomes a forced win for X:

New Square at a4, Game 1
1. a3 b2
2. a2#


New Square at a4, Game 2
1. a3 a2
2. b2+ c1
3. b3#


New Square at b4, Game 1
1. b2 c3
2. b3#


New Square at b4, Game 2
1. b2 b3
2. a3+ c3
3. a1#


By the same measure, a greater row requirement can lead to a game that is too easily drawn, even by the standards of a game like Tic-Tac-Toe. A brief playthrough of 4-in-a-row on a 4x4 board should illustrate the point.


A Bad, Boring 4x4 Game
1. a1 c3
2. b1 b3
3. c1+ d1
4. a2 d2
5. a3+ a4+
6. c2 d4+ 7. d3 c4+
8. b4 and a draw

The best size for a board tends to be the largest one that is not proven to be a win for the first player. For 4-in-a-row games, the only suitable symmetrical board is 5x5 [1].


Given a 5x5 board and 4r, what does the opening play look like?

Although X may have motivation to try different options in Tic-Tac-Toe, in this game, there is no reason to play anything but the center. This gives him the most room to expand his attack.

At this point, O must move in a square diagonally adjacent to the center. Anything else is a forced win for X.


Edge Defense Refutation
1. c3 b3
2. b4 d2
3. d4 c4
4. b2#

abcde
5
4XOX
3OX
2XO
1

Time and space don't presently allow an exhaustive listing of X's options after a corner defense, but the strategy is focused on getting one of the possible combinations which lead to 4r in short order, which include:

  • 1 three-in-a-row, with no pieces blocking either end.
  • 2 simultaneous three-in-a-rows, either or both of which may be blocked on one end.
  • 2 simultaneous two-in-a-rows, with no pieces blocking either end.

A solid strategy for this game is to play the center of the board as a regular game of Tic-Tac-Toe. If you keep this foundation in order, the threats at the edges are easy to prevent. The biggest problem a player is likely to run into is the desire to 'cheat' by playing a move oriented towards getting a winning threat when they should be focused on defense.

A Sample 5x5 Game
1. c3 b2
2. b4 d2
3. e2 d4?!
(Complicates the game, but probably for the worse.)
4. d3 c2!
Saves the draw.
5. a2 b3
6. a3 a4
7. d1 e3
8. c4 b5
9. c5 and draw

Another Sample 5x5 Game
1. c3 b2
2. b4 d2
3. e2 c2
4. a2 d3
5. d4 e4
6. b1 a4
7. b3 d5 and draw

It is occasionally useful, at least psychologically, to make a move that blocks only one end of a row, when you have the option to do otherwise. This seems to be halfway between playing a solid defensive move and a 'cheat'. Whether it will prove to be sound or unsound depends on the details of the position and whether your opponent keeps track of what you're up to, but I suspect that it is slightly incorrect and this habit can get you punished in similar games on larger boards.


A game like 5r Tic-Tac-Toe is known and appreciated around the world. It has a variety of names but is best known as the Japanese "Gomoku".

At sufficiently large board sizes, without or sometimes even with artificial restrictions, Gomoku is known to be a forced win for the first mover; this is true on boards as small as 15x15. [2] It appears to be unknown at present what the largest size is that is proven to be a draw.

I've played 5r games at 7x7 and 9x9 sizes. My expectation is that the latter is drawn, but this hasn't yet been proven. Play allows no room for error.

I've never focused my attention on this game in the way that I might have, for two reasons.

Firstly, the fact that it already has many expert and professional players has a chilling factor on my level of interest. I admit being opportunistic in this respect. I would rather try to break ground in a new land and be first-rate at something than to be second or third-rate in a sprawling metropolis. At any rate, I'm not sure how much value I can offer writing about a game that has already been discussed and solved and revised and re-solved multiple times (the previous content in these articles notwithstanding).

Secondly, I discovered Ultimate Tic-Tac-Toe shortly after my first 5r series, and my enthusiasm for that game further dampened my interest in doing an in-depth study of this one. It is therefore appropriate that Ultimate (or, as we've taken to calling it, ULT) should be the subject of the next article in this series.

[1] There are larger boards which are said to lead to interesting games. The key phrase here is "symmetrical board". This vintage site is informative about that, and such variants generally: "Generalized Tic-tac-toe", by Wei Ji Ma
[2] The proof text is Searching for Solutions in Games and Artificial Intelligence, a 1994 thesis by Louis Victor Allis.