In particular, if the first player opens by playing in the centre column then this guarantees victory - in fact it is the only opening move that does. This result was first discovered by Victor Allis and James Allen in 1988.
How does one determine the best move to make from an arbitrary position? At one end of the spectrum, a purely computation approach without precomputation is practical on modern hardware. At the other end, you can download a 15TB table of all positions and read out the value of each possible move, at the cost of table lookups.
Between these two poles is the territory of time-memory trade-offs, and any compromise approach has the potential to be useful or interesting.
A strong solution for Connect 4 is one that provides optimal play from any valid position. By contrast, this project is a weak solution that provides a guaranteed path to victory for the first player, but only from the start - i.e. not from an arbitrary position. It is inspired by (and would not exist without) the corresponding project by 2swap.
With enough of these it is possible to produce a solution graph such that starting from an empty board, any sequence of moves by the second (losing) player is guaranteed to reach a leaf node corresponding to one of these tables.
The 2swap strategies work by providing a list of rules in decreasing priority. On each move the first player chooses the first valid rule on the list; this guarantees eventual victory. The prioritised list of rules is:
Tables must be constructed such that this list of rules is well-defined, e.g. there can never be two playable '!' or '|' squares at the same time. The exception is the '@' ('miai') square: if two or more of these are playable then the rule is skipped but it does not make the table badly-defined.
These rules are informed by 2swap's experience as a Connect 4 player. They are designed to produce simple, easy-to-memorise strategy tables. The result is a complete graph that guarantees victory from an empty board.
Here is a representative strategy node:
Orange is to play. No winning move is available and there is no need to block a winning move by green. The available moves with numbers (highlighted orange) are 2, 2, 4, 3, 5. We discard '2' as it occurs multiply; the least of the remaining moves is the '3', so we play in that cell.
This language is more expressive than (and indeed contains) the 2swap language in the sense that any 'steady state' board can be reduced to the new format by unwrapping the claimodd / claimeven squares ' ' and '|' into an alternating sequence of numerical and blank squares. In this case above, the claimeven and claimodd patterns are clearly visible; note we have the flexibility to construct them from any number.
The new method is practically more powerful due to a combination of
A further advantage of having a simple numerical system is that it possible to manipulate strategies. For instance, adding 1 to the value of each numerical square does not affect the strategy, but allows subsequent insertion of a number '0' that may lead to a strategy with more graph coverage. I used this extensively when constructing the solution graph.
Firstly try to produce a strategy node completely at random: for each square, either leave it blank or choose a number 0 to 7. Then determine whether or the not the strategy guarantees victory; in the likely event that it doesn't then start again.
For early-game positions, this approach is obviously futile. However for late-game (and occasionally mid-game) positions, it is a surprisingly effective means of obtaining a starting point.
Now we have a foot in the door, consider closely-related starting positions, e.g. the siblings that correspond to a different previous move by the second player. These sibling positions are often strategically similar, so there is a small chance that a modification to an existing strategy will extend its coverage to a sibling position.
This suggests a random walk approach: Suppose we are trying to obtain a single strategy that solves a total of n starting positions. Then a state in our random walk is a list of 2^n strategies. Each element in the list is either empty, or is a representative strategy that solves / does not solve each starting position, according to the bit mask of its index. So to take a step on the walk, we just modify an element on the list, score it, then insert it in the correct position.
When the walk reaches a solution corresponding to the all-ones bitmask, it will by definition work for each of the n starting positions, so we can stop. Hence in the solution graph, we can now erase all children of a given node. Iterating this idea reduces the node count of the graph.
This random walk approach relies on little understanding or experience of the Connect 4 game. This reflects the fact that I am a poor player!
While this project started off as attempt to improve 2swap's work, the graph was ultimately generated from scratch - largely by computer. Hence any similarities wrt choices of move are corroboration rather than derivation.
I think there is more still that can be squeezed out of this approach and have ideas for future improvements.
For instance, see the 4444422226666 position in the interactive game (i.e. play on columns 4, 4, 2, 2, 6, 6). There is an easy way of saving a node here...
In order to make the game as fair as possible (which is still completely unfair), hovering the mouse over a column will tell you what the computer's next move would be, should you play in that column.
The 'all fours' strategy - you'll know it when you see it - indicates a bad move by the player, i.e. an avoidable loss.
Press R to reset, right-click to undo.