Building an Unbeatable Tic-Tac-Toe AI (And Why It Keeps Crashing Your Browser)
So, you want to code an AI for a game. You think to yourself, "I'll just make it pick random moves!" Cool, but your friends will beat it in three seconds and laugh at you. If you want to make an AI that actually feels smart—or in the case of Tic-Tac-Toe, literally impossible to beat—you need to learn the Minimax algorithm.
Fair warning: when you first write this in JavaScript, there's a 90% chance you will accidentally freeze your browser tab forever. It's a rite of passage.
The Game Tree: Seeing the Future
Minimax works by essentially looking into the future. Imagine the current board state. Now imagine every possible move you could make. Now imagine every possible response your opponent could make to those moves. It branches out like a massive, terrifying tree of decisions.
The AI simulates this entire tree down to the very end of the game (the "terminal states"). If a path leads to an AI win, it scores it a +10. If it leads to you winning, it scores a -10. Then it works backwards up the tree. The AI wants the maximum score (it's the "Maximizer"), and it assumes you will play perfectly to force the minimum score (the "Minimizer").
Why Does It Freeze My Browser?
Tic-Tac-Toe is a tiny game, and its game tree still has a few hundred thousand possible states. JavaScript is single-threaded, meaning if you tell it to calculate 300,000 moves, the entire browser window locks up until it's done.
If you try this with Connect Four? Trillions of states. Your computer will catch on fire. We need to cheat a little to make it faster.
Enter Alpha-Beta Pruning
Alpha-Beta pruning is a fancy way of saying "stop doing pointless math." As the AI scans the tree, if it finds a move that is definitively worse than a move it already checked, it just stops looking down that branch. It "prunes" the tree. This cuts calculation times down drastically without changing the final decision.
The Hack: Iterative Deepening
Even with pruning, sometimes the AI just can't finish calculating fast enough. To stop the browser from freezing, we use Iterative Deepening. The AI searches 1 move ahead. Then 2 moves. Then 3. If it hits a time limit (say, 500 milliseconds), it just aborts the search and plays whatever the best move was from the last completed check. It keeps the game smooth and responsive.
Teaching It Strategy: Heuristics
For big games like Chess, the AI can't look all the way to the end of the game—it would take centuries. So it stops at a certain depth and guesses who is winning. This guess is a "heuristic." You write code that says, "Okay, having a queen is worth 9 points, a pawn is 1 point. Who has more points?" Writing a good heuristic is basically the dark art of AI programming.
Try Beating the Machine
I dare you to try and beat a properly coded Minimax AI. Best you can hope for is a draw. Go on, give it a shot: Tic-Tac-Toe, or test your own brain against Minesweeper and Sudoku.
