Four in a Row

Four in a Row came out in 1974 from Milton Bradley. It looks trivial until you play someone who actually knows what they're doing. The rules fit in one sentence. You drop a chip into one of seven columns, it falls to the lowest empty spot, and the first player to get four of their colour in a row (horizontal, vertical or diagonal) wins. The interesting bit is that the game was mathematically solved in 1988. With perfect play from both sides, the first player always wins by starting in the centre column. It stays interesting because almost nobody plays perfectly.

In our version you play red and the AI plays yellow. The AI runs standard minimax search with alpha-beta pruning, and there are three difficulty settings.

• Easy searches to depth 2, so it looks two moves ahead. It will block an obvious three-in-a-row but misses traps and double threats. Most players beat it consistently.
• Medium searches to depth 4. It sees most tactical combinations and sets up forks of its own, and it's about even with a casual player who knows the basics.
• Hard searches to depth 6. It reads the whole mid-game accurately and plays close to optimally. You'll need real strategy to beat it with any consistency.

How to actually play well. Three principles cover 80% of the game. The first is to play the centre column whenever you can, since the centre is part of more potential four-in-a-row lines than any other column. The second is to create double threats, meaning two separate three-in-a-row setups so your opponent can only block one of them. The third is to count parity. In a long game, odd-numbered rows (1, 3 and 5 from the bottom) favour player one and even rows (2, 4 and 6) favour player two, so try to force the win onto a row that suits you.

Build notes. The minimax function uses alpha-beta pruning with move ordering. We try the centre columns first because they're statistically the strongest moves, and that lets the search prune more aggressively. The evaluation function scores every 4-cell window on the board. A 3-in-a-row with an empty cell is worth 15 points, a 2-in-a-row with two empties is worth 4, and an opponent's 3-in-a-row is a 25-point penalty because we want the AI to block aggressively. Even at depth 6 it answers in well under a second on every device we've tested. Four in a Row has a branching factor of only 7 (one move per column), so the search never gets out of hand.