Towards Beating the Engine

This post is about chess, but chess as it bears on a larger question. How do you play against a computer that's smarter than you? As time passes that question seems more and more important. The general case is vague enough to make things difficult to answer, so we'll take a good bit of time to look at playing against chess computers. In the grand scheme of things it might not matter whether we win or lose over the board, but it matters a great deal how raw humanity can compete with silicon intelligence.

In 1997 then-reigning world champion Garry Kasparov lost a chess match against the IBM supercomputer Deep Blue. In 2006 Kramnik (who had taken the title from Kasparov) lost a match to a program running on ordinary computer hardware. Since that time the engine has reigned supreme. I've asked my local chess club whether a human might ever beat the engine ever again. I'm the only one who sees even a glimmer of a possibility.

How did We Get Here?

Thousands of years of human dominance. A few decades of weak competition, a few years of struggle for supremacy. Then, game over. -Garry Kasparov, who, on the whole, really is an optimist about technology.

Alan Turing, the famous computer scientist, invented the first chess engine. Simple as it was (only evaluating the moves currently available) it was still too complex to run on the computers of his day, so he played a game with it, working out the calculations by hand. It wasn't a great game --- as far as chess goes --- but it was at least recognizable, which makes it a stunning achievement. As Samuel Johnson noted of a dog walking on its hind legs: "It's not so much that it does it well as it does it at all."

I bring up Turing's engine because the logic is easily comprehensible to us humans. It works sorta like this:

For each move on the board, if you make that move:

1. Does it capture a piece? If so, assign points for the value of that piece.
2. How much room does it allow your pieces to maneuver in the future? Assign points for potential activity.
3. How well protected is your king? Assign points for good defense.

Sum up the points for every possible move you can make, and then choose the move with the highest score.

Even Turing's original engine was more sophisticated than that --- weighing more considerations --- but that's enough to go on. (If you'd like the specifics you can find them at the linked videos here and here.) Later chess engines also run an evaluation for the moves your opponent makes, to see how good they are, and so on. For the interested nerd, the phrase "to Google" is "alpha-beta pruning". The rest of us will blithely march on and assume the computer knows its business. We're also going to skip over most of the history of human-computer chess. If you'd like to know more about that, I highly recommend Kasparov's 2017 book Deep Thinking.

In 2016 a new challenger appeared. At that time the best engine in the world was known as Stockfish. Google trained an algorithm called AlphaZero using machine learning techniques. It wrote a program to play chess against itself over and over and over again until it got good. How good? Good enough to feed Stockfish its own pants. Google then diverted into other areas of research. The engineers behind Stockfish rebuilt their engine to incorporate machine learning principles (and how that works, I haven't the foggiest), and these days the top-level computer versus computer chess is played between Stockfish (who reigns once again) and an open-source project called Leela. I'd love to get Kasparov's thoughts on this but publication dates being what they are, I'll have to wait for a sequel.

Thinking about the Computer's Thinking

If you know your opponent and you know yourself you will be victorious in a hundred battles --- Sun Tzu, who's never been down a rook and a bishop and forced to trade queens.

During the decades between the advent and the triumph of computer chess, engineers were caught in a dilemma. Take another glance at that algorithm. You can refine it two ways. Either you evaluate a given move more precisely or you calculate one move deeper. Call it a sniper versus machine gun approach. A sniper will target one bullet exquisitely, being pretty sure he's going to hit the right thing. A machine gunner will spray hundreds of bullets at the target, also being pretty sure he's going to hit it with at least one. It's hard to do both.

A chess algorithm has a calculation it does to evaluate a given board position. This is a single shot in our analogy. The more precise the calculation, the more accurate the shot is. However, the more accurate each individual shot is, the slower it is to calculate. Alternately you could make the calculation very simple and not very accurate, but you can run it over and over again for a deeper set of results, machine-gun-like. If you increase the accuracy of any given shot, you decrease the rate of fire. If you calculate more positions, you need a more efficient and less accurate calculation.

An engineer can happily spend an entire career arguing with that dilemma, but we'll keep things simple. You know what else goes up exponentially? Computation power. Without denigrating the hard work put in at every level of these problems, part of the solution required waiting for the right hardware. We've gotten further than any human can calculate. But are you sure it's correct?

The only way to check that an engine is correct is to feed the position to another engine and see what it says. If they disagree, how do you know which is right? If they agree, are you sure they're correct? Since the engine is stronger than we humans there's a tendency to imagine it's infallible. You can't think that way if you're hoping to beat it.

The engine excels at tactics. Given a position, it can accurately calculate dozens of moves forward, but it can't calculate everything. On the first move of the game, white has twenty legal options. Black has twenty options as well. After each player has made a move that means there are 20x20 = 400 possible board states. Extend that out to, say, thirty moves, and people start throwing around phrases like "the number of atoms in the universe". The engine can't calculate every single possible move, so it has to cut it down. How sure are you that you've cut out only the inferior options?

Weaknesses in the Engine

No; not a chance - Magnus Carlsen on whether he could beat his phone.

Practically speaking this leaves two weaknesses in the engine. The first is that, despite its mastery of tactics, it lags behind humans in strategy. Suppose the engine evaluates the next twenty moves. If a given maneuver will only pay off twenty-four moves down the line, the engine will overlook that. Kasparov used an "anti-computer strategy" in a brilliant game against a chess computer in 2003, deliberately stalling the game where he could improve his position slowly while the machine couldn't. Here's a recent game where the engine may have misevaluated a strategic position, showing things to be dead even where white has a definite advantage. Or maybe the engine sees something we don't.

The second is that, to deal with the exponential options, the engine is forced to prune off certain branches, ignoring moves that don't look like they'll have a good outcome. Here's an example video from a couple years back, where the engine misses the winning move because it pruned off the wrong branch.

There's a fundamental problem with trying to exploit these resources. Computation power is cheap. The default you-haven't-even-signed-up-yet engines on Chess.com or Lichess will calculate twenty moves deep right in your browser. While it may still be possible to find small advantages that build up over the long term, the further out the computer can push that long term the harder it gets. At some point you run out of long term; for better or for worse most games are over by move one hundred.

The better the position evaluation, the less likely the machine is to ignore whatever small advantages you might see. In the final game against Deep Blue, Kasparov laid a trap for his opponent, figuring the algorithm wouldn't weigh long-term problems accurately against a knight gained now. Deep Blue avoided that trap, which cost Kasparov the game. In the decades when man was still superior, the engines made steady progress because they were advancing both in power and sophistication, in accuracy and rate of fire. Maybe they still are; it's kind of hard for a human brain to tell.

Should a human ever be able to challenge the machine in a fair match again, that gives us an idea as to how he'd have to do it. He'd have to start with world champion-level tactics to at least stay alive against the traps the machine would lay. Then he'd also have to have a brilliant grasp of strategy, making moves that give him benefits far down the line, such that he can use those tactics not only to stave off defeat, but to slowly build advantage. Then ideally he'd also be on the lookout for wild and crazy moves that the engine might overlook. I said up top that I see the glimmer of a possibility of it happening, but even that dim hope marks me as insanely optimistic. On the other hand, that doesn't leave us entirely without options.

If You Ain't Cheating you Ain't Trying

If at all possible play chess with your opponent sitting in front of a mirror. That way you can see his pieces. -Carlin. Not the comedian you're thinking of, the one in my local chess club.

I'd prefer humanity to win in a completely fair match. There are other options. It used to be common for stronger players to offer an odds match to their opponents; starting down a piece to even the game. We could do something similar for machines; restricting them to calculations within a certain time, or using a limited number of cycles, or even to only burn as much energy as a human brain. I like this idea because it creates interesting problems for the engineers, but I'm less sanguine about it because victory is kind of hollow when it comes to setting the dial.

Two more quick ideas I gleaned from Kasparov's book: One is to remove the computer's opening book. Human chess players have figured out the best first couple moves of the game (depending of course on what your opponent does). These are the moves where strategy matters most and tactics the least. By denying machines access to recorded memorized sequences, you're forcing them to make calculations where their calculations are the weakest. The other idea is to take the knights off the board. From novice to grandmaster, the tricky ways knights move seem to mess with human computation. A more linear game of chess is easier on our brains.

Instead of making things easier on us, you can make things harder on the machine. The engine is a computer program. Humans input data and the program spits out a move. Suppose I insisted the machine play like any other player. The designers have to build a robot capable of imaging and reading the board, doing the computation, and then gripping and placing pieces themselves. Then the problem designers have is several times more complex than merely building a better algorithm. You could insist the machine was forfeited due to mechanical failure. The difficulties I'm adding here are solvable --- similar things are routinely done in an industrial context --- but the principle is worth remembering: The more accommodating the human is toward the machine, the easier it is on the machine designer. The more the machine works to accommodate the human, the harder it is to build. Though I suppose you could even things out again by insisting the human play from inside a Mechanical Turk.

The Hippy-Dippy Solution: Can't We All Just Get Along?

AI deserves to lose. -James, the Bartender

Much as I hate to indulge in that kind of talk, there really are some interesting things that happen when you redefine the question. Do you know what happens when you pair a human and a computer versus a computer? I don't. Kasparov talks about an open tournament where any combination of human and computer teams could enter. The strongest computer didn't win. The strongest grandmasters with their engines didn't win. The winners were a pair of ordinary dudes running three off-the-shelf engines. They were better at working with the technology. That's an interesting result, but does it still apply with machine learning engines? I'd like to see the experiment run again. And again. There's plenty to explore.

On the other hand the idea of using a computer to cheat against a computer puts me in mind of my junior high football career. At some point you cross the line from providing questionable "help" to actively screwing things up for the better players.

There are ways we can learn from chess computers. We've run the great games of the past through the engines to see what we've missed. One surprising thing we learn here is that the moves made over the board, under tremendous pressure, are better than moves favored by analysts studying at their leisure afterward --- even when it's the players themselves doing the analysis. Simply having a machine capable of doing more accurate calculations than us gives us an opportunity to learn about how we ourselves think.

Some of the engine's ideas can be stolen and used by the hypermodern Prometheus. Computers like to push their H-pawn. This was considered a bad idea by right-thinking strategists for centuries, but you see it creeping more and more into human play. When I'm sitting across the board from another player, what does it matter that a computer can beat us both? Maybe if I steal some ideas from the machine I'll be able to crush the man in front of me.

The game Go has resisted the same sort of machine dominance, partly because it's harder to make a good evaluation function for a given position, and partly because the 19x19 board requires the engine to calculate more options each move. In our gunpowder analogy it's both harder to snipe and requires more machine gun bullets. Google's AlphaGo beat the world champion in 2016, almost twenty years after Kasparov lost. It did so because the machine learning algorithm it used deployed brand new tactics, things that the masters of the game hadn't even considered before. That's cool and all, but the story gets really wild in 2023.

Kellin Pelrine, an American Go player and not even a top-rated professional, beat a top-ranked engine. He did so by using a computer to analyze the engines for weaknesses, discovering a strategy that might work against them, and then deploying it entirely with his human brain. Perhaps the models can be trained to defeat this strategy, but there might be more chances besides that out there. Perhaps I should go back to the top and rewrite this whole post that way, but I'm a rank amateur at Go. The most I can say is that it validates my idea that computer dominance is not inevitable.

Playing a Different Game

I don't mind losing to my computer at chess because I still win the rematch at kickboxing. -Jack Rysider, a guy whose podcast I listen to only partially for dumb jokes.

We can make it impossible for the computer to win by changing the game. You may beat me at chess but I've decided to play Tic-Tac-Toe instead. Yeah, I know Tic-Tac-Toe is a solved game, and that in principle I can never do better than a draw against a computer, but it seems you weren't programmed to play that game. Guess I'll win by default. Any five-year-old employs this strategy under similar circumstances. When she decides she can't win, she'll say, "Let's play a different game."

Suppose the engineer comes back with a chess engine that also has a Tic-Tac-Toe solution stapled on. I challenge it to checkers, but he's thought of that, and it beats me at checkers too. And Go (remember, rank amateur), and Risk, and Monopoly, and even when I try Candy Land, an unlucky shuffle of the deck means the computer won even though neither of us, strictly speaking, made any choices. Board games as a class are relatively easy for a program to solve because the real-world complications are necessarily abstracted away. If you lined up real-life soldiers like chessmen, the resulting donnybrook would look nothing like a game. In real battles no one takes turns. By stating my original goal as beating the chess engine, I've already conceded most of my chance because I'm facing the computer on terms that are incredibly favorable to the computer.

This needn't be true in all circumstances, even in all games. Last I've heard the best human players of Starcraft II can still beat the best AI competition. You'd think a video game --- especially one reliant on precise timing and superhuman reaction speeds --- would favor the machine, but apparently not enough. I have my doubts that we'll ever see a computer able to play consistently professional Magic: The Gathering. Once you're dealing with questions that haven't been deliberately abstracted down, the computer's advantage diminishes rapidly. Granting that SkyNet thought of nuking its enemies back home, it'd have a hard time winning the resulting war because war is a game that greatly favors those who innovate.

As fascinating as I find games (almost certainly more than my audience — thanks for sticking around), we should look at the rest of the world. The computer from War Games is right; the only winning move is not to play. Why do we really care if the machines are better at chess? Even if the computer's dominance ruined the fun of me losing to other humans, I could leave that field behind and do something else with my life. But for how long? That's the lingering fear behind all worries about automation; what do you do when your job is automated away? When every job you can do is automated away?

Marc Andreessen is fond of reminding us that software is eating the world. It's cheaper to solve a problem in software than by getting a man to do it. However difficult the problem is, once it is solved you can copy and copy the solution. Hence, anything that can be solved by software will be solved by software. This worry has grown more acute since large language models burst into the public consciousness. The picture might have six fingers on the right hand, but I'm already seeing better pictures. Are you sure you can tell the difference between AI-generated art and stuff made by humans? If machines can take over the art world, what else is there?

I'm honestly not that worried. Because the Large Language Model that's spitting out --- let's not say art, because I'm not going to be competitive in the drawing world absent a last-man-on-Earth scenario --- computer code might do an amazing job at replacing me. But that AI is going to share some DNA with the chess engine. It'll determine what to put where based on a large calculation of rules it derived from its training set. That calculation is going to have weaknesses, weaknesses I can potentially exploit.

Perhaps I can out-compete it directly, by applying my superior strategic understanding to write code that's actually adapted to the problem at hand, not just the computer's understanding of the problem. Perhaps I can use the LLM to write some of the code, trusting it to handle the tactical problem-solving while I focus on the larger goals. Perhaps I can just write a better algorithm than the AI because it's pruning the wrong branches when it's optimizing it's decision tree. Perhaps I can switch to a field the machines are worse at: gardening, or baseball, or con artistry.

It may be that a world is coming where people are automated out of all usefulness. That they won't be able to get a job because there are literally no jobs that they can do profitably. That world isn't here today. It won't be here tomorrow either. If they announce tomorrow that they've got a new algorithm that can do everything I can do, but better, I still won't trust it. Algorithms, even unbeatable ones, have their weaknesses. And that's why I find it worth considering how I'd beat the chess engine.