Log in

No account? Create an account
Tic tac toe for adults - the emperor has no clothes! - Arvind Narayanan's journal [entries|archive|friends|userinfo]

Tic tac toe for adults - the emperor has no clothes! [Dec. 22nd, 2005|12:45 pm]
Arvind Narayanan
[Tags|, ]

Most reasonably bright kids tire quickly of tic-tac-toe, but there is a version that is far more complicated: the (m,n,k)-game is played on a m x n rectangular board. Two players alternate in placing stones of opposite color; the first to get k stones in a row (vertically, horizontally, or diagonally) wins. Thus, tic tac toe is the (3,3,3)-game.

There are a gazillion scientific papers addressing the question of who wins the (m,n,k)-game for different values or groups of values of m,n and k. It is well known that the second player cannot win; this is called the strategy stealing argument and is used all over the place in combinatorial game theory. (If the second player has a winning strategy, then the first player can make an arbitrary first move and then mirror the second player's strategy.) So the game is either a first player win or a draw.

There is one other fact that these papers will assume is known to the reader or will mention in passing: if the (m,n,k)-game is a (first player) win, then for every m' ≥ m and n' ≥ n, the (m',n',k)-game is also a win. Which is pretty obvious - whatever winning strategy the first player has on the smaller board also carries over to the larger board. Right?


Where the above argument falls down is that if the first player blindly tries to carry over the original strategy to the larger board, then the second player may have a win, said win having been impossible on the smaller board because the winning move would not have been within bounds.

So is there some other way to transfer a winning strategy onto a larger board? I haven't been able to find any such way, and as for the people who claimed the extension to be obvious, they have no answer when presented with the counterargument.

Even worse, some authors (example) also assume that if the (m,n,k)-game is a win, then so is the (m,n,k')-game for k' < k. As far as I can see, there is no known proof for this assertion either. (I will call the first statement conjecture 1 and this one conjecture 2.)

The whole situation shows the scientific peer review process at its worst. How did legions of presumably very smart researchers miss these obvious holes in the argument? Someone must have originally made the mistake, and everyone else assumed that the first guy did his homework. I'm sure some people noticed the hole, but were too timid to speak out, for fear that they might have missed something and look like a moron. It takes a child, an outsider, to point out that the emperor has no clothes.

Notice that I am not saying that either conjecture is false - I'm just saying that the commonly assumed "proofs" are flawed. In fact, I think it highly likely that both conjectures are true. It is highly improbable that every single first player winning strategy can be defeated in the manner outlined above, although it is theoretically possible.

Further, in the case of conjecture 1, we can prove a related but weaker statement: if the first player has a winning strategy in the (∞, ∞, k)-game with the property that there exists a mxn rectangle such that no matter how the second player plays, the first player never makes a move outside this rectangle, then the (m',n',k)-game is a win for all m' ≥ m and n' ≥ n. Here the strategy transfer goes through with no problem.

Apart from conjectures 1 and 2, I believe there are two more questions that remain open:

Conjecture 3: if the (∞, ∞, k)-game is a draw, then is every (m,n,k)-game also necessarily a draw?

Conjecture 4: if the (∞, ∞, k)-game is a win, is the (m,n,k)-game is a win for all sufficiently large m and n?

I'm still researching the existing literature. Maybe I'll find out that everything I said is crap :)

From: numnesofthbeast
2005-12-22 04:41 pm (UTC)

These statements look so obvious, yet in every case, when I ask myself how to actually prove the thing, I draw a blank.

It would be so much simpler if the game were asymmetric, in that only the first player was allowed to win, and the job of the second player were merely to prevent the first player from winning. Then, surely, all those 'obvious' results really would be obvious (except maybe conjecture 4).

Perhaps the authors you mention are confusing that asymmetric game with the real thing.
(Reply) (Thread)
[User Picture]From: arvindn
2005-12-22 11:07 pm (UTC)
I think conjecture 3 is true via a direct strategy transfer - the second player plays exactly as they would have on an infinite board, and if that strategy calls for making a move outside the smaller board, they make an arbitrary move inside the board. An extra move can never hurt.

You are totally right about the asymmetric game, all except conjecture 4 appear to follow. However I highly doubt that the papers were written with this game in mind. Anyways, reasoning this way, it would intuitively appear that with the regular game, conjecture 4 should be *harder* than the other ones. Yet I believe it is the other way round! The infinite gives us a lot of maneuvering room. I've made some progress toward proving 4, whereas I have no clue how to prove 1 and 2. If I get a proof or make substantial progress I will post it.
(Reply) (Parent) (Thread)
[User Picture]From: arvindn
2005-12-25 08:21 pm (UTC)
OK I was wrong above about conj. 3, sorry. The same flaw as in the supposed proof of conjecture 1 holds for my argument above as well.
(Reply) (Parent) (Thread)