Teaching a computer to lose

For a while there was a tic-tac-toe game on this blog, sitting where the posts should have been. You couldn’t beat it. Not “it’s pretty good” — you could not beat it, ever, and a draw was the best day you were going to have. I was proud of that for about a day, until I noticed nobody played it twice.

The trick behind it is minimax, and the whole idea fits in one sentence: assume your opponent is exactly as clever as you are. You look at the positions where the game is already over and score them — I win, you win, draw. Then you walk back up the tree. On your turn you take the best score available; on theirs you assume they’ll take the worst one for you. Alternate that all the way to the top and the number you’re left with is what the position is actually worth, assuming nobody blunders.

Tic-tac-toe is the classic teaching example because the entire game fits. A couple hundred thousand positions is nothing — you can search every possible future from the opening move and be certain you’re right. Which is also exactly why the result is joyless. A solved game, played perfectly, is a formality with extra steps.

The first genuinely clever thing you learn is that you don’t have to look at all of it. If one line already guarantees you a 3, and the very first reply in some other line drops to a 2, that second line is already dead — your opponent would be delighted to take you there, so you’ll never choose it, so the rest of that branch cannot possibly matter. You stop looking. That’s alpha-beta pruning, and the first time it worked I remember being faintly offended by how much of my carefully built tree it refused to visit.

Then I took a studio job writing game AI for things considerably larger than a three-by-three grid, and the whole frame flipped over. Perfect play isn’t the goal there. Perfect play is a bug. An opponent that never misreads you, never overcommits, never lets you get away with anything isn’t a hard opponent — it’s an unfun one, and players don’t rise to meet it. They quit.

So a surprising share of the work is making the thing worse, deliberately and precisely. Give it a reaction time. Let it take the second-best option sometimes. Let it lose track of you for a beat when you break line of sight, because a person would have. None of that is a weaker algorithm — it’s the same search with a deliberate hand on it. Difficulty turned out to be something you author, not a number you turn up.

The performance lesson landed in the same place. Asked to make the AI faster, my instinct was to make the search faster; the actual win came from searching less. Not every agent needs to think on every frame, most of them can reuse what they concluded a moment ago, and a cheap heuristic covers the boring majority of situations so the expensive search only runs when something interesting is happening. Budgeting the thinking beat optimizing it.

That’s the part I still carry around. Minimax I could have learned from a textbook in an afternoon — the algorithm was never the hard bit. The hard bit was that “good” and “optimal” turned out to be different things, and only one of them was in the spec. The bot on this blog was optimal. It was also the least fun opponent I have ever built.

— Adi