How can be it proved that tic-tac-toe on an infinite grid (winning with $12$ in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)?

There is a hint: to use a "magic square of $4\times4$" and a "tessellation".

  • $\begingroup$ Tic-tae-toe on an infinite grid can never end in a tie. Presumably you mean that neither player has a winning strategy. $\endgroup$ – Peter Taylor Apr 15 '14 at 10:39
  • $\begingroup$ @PeterTaylor I define tie as "not making 12 in a row, a column or a diagonal", so the infinite play is a tie. You are right about the inappropriateness of the verb "end", though. $\endgroup$ – John Smith Apr 15 '14 at 18:42
  • 2
    $\begingroup$ There's a proof in one of the later volumes of Winning Ways that the 9-in-a-row game is a draw on an infinite board. A fortiori the 12-in-a-row game is too. $\endgroup$ – MJD Aug 26 '14 at 14:10
  • $\begingroup$ @PeterTaylor According to the rules, the game ends after $\omega$ moves if nobody has made $12$ in a row. One could consider a variant, where play continues into the transfinite as long as there are any unoccupied points, but this is not so popular. $\endgroup$ – bof Apr 19 '15 at 12:25
  • 1
    $\begingroup$ @GarethRees Yes, I know. I remarked on that fact in my comment to MJD, and again in my reply to your comment, by bolding "If". The only reason for my comment to MJD was that he did not mention the pairing strategy but only reported that "the 9-in-a-row game is a draw", which I thought could be misleading. $\endgroup$ – bof Apr 28 '15 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.