The Slow Race to Solve Chess

Can an algorithm deliver a definitive solution to the problem of a chess game?

|
Jan 3 2015, 12:00pm

​Image: Cyndy Sims Parr/Flickr

Deep Blue, the computer that infamously defeated chess champion Garry Kasparov in 1996, was capable of evaluating some 200 million different positions per second. It was a marvel of computing hardware, but the chess computer arms race has since then become a battle of algorithms. In 2006, the program known as "Deep Fritz" faced off against World Chess Champion Vladimir Kramnik, crunching just 80 million moves per second but with the capability of examining moves very "deep" within the game.

Now, chess championships exist just for programs—algorithms, really—to face off against each other. The winner of 2014's Thoresen Chess Engines Competition, considered by some to be the de facto world computer chess championship, is a system known as Komodo, the creation of chess Grandmaster Larry Kaufman and programmer Don Dailey. The program's creators note that Komodo can be expected to have a gain of 40 elo (elo being a probabilistic skill rating system for chess and other games) over other leading chess engines. That goes up to 50 in a multicore machine.

The advantage comes from a few different things, one being a better ability to use multiple processing cores, which is really a general problem for computer algorithms. (For all kinds of reasons, from shared memory access to intercore communication.) It also boasts better search efficiency (looking forward though a game) and time management. Again, these are pretty general computing problems.

Potential Komodo customers (the program can be had for about $60) are greeted with the words/endorsement of human chess grandmaster Boris Avrukh: "I am deeply moved by the style of Komodo. In my opinion it's the perfect combination between computer accuracy and human positional understanding. acy and human positional understanding. I get the feeling it's taken positional understanding to the next level."

Is chess a solvable problem?

In other words, can a computer play a perfect game of chess or just a really good game? It's an open question. Paraphrasing UNIX co-creator Ken Thompson, Dick Lipton, a computer science professor at Georgia Tech, ​summarizes the historical chess challenge as such: "All chess programs looked at a huge set of positions and then generated one move. As long as the move was legal the programmer had no idea the program had made an error—unless the move led to an unexpected loss."

This is the hellscape of complexity, in a nutshell. A chess game is a space of possibilities, a collection of states, one that might update entirely given a single move by either player. Solving chess means computing every possible move and every possible update until there are no more possibilities. Nothing less.

In theoretical computer science, a game is given by a game-tree. This is a collection of nodes, with each one representing the current state of a game along with every possible move given that state. These moves are represented by branches or "edges" from the current node. A complete tree has a node for every possibility.

The technical challenges are, well, technical—or at least mathematical. Like, how to take the immense move-spaces (or graphs or trees) of a chess game and conduct simple or simple-enough searches within them. Or, how to store the massive piles of accumulated data required by a true chess solution, in which every possibility ever has been computed and stored. The information theory pioneer Claude Shannon estimated that a true chess solution would need to store and compare 10 120 moves.

Which is this:

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Consider that the number of atoms contained within the observable universe is estimated to be a mere 10 80. In 2007, computer scientists at Reykjavik University ​"solved" checkers, a game with a position-space of some 1020 possible moves. Both players playing perfect (solved) games led to a draw, as expected.

On a 1 mHz processor, Shannon calculated, it would take 10 90 years to crunch a perfect chess game, or this many years (leaving the problem for quantum computers):

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Sixty-four squares, 32 pieces, two players, one winner. It's actual computer hell, but still a theoretically possible hell, according to ​Zermelo's theorem. The theorem basically states that there exists a set of moves that will win a chess game regardless of how the other player responds. This is generally true of any game that doesn't involve either hidden information or random chance. An opponent can delay a loss, but not prevent it.

This is still subject to the very large numbers above, however. To say that something is theoretically possible doesn't demand that it be practically possible. The checkers solution mentioned above, courtesy of computer scientist Jonathan Schaeffer, was only a "weak" solution based on simulations that discarded bad or poor moves immediately rather than following them all the way through. Of the 1020 possible checkers moves, only 1014 needed full evaluation. Still, it took a month of processing time.

As for chess, ​Schaeffer told IEEE Spectrum back in 2007 that a solution, even using his "weak" approach, couldn't even be attempted using existing computing technology. Chess is a quantum problem. "The one thing I've learned in all of this is to never underestimate the advances in technology," he said.