From Tic-Tac-Toe to Four In a Row

Logic Level 3

In the game of Tic-Tac-Toe , the goal is to line up 3 pieces in a row horizontally, vertically or diagonally on $3 \times 3$ board.

If suppose the goal is to line up 4 pieces in a row on a $19 \times 19$ board, assuming both players play optimally, what can be said about their winning chance?

Image Credit: Board Game Arena.

A player who starts second will win A player who starts first will win The winning chances can't be determined

1 solution

Michael Mendrin
Jan 16, 2017

This is the 19,19,4-game, a special case of a m,n,k-game . So far, the case of a forced win by the player who starts first is still only "weakly solved". This is a particularly difficult problem, and I wonder if anyone can cite a paper showing this to be a "solved" game.

Freestyle Gomoku is a 19,19,5 game, and is not known to be "solved", i.e., a win or a draw can be forced by either player.

@Michael Huang The strategy-stealing argument only tells us that either first player will win, or that the game would be a draw.

Is there any reason why 19, 19, 4 must lead to a win?

Calvin Lin Staff - 4 years, 4 months ago

I've been playing Gomoku and connecting games since my childhood, so I thought asking this question is the great idea. This seems to me like a computer science question, even though I thought it may be a logic problem. Here is the "Laymen's language" idea I am having (please excuse the lack of rigor):

Consider a $19 \times 19$ board. As the specific results states, if the game is played on $6 \times 5$ board with 4 pieces lined up, then the first player guarantees a win. To approach this proof, visualize how a $6 \times 5$ rectangle can be positioned inside $19 \times 19$ rectangle without leaving any portion outside. If the players were to play within the rectangle, then it is like playing $6 \times 5$ board instead of $19 \times 19$ board. Then, the idea is close to "If the small fitting dimension guarantees the win, then the greater dimension guarantees the win". Since there is highest chance that the pieces are positioned adjacent/nearby each other for optimal play, it wouldn't be necessary to test out the large dimension case.

I believe that in Gomoku, the 5-In-A-Row, the first player can win if both players were to play $15 \times 15$ board game, which was proven by Allis. However, I couldn't find the strongest proof for this one.

EDIT: As the fun time to spend on learning about combinatorial games, here are some articles/papers I believe to be interesting:

Connect6
Games solved: Now and in the future
The advantage of the initiative : I believe this paper is what Mendrin is looking for.

By the way, let me know how you think about the articles.

Michael Huang - 4 years, 4 months ago

Kudos for having found that necessary citation to save your problem, your answer seems correct. It does say that it is "known" that for a 19,19,4 game, the first player can force a win. What's surprising to me is that in a 19,19,5 game, the freestyle Gomoku game, the first player can also force a win! Yes, "The Advantage of the Initiative" is a pretty engrossing read.

I like the observation made in "The Advantage of the Initiative" that given a value for k, if given a sufficiently large board, the first player can eventually force a win, and the results from analyses on smaller games bears out this trend. It's a pretty persuasive argument, although we know that mathematical exactitude demands more than mere persuasion.

At least we've also established that this is very difficult problem, hardly anything people can solve by sitting down with a pencil and paper.

Michael Mendrin - 4 years, 4 months ago

Thanks! I'd read those articles on my way home.

The "smaller board win implies larger board win" argument is the one that I'm most concerned about. It is not immediately apparent why this is "easy to show" (as stated in the article), though I agree that it should be intuitively true.

Calvin Lin Staff - 4 years, 4 months ago

@Calvin Lin – It is an interesting question. I can see a situation in a winning strategy for a smaller board where the second player being up against an edge keeps him from finishing a row of 4, or an open 3. Then the smaller board gives a forced win for the first player, where a larger board might not.

In practice, this does not seem to be the case here, but the argument is not as simple as it first appears.

Steven Perkins - 4 years, 4 months ago

On the first 3 moves first player build a triangle. Then he extends one of its sides and builds a fork. Second player cannot block all 3 sides.

Hasmik Garyaka - 2 years, 4 months ago

From Tic-Tac-Toe to Four In a Row

Image Credit: Board Game Arena.

1 solution

0 pending reports