How the computer decides
Both games use minimax, one of the oldest ideas in game-playing artificial intelligence. The AI imagines every move it could make, then every reply you could make, then its answer to that, and so on, building a tree of possible futures. At the bottom of the tree it scores each position: a win is very good, a loss very bad. Working back up, it assumes you will always pick the move that is worst for it, and it picks the move that is best for it given that. The result is the move that guarantees the best outcome against a perfect opponent, as far as it can see.
Alpha-beta pruning
The tree grows explosively. Connect Four has seven possible moves at each turn, so looking eight moves ahead could mean more than five million positions. Alpha-beta pruning skips branches that cannot change the decision: once the AI has found that a move lets you force a loss, it stops examining that move's other replies. Searching the centre columns first, where good moves usually are, makes pruning far more effective. The note under the board shows how many positions the AI actually examined and how long it took, often a few thousand in a few milliseconds.
Tic-Tac-Toe: perfect play
Tic-Tac-Toe is small enough to search completely, so on medium and hard the AI plays perfectly and you cannot beat it. The best you can do is a draw, which is the known result of the game when both sides play well. On easy, the AI sometimes picks a random square, so you can win.
Connect Four: looking ahead
Connect Four is far bigger, so the AI looks a fixed number of moves ahead: two on easy, four on medium and eight on hard. When it cannot see to the end of the game, it judges positions with a heuristic: it scans every possible line of four, rewarding lines where it has three discs and an empty space, penalising yours, and preferring the centre column, which takes part in the most lines. Connect Four was mathematically solved in 1988: the first player can always win with perfect play by starting in the centre. Even the hard level here is beatable with careful planning, especially if you set traps that lie beyond its horizon.
Tips
- Control the centre column early.
- Build threats on odd and even rows so that one forced move sets up another.
- Watch for diagonals; they are the easiest to miss.
The games run entirely in your browser, with no account, download or network connection needed.