-4
$\begingroup$

"Attention everyone! It is the final game of the Connect 4 championship!

Billy and Sarah have played perfectly so far during this tournament, so in efforts to prevent Player 1 from being able to win, we are going to try something new!

These perfect players are going to be given an infinite playing board."

Now that you've listened to the announcement, it's time for the question.

So, assuming Billy goes first, who will win? Or will it be a tie?

$\endgroup$
  • $\begingroup$ Do you still "drop" your markers so that they fall to the lowest row possible in that column? Does this mean that infinite board has a bottom border but extends in all other directions. $\endgroup$ – xnor Feb 7 '15 at 20:46
  • $\begingroup$ @xnor Yes, it has infinite columns and infinite rows. $\endgroup$ – warspyking Feb 7 '15 at 21:08
  • 3
    $\begingroup$ That's not actually answering my questions. $\endgroup$ – xnor Feb 7 '15 at 21:38
  • 4
    $\begingroup$ In "Advances in Computer Games" (part of the "Lecture Notes in Computer Science" series), there is an article titled "Infinite Connect-Four Is Solved: Draw". See here: link.springer.com/chapter/10.1007%2F978-3-642-31866-5_18 $\endgroup$ – Julian Rosen Feb 8 '15 at 2:53
  • 5
    $\begingroup$ @ghosts_in_the_code I don't think that's a good reason to close the question. $\endgroup$ – mmking Jul 11 '15 at 15:36
1
$\begingroup$

@JulianRosen Your link refers to a semi-infinite board, where either the width or height is limited.

If neither is limited, I suppose the game can not be won against a perfect player, irrespective of who starts. It will continue endlessly.

I have not studied it in detail, but I know from personal experience that the only way to win (except controlling the Zugzwang) is to create a double trap, which can always be prevented.

$\endgroup$
  • $\begingroup$ Proof that in can always be prevented? $\endgroup$ – warspyking Feb 8 '15 at 19:49
  • 1
    $\begingroup$ @warspyking The best strategy for player 2 would be to just block all of player 1's traps. If player 1 still forces his way and gets one, player 2 can prevent can prevent him from getting one on the next slot (prevent a double trap). Suppose player 1 can get a double trap on the next as well as the next to next slot, it means player 2 has made a bad move in the past. $\endgroup$ – ghosts_in_the_code Feb 9 '15 at 15:28
  • $\begingroup$ Maybe a more detailed proof is required, but I'm quite sure of it being a draw for 2 perfect players. $\endgroup$ – ghosts_in_the_code Feb 9 '15 at 15:32
  • $\begingroup$ In regular connect 4 it's a win for player 1. How do you know exactly it's not a win on the infinite board? $\endgroup$ – warspyking May 3 '15 at 11:11
  • $\begingroup$ @warspyking There are 2 ways to win. One is creating a trap that forces a win quite before the end of the game. It is a single structure with 2 or sometimes even 3/4 traps (a trap is a 3-in-a-line). Two The other way of winning is controlling the Zugzwang. That is, almost at the end of the game, the opponent has no choices left, but to let you win. On an infinite board, there is no limitation of choices. So, you must win using method one. Method one can be blocked using perfect strategy on almost every sized board I've seen, so I guessed it should be true on an infinite board too. $\endgroup$ – ghosts_in_the_code May 4 '15 at 6:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.