-3
$\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?

Improve this question
$\endgroup$
9
  • $\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, 2015 at 20:46
  • $\begingroup$ @xnor Yes, it has infinite columns and infinite rows. $\endgroup$
    – warspyking
    Feb 7, 2015 at 21:08
  • 3
    $\begingroup$ That's not actually answering my questions. $\endgroup$
    – xnor
    Feb 7, 2015 at 21:38
  • 5
    $\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, 2015 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, 2015 at 15:36

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Proof that in can always be prevented? $\endgroup$
    – warspyking
    Feb 8, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 6:21

Your Answer

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

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