Talk:m,n,k-game

Drawing-strategy scalability

I think there's a hole in the proof that a drawing strategy on a larger board can be converted into a drawing strategy on a smaller board. There can exist a sequence of moves which ends in a win for the second player on move N on the larger board, but not on the smaller board because the winning move lies outside the board. Then the first player can win the game on move N+1. In fact I doubt if the theorem is true at all. Arvindn 21:37, 17 Oct 2004 (UTC)

No, the proof is correct. Your counterexample assumes the second player has a winning strategy. But it is proven earlier in the article that the second player can never have a winning strategy at all. vslashg 23:01, 18 Oct 2004 (UTC)

No, I didn't assume any such thing. Let me be more verbose. Suppose the second player plays according to his drawing strategy. Then the first player plays *suboptimally*. That is, her play would be suboptimal if the game were being played on the larger board. The second player continues following the optimal strategy, and expects to win on move N. However, the winning move turns out to lie outside the smaller board, so the second player cannot finish the game on move N, and the first player ends up winning on move N+1. Have I made myself clear now? Arvindn 23:55, 18 Oct 2004 (UTC)

OK, its been a while, no response to above; I've mailed the author (Uiterwijk) asking for the proof; gave essentially the same flawed proof as mentioned above; I replied pointing out about the bug, again no response; so I'm assuming that the proof is wrong and removing it and all consequent information from the article. Arvindn 03:15, 19 Nov 2004 (UTC)

Agreed -- I've never seen a valid proof that a draw holds when the board size is decreased and by similar logic, we can't say that a win holds on a larger board (the new space might yield a winning play for player 2, changing p1's strategy, and giving a drawn result). The line in the article asserting this should be removed. Also, references should be given for what we know to be true, right? Mikebell 01:21, 14 November 2005 (UTC)

Right. Somebody keeps putting it back in, and I keep removing it. Almost all the stuff that's in the article right now, though, deals with specific board sizes and we can trust that whoever proved them got their computer programming right :) Arvindn 05:36, 22 December 2005 (UTC)

I agree that the proof didn't quite hold up as it was written—I think that it confused the ideas of "the second player can always draw the game" and "the second player can always either draw the game or win." However, I think that the following result (with a strengthened hypothesis) is correct: If there is a strategy for a given m,n,k for Player 2 that can always draw the game, then Player 2 can always draw or win on a smaller board by mimicking the larger board's strategy when possible, and making random plays when he can't mimic it. (Since the pairing strategy for k ≥ 9 does guarantee a draw (it never results in a Player 2 win), then 9-in-a-row is drawn on any board size if both players play optimally.) I don't know enough about the strategies on other board sizes to know if this carries over for board sizes other than k ≥ 9 or not. Thoughts? —Babcockd 17:04, 11 March 2006 (UTC)

But what you have proven here is exactly what you want (by basically the same argument). If player 2 can draw on a board of size (m,n)>(M,N), then he can also draw on a board of size (M,N). This is true because he simply pretends he is playing on the larger board. Any move he would need to make on the larger board will not be needed to block anything (because player 1 can't play outside of the board), so replacing these with random moves yields a draw on a board of size (M,N). This means, effectively, that draw on large - > draw on small. Because the game (given perfect play) must end either in win for player 1 or draw, the contrapositive of this is that player 1 will win on a large board if he wins on a small one. I'm not sure I understand the original objection to this statement, but hopefully this has clarified it. In any case I'll be writing it into the article again. — Preceding unsigned comment added by 83.109.9.165 (talk) 02:38, 30 July 2011 (UTC)

Now has anyone found a Proof for this problem? The Problem mentioned by Arvindn does not seem trivial to me. A citation or a proof would be very helpful. The person who wrote the last Comment(unsigned) didn't seem to get the Point. ---19:39, 21. January 2012(UTC) — Preceding unsigned comment added by 84.73.55.171 (talk)

What about the assertion

• k ≥ 8 is a draw: it has been shown that when k is at least 8, the second player can force a draw even on an infinite board, and hence on any finite board. This means that when the board is infinite the game will go on forever with perfect play, whereas if it is finite the game will end in a tie. It is not known if the second player can force a draw when k is 6 or 7.

? Isn't the fourth clause of the first sentence subject to the same logic? —Simetrical (talk) 02:42, 26 December 2005 (UTC)

Excellent question, I've been thinking about that myself. I initially thought that that assertion is true, but now I realize the same flaw exists in a strategy transfer argument in this case too.

For k=9, a draw via pairings has been shown: the second player pairs the squares of the board in a certain way and always plays in the same pair as the first player. This is a strategy in which the second player doesn't try to win, so it transfers to any smaller board.

But you are totally right about k=8. Arvindn 04:28, 26 December 2005 (UTC)

A general k=8 strategy wouldn't necessarily work on a finite board, but the Zetters strategy does because it only impacts player 1's strategy by picking squares in which she may not play. This means that shrinking the board helps it the same way it does for pairing strategies.

In fact, a more general statement that captures Zetters and Hales-Jewitt would be that any drawing strategy which still holds in a tic-tac-toe where player-2 can never win (that is, a game where player 2's winning lines are ignored) will be a valid drawing strategy in normal tic-tac-toe on any sub-board. Mikebell 20:02, 6 February 2006 (UTC)

I just removed "(k,k,k) is a draw if and only if k ≥ 2 (pairing strategies for k ≥ 6, special cases otherwise)". It seems highly plausible that replacing the first "≥" with ">" would make that true, hopefully someone can show that. JumpDiscont (talk) 05:21, 25 October 2012 (UTC)

Strategy Stealing Argument

Check [1] for a discussion on if the strategy stealing argument is valid. 70.111.251.203 13:43, 9 February 2006 (UTC)

Problem with k=3

The article states:

• k = 3 is a draw for (3,3,3) (see Tic-tac-toe) and a win otherwise if m > 3 and n > 3. If m ≤ 3 or n ≤ 3, the game is a draw.

I think it should state that it is a win if m > 3 OR n > 3. Also, if m ≤ 3 AND n ≤ 3, the game is a draw. For example, (3,4,3) and (4,3,3) are both wins.

Yeah, this was obviously a mistake. —Preceding unsigned comment added by 129.177.122.124 (talk) 14:26, 18 October 2007 (UTC)

I don't think this is right; in a (1,4,3) game it's obviously impossible to win. Maybe it should say if m≥3,n>3 or vice versa it's a win? CHL (talk) 08:35, 3 May 2008 (UTC)

General result?

If k<m and k<n, there is a draw. Should this be added to the general results section? —Preceding unsigned comment added by 141.156.40.94 (talk) 17:09, 6 June 2009 (UTC)

Pairings to draw (9,6,6) and (7,7,6)

0A	3B	----	7A	7B	7A	6B	1B	2A
0B	0A	3B	5C	5B	5B	1B	2A	----
0B	1A	4C	4A	4A	6A	0C	2C	7C
4B	4B	4C	5C	----	3C	3C	2C	7C
----	6C	6B	2B	2B	6A	5A	1C	----
6C	1A	----	3A	7B	3A	0C	5A	1C

----	8A	----	1A	1A	8B	----
9A	5A	4A	7B	6A	7B	9B
0B	5A	3A	7A	7A	4B	0A
0B	2A	4A	----	6A	2A	0A
----	5B	2B	1B	3A	5B	----
8B	2B	6B	1B	6B	4B	8A
----	9B	----	3B	3B	9A	----

JumpDiscont (talk) 17:23, 20 January 2017 (UTC)

m×n

What does "m×n" that mean????? Readers don't know Anna Frodesiak (talk) 11:27, 20 July 2017 (UTC)

weak (m,n,k) game

This is defined as 'k-in-a-row by the second player does not end the game with a second player win.' What does that mean? What's the winning condition of this game? Surely it doesn't mean "no matter how bad the first player plays, the second player is never declared a winner". 2001:981:4B0C:1:DAA2:5EFF:FE8E:C8D8 (talk) 19:34, 11 September 2017 (UTC)

Actually it does, the second player is playing to avoid a loss. If it were a real game you would probably say the second player was the winner if the the first player did not get n-in-a-row, but weak (m,n,k) games are mainly a mathematical tool to analyze normal (m,n,k) games (themselves mostly of mathematical interest). The notion of Maker-Breaker games is very similar. MathHisSci (talk) 09:51, 17 September 2017 (UTC)

Two-dimensional corollaries of result stated in section "Multidimensional variant"

Consider the case of k-in-a-row on a 2-dimensional hypercube with all edges having length k (more commonly known as a k-by-k square). Then the Hales and Jewett result quoted from the Berlekamp, Conway, Guy book in the aforementioned section of the article applies, with n=2: that is, the game is a draw if k is odd and k ≥ 3^2-1 = 8 or if k is even and k ≥ 2^(2+1)-2 = 6. We already have in the Wikipedia article the statement that (m,n,k) is a draw for k≥9 for any m,n, which is stronger than the "k is odd" case already, but the second case also gives us that both (6,6,6) and (8,8,8) are draws, neither of which is implied by any of the statements in the "General results" or "Specific results" sections as of the writing of this comment. If anyone is familiar with either the BCG book in the references or the apparent Hales and Jewett paper, can they please confirm that the result is indeed proven for n=2? If not, this condition should be mentioned where the result is stated. If so, it seems that (6,6,6) and (8,8,8) need to be added to the "Specific results" section as draws. Note that in the case n=1, i.e. a (k,1,k) game, the HJ result, that this is a draw for all k≥2, trivially holds. Adam Dent (talk) 19:18, 13 July 2018 (UTC)

(6,6,6) being a draw is implied by "(9,6,6) and (7,7,6) are both draws via pairings.", and the statement I just quoted was in the "Specific results" section as of the writing of your comment. ​ I'm not familiar with the sources you mentioned, although I might get around to finding a pairing draw against 8-in-a-row for boards at least as large as 8x8. ​ ​ ​ JumpDiscont (talk) 13:17, 16 April 2019 (UTC)