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$ 21 Answer
$\begingroup$Here I have for you a simulation program that I worked on for this fascinating problem.
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
