4
$\begingroup$

My question: how to prove or disprove the following two conjectures?

Conjecture 1: (Gomoku large conjecture) there is no draw on infinite board for Gomoku with any initial opening with finite stones, if both players play optimally.

It has been widely believed among Gomoku players. But I have never seen researches on "something cannot draw" for $N$-in-a-row.
Maybe we can start from 3-in-a-row? (2-in-a-row is trivial for any opening)

Conjecture 2: (One famous open problem) $6$-in-a-row on infinite board is a draw.

[Edited May.16.2024] Today I found many researches on this, without solving even $7$-in-a-row. So proving it may be hopeless in a short time.


Definition of $\mathbf{M},\mathbf{N}, \mathbf{K}$-games and Gomoku ($\mathbf{K}=5$): relevant Wikipedia entry


The following statements are the reasons why I proposed these conjectures.

Background of Gomoku

Gomoku, or Five-in-a-row, is a popular board game worldwidely. Black and white alternatively play one stone. Who first connects five stones straight or diagonally wins.
It is widely known that black (the first player) has a winning strategy for Gomoku (Five in a row). So the professional players are using swap rules: these allow the forming of a "balanced opening", in which both players think neither black nor white has advantage. Then two players start the game from this opening.

Draw-rate vs board-size for Gomoku

For $15\times15$ boards started with balanced openings, the draw rate(the probability of draw) is about $50\%$ for top players or AIs. However, the draw rate drops exponentially when board size increases, $\sim 3\%$ for $19\times 19$ board and $\sim 0.1\%$ for $25\times 25$.
In addition, I found that more and more openings on bigger boards can be "almost-solved" by AI. For example, $F2$, $G2$, and $H2$ openings (openings with just one black stone initially) are three balanced openings for "swap after first move" rule on $15\times 15$ board. However, all of these have big advantages for black with $19\times 19$ board, means there is no balanced openings for "swap after first move" rule.
From this, I have the following conjecture:

Conjecture 1: there is no draw on infinite board for Gomoku, if both players play optimally and the number of the stones of the initial opening is finite.

Which means, either black or white has a winning strategy.

$6$ or more in a row, and the Critical Point of no-draw and draw

If there is no draw for $5$-in-a-row, then if we increase the difficulty of winning, there might be a critical point of no-draw and draw.
Simply increase to 6-in-a-row might be too much. It's very easy for human players to have a draw for 6-in-a-row. However it has not been proved yet. $8$-in-a-row has been proved to draw by Zetters, which is still very far from $6$.
Alphazero-like AI (Katago) can help finding the critical point. Some results for different rules for large boards are listed below

  • Gomoku/Renju: no draw.
  • $6$ in a row: very easy draw.
  • $5$ straight and $6$ diagonal/$6$ straight and $5$ diagonal: easy draw.
  • Gomoku on Hex board (equal to blocking one diagonal direction): easy draw
  • Caro(not win if two teriminals of the five stones are blocked): no draw.
  • Terminal-five(the last move must be the terminal of the five stones): no draw.
  • Terminal-five + Caro: near critical point.

Conjecture 2: $6$-in-a-row on infinite board is a draw

One extra question: where is the critical point of no-draw and draw?

$\endgroup$
10
  • 2
    $\begingroup$ It's unclear what kind of answer you're expecting. You did a lengthy summary of the state of the art, from which it is obvious that it is not known for which $n$ optimal play results in a draw, and MO is not a place to formulate conjectures. The question “for which values of $n$ is it mathematically proven that optimal play results in a draw, resp. a win for some player?” is a valid one, but if so, you had better track your “citation needed” about $n=8$: where did you get this information from? $\endgroup$
    – Gro-Tsen
    May 15 at 11:48
  • 2
    $\begingroup$ Also, since you are posting this to a math forum, one would expect a mathematically precise definition of the game. Not that I expect major difficulties, but it should at least be written in such a way that makes it clear whether it is played on $\mathbb{N}^2$ or $\mathbb{Z}^2$, what “in a row” means, whether the game ends in a draw as soon as $\omega$ turns have been plaid or whether it continues until the entire board is full — this sort of things. And you didn't define “swap rules” so why did you bring them up? $\endgroup$
    – Gro-Tsen
    May 15 at 11:52
  • $\begingroup$ Thanks for your comments. The answer I need is how to prove these conjectures. I will explain these questions more mathematically. $\endgroup$
    – hzy
    May 15 at 15:05
  • $\begingroup$ Have you read either Winning Ways or the various Games of No Chance collections? They're perhaps the best starting point for this. AFAIK you may be able to show that 5-in-a-row is a win on a sufficiently large board 'conceptually', but I would expect that to be well explored already and (given the lack of results) to not readily yield to any techniques that we could offer you. Finding the smallest board on which it's a win seems almost guaranteed to be a product of long computer exploration if at all. $\endgroup$ May 15 at 18:28
  • 2
    $\begingroup$ More broadly, as Gro-Tsen noted, 'how do I prove these conjectures that have been open for multiple decades' is not likely to garner much in the way of useful information. You could ask 'what strategies have been used to show that similar games are draws?', and TBH I suspect the first answer would be something along the lines of 'Go look at Winning Ways.' $\endgroup$ May 15 at 18:30

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.