TLDR: A new research paper by Markus Böck presents a strong solution for the standard 7×6 ConnectFour game, generating an 89.6 GB look-up table in 47 hours on consumer-grade hardware. This was achieved by revisiting symbolic search methods using Binary Decision Diagrams (BDDs) with an optimized state encoding, overcoming previous memory limitations and making a complete win-draw-loss evaluation feasible.
The classic game of ConnectFour, where players drop colored discs to form a line of four, has long fascinated mathematicians and computer scientists. While the game has been mathematically “solved” in various ways, creating a comprehensive look-up table that details the win, draw, or loss outcome for every possible game position was considered an insurmountable challenge, especially for the standard 7×6 board size, due to the immense computational and memory requirements.
However, a recent breakthrough by Markus Böck from TU Wien, Vienna, Austria, has shattered this belief. In a paper titled “Strongly Solving 7 × 6 ConnectFour on Consumer Grade Hardware,” Böck demonstrates how a complete win-draw-loss evaluation for the 7×6 ConnectFour board can be achieved on readily available computer hardware. This significant achievement involved revisiting and refining a method known as symbolic search, which utilizes Binary Decision Diagrams (BDDs).
The Challenge of Solving ConnectFour
ConnectFour is a two-player game played on a grid, typically 7 columns by 6 rows. Players take turns dropping discs into columns, aiming to get four of their own discs in a row, either horizontally, vertically, or diagonally. The game can end in a win for one player or a draw if the board fills up without a winner.
Previous attempts to solve ConnectFour included explicit search methods, which traverse one game state at a time, and earlier symbolic search methods using BDDs. While effective for smaller board sizes, these methods faced exponential scaling issues with memory, making the 7×6 board intractable. For instance, prior research estimated it would take 93 days on a 192 GB machine to solve the standard board using a hybrid approach.
Böck’s Innovative Approach
Markus Böck’s work builds upon the foundation of symbolic search and Binary Decision Diagrams. BDDs are a data structure used to represent complex Boolean functions, which in this context, encode sets of game states. Instead of analyzing one game position at a time, symbolic search processes entire sets of positions simultaneously, making it highly efficient for certain problems.
The key to Böck’s success lies in a crucial improvement: a different, more compressed state encoding for the ConnectFour board within the BDDs. This new encoding significantly reduces the number of nodes required to represent game positions, thereby drastically cutting down memory consumption. While previous methods struggled with memory, this optimized encoding allowed the solution to fit within consumer-grade hardware limits.
Impressive Results on Standard Hardware
Using a single CPU core of an AMD Ryzen 5950x processor and 128 GB of main memory – hardware commonly found in high-end consumer machines – Böck’s efficient implementation was able to produce an 89.6 GB look-up table for the standard 7×6 ConnectFour board. This monumental task was completed in just 47 hours. The memory constraint was a critical factor, as the standard encoding would not have been feasible.
Beyond just determining win, draw, or loss for every position, the research also integrated an alpha-beta search algorithm. This allows the system to not only identify the outcome but also to find the optimal move that leads to the fastest win or the slowest possible loss. This capability was used to generate an “opening book” by evaluating over 184,000 8-ply positions, a process that took about 5 hours using 16 cores.
The research also successfully reproduced and confirmed unique position counts for various board configurations, including the massive 7×7 game, which was found to have over 161 trillion unique positions.
Also Read:
- Smarter AI Decisions: New Methods for Dynamic Abstraction in Monte Carlo Tree Search
- Unlocking Global Optimization: A New GPU-Powered Search Method for Complex Functions
Impact and Accessibility
This work represents a significant milestone in game AI and computational search. By demonstrating that a strong solution for 7×6 ConnectFour is achievable on moderate hardware, it opens new avenues for research and practical applications. The entire source code for reproducing these results and querying the win-draw-loss table is openly available, fostering further exploration and development in the field. You can find more details in the research paper itself: Strongly Solving 7 × 6 ConnectFour on Consumer Grade Hardware.
In conclusion, Markus Böck’s research has not only provided the first look-up table-like strong solution for the standard 7×6 ConnectFour board but has also pushed the boundaries of what’s possible with symbolic search on accessible hardware, proving that long-held beliefs about computational infeasibility can be overcome with clever algorithmic improvements.
