1
$\begingroup$

On a standard Connect-$4$ board ($7$ columns & $6$ rows), if two players take turns making moves by selecting an available column uniformly at random, what is the probability the game will end in a draw (i.e. all $42$ spots are filled and neither player has $4$-in-a-row anywhere in the board)?

I believe the probability of a draw is highly unlikely ($<1$%). There are just too many places on the board for $4$-in-a-row to occur. I've simulated a few games and none have made it to a draw.

Here is my way of getting a rough estimate. There are $69$ locations on the board to get $4$-in-a-row (counting horizontal, vertical, and diagonal runs of 4 cells). For each, the probability of all $4$ the same color is $\frac{1}{8}$ since the first piece can be either color, and the remaining $3$ each have probability $\frac{1}{2}$ to match the first. Thus there is a $\frac{7}{8}$ probability the four pieces are not the same color.

For the whole board, the probability of a draw is found by $(\frac{7}{8})^{69}\approx0.01$%

I know this isn't the exact answer, because I didn't consider factors such as there need to be an equal amount of both colors, the players take turns, each cell is part of multiple runs of $4$-in-a-row, etc. But I expect my estimate is pretty good. My question is how to calculate the exact probability of a draw, and also the probabilities of player $1$ and player $2$ winning (I expect going first gives player $1$ an advantage over player $2$)?

I know the total number of Connect-$4$ games can be found on OEIS and elsewhere online, but it isn't clear how many of those $4.5$ trillion games end in a draw.

$\endgroup$
2
  • $\begingroup$ Simulated a "few" games? How many is a "few"? $\endgroup$
    – Math1000
    Mar 5 '20 at 6:50
  • $\begingroup$ A couple hundred, though my programming skills are lacking. I just randomly populated a 6 × 7 grid in excel with 1s and 0s (21 of each) and looked for 4-in-a-row. There are problems with that method (e.g. arrangements that are impossible in regulation play can come up), but I think it's a fair way of seeing if my estimate is somewhat accurate. $\endgroup$ Mar 6 '20 at 5:21
1
$\begingroup$

here I have for you a simulation program that I worked on for this fascinating problem.

https://dotnetfiddle.net/5Ja1JS

All set up, you should be able to just click on RUN button to get output

you can run various numbers of trials. if you have or obtain C#.net you can run for large iterations.

$\endgroup$
1
  • $\begingroup$ That is awesome, thanks for sharing! I am kind of surprised the draw percentage is so high, hovering around 0.25%. $\endgroup$ Mar 8 '20 at 23:47

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.