Web UI: https://christophesteininger.github.io/c4

Connect 4 on a 7x6 board was first solved in 1988 independently by James D. Allen and Victor Allis. John Tromp solved the game for all board sizes where width + height $\leq$ 15 in 2006, and solved the 8x8 case in 2015.

I've extended these results by solving the game on all board sizes where $w$ + $h$ = 16, as well as some board sizes where $w$ + $h$ $\geq$ 17.

Results

Outcome

The table below shows which player will win of a game of Connect 4 if both players play perfectly on different board sizes. 1^st means the first player to move can guarantee a win, while 2^nd means the second player to move can guarantee a win. On some board sizes, neither player will be able to force a win, in which case the outcome will be a draw.

Width → Height ↓	4	5	6	7	8	9	10	11	12
4	Draw	Draw	2nd	Draw	2nd	2nd	2nd	2nd	2nd
5	Draw	Draw	Draw	Draw	1st	1st	1st	1st
6	Draw	Draw	2nd	1st	2nd	2nd	1st
7	Draw	Draw	1st	Draw	1st	1st
8	Draw	Draw	2nd	1st	2nd
9	Draw	Draw	1st	Draw	1st
10	Draw	Draw	2nd	1st
11	Draw	Draw	1st
12	Draw	Draw	2nd
13	Draw	Draw

Last Move

The table below shows the move on which the game will end if both players are perfect. An entry such as "53" for the 8x7 board means the game will end on the 53^rd move. With the results from the above table, this means the 1^st player can always force a win on move #53 if the second player plays perfectly. If the second player in an 8x7 game is not perfect, then the first player can always force a win before move #53.

Width → Height ↓	4	5	6	7	8	9	10	11	12
4	16	20	24	28	32	36	40	44	48
5	20	25	30	35	39	41	47	51
6	24	30	36	41	48	52	59
7	28	35	41	49	53	55
8	32	40	48	55	62
9	36	45	53	63
10	40	50	60	69
11	44	55	63
12	48	60	72
13	52	65

Building

Build using CMake. Run these commands in the root dir to compile and solve Connect 4 on the standard 7x6 board from scratch (i.e. no precomputed data). This will only take a few seconds.

$ cmake --preset optimise
$ cmake --build --preset optimise
$ out/optimise/c4

On Windows, the repo can be imported as a Visual Studio CMake project.

Adjust the values in src/solver/settings.h then recompile to set the size of the board, number of threads, memory usage, and more. Increasing number of threads and memory usage to the maximum available on your machine will reduce solve time significantly.

Increasing the board size will exponentially increase the difficulty of the solve, so solve times will increase quickly if the board size is changed. For example, on my machine solving the 7x6 board takes 3 seconds while the 7x9 takes ~16 hours.

Compiling will generate five executables:

1. c4: Solves a single position then prints the result and search statistics. Used to generate the tables above.
2. play: Interactive program to play against the solver.
3. test: Runs unit tests, then tests and benchmarks the solver using positions with independently verified scores.
4. book: Generates an opening book by solving all positions up to a set depth.
5. random: Generates random games for testing and benchmarking.

Credits

This solver expands on the work of two others:

• John Tromp
• Pascal Pons
• Guido Zuidhof - COOP and COEP workaround for GitHub pages.