Algorithms and games
Pathfinding
Five grid search algorithms side by side on walls you draw. The search […]
Connect Four
Drop discs and line up four, against an AI you can switch between minimax, alpha-beta, Monte Carlo tree search and simpler players. Written first in Python, rebuilt for this page in TypeScript.
Live demo
The first version of this game and its AI was written in Python. Python does not run in a browser, so the board you can play here is a TypeScript rewrite of the same ideas. Pick any of the five opponents below.
Rules
- 01The grid has 7 columns and 6 rows and stands upright. Two players take turns, the first player starts.
- 02On your turn you choose a column and drop one disc into it. It falls to the lowest empty cell of that column. A full column cannot be chosen.
- 03The first player to line up four of their discs in a row, across, down or on either diagonal, wins immediately.
- 04If all 42 cells are filled and nobody has four in a row, the game is a draw.
- 05With perfect play from both sides the player who starts can always win, but only by starting in the centre column.
Algorithms
- 01Minimax →O(7^d)
Plays out every sequence of drops to a chosen depth, assuming you always answer with your best move, and picks the first move of the best sequence.
Steps- Try each of the up to seven columns for the AI.
- From each result try the seven columns for you, and so on to the chosen depth.
- A four in a row is a huge score for whoever makes it, and sooner is better than later. Other leaves get the line-counting evaluation.
- Back the scores up the tree, maximising on the AI’s turns and minimising on yours.
- 02Alpha-beta pruning →O(7^(d/2)) best case
The same search with two running bounds so that hopeless branches are never explored. Trying the centre column first makes the cuts come earlier.
Steps- Keep alpha (what the AI is already sure to get) and beta (what you are already sure to hold it to).
- As soon as alpha reaches beta, the rest of that branch cannot change the decision: stop.
- Order the columns 4, 3, 5, 2, 6, 1, 7 so the strongest moves are tried first.
- 03Monte Carlo tree search →O(iterations × game length)
Judges a column by how often random games that start with it end in a win, concentrating the games on the promising columns as it learns.
Steps- Select a path through the tree with UCT, which balances exploiting good columns and exploring rarely tried ones.
- Expand with one untried column, then finish the game with random drops.
- Add the result (win, draw or loss) to each position on the path.
- After the chosen number of games, play the most visited column.
- 04Greedy and random baselinesO(7)
Greedy picks the column whose resulting position scores best right now; random drops anywhere. Beating them is the minimum bar for a real search.
Algorithm pages
Each of these has a page of its own, with the steps, the cost and the other places it is used.
How it works
- 01Connect Four has at most seven moves per turn, so a search can look a long way ahead: the opponent menu lets you choose how it uses that.
- 02Positions are judged by counting the 69 possible lines of four. A line that only you can still complete is worth more the closer it is to finished, a line that only your opponent can complete counts against you, and the centre column is worth a bonus because it belongs to the most lines.
- 03Press “Compare the algorithms here” to run the four searching players on the current position. Minimax and alpha-beta pick the same column, but alpha-beta reaches it after examining far fewer positions.
More in this category
Algorithms and games
Tic-tac-toe
A tic-tac-toe opponent that cannot be beaten, built on minimax with […]