Machines That Think

Checkmate

While it's easy to make a machine understand the rules of chess, teaching it to select the best move from the wide array of all possible moves is incredibly difficult and computationally demanding. Why? Because mastering chess is all about knowing what will happen next and choosing your moves accordingly. To pick the next move in a game, a chess computer must build a large search tree containing all possible future moves by both players-itself and its opponent. The following image shows an example of a tiny part of a search tree, where white circles represent the machine's moves and black squares represent the opponent's moves:

At the bottom of the tree, we find the outcomes of all possible games: 1, 0, and -1 for a win, a draw, and a loss, respectively. Given such a search tree, a chess computer can determine which move is the best using an algorithm called Minimax. This algorithm was created by John von Neumann in 1928-yes, long before artificial intelligence was even a discipline-and adapted in 1950 for chess by Claude Shannon (who also attended the famous Dartmouth conference). The algorithm works by moving upward from the last move and selecting the best position for each possible position that the opponent might take-that is, the maximum. On the next level, it assumes that the opponent will choose the worst possible position for itself, in other words, the minimum. This maximum/minimum stuff is the origin of the algorithm's name: Minimax. Finally, the best among the three highest-ranked positions is chosen as the best move. Next, it's the opponent's turn to make a move, and then . the chess computer must build an entirely new tree based on the new position on the board and repeat the whole Minimax process. And so it goes, move by move, until the game is over. To say the least, Minimax is a clever idea, but if you stare at a chessboard for a bit, you quickly see a huge problem: It's impossible to imagine every possible game that can unfold on the board-or search through the entire tree-as a chess computer would have had to do. If, on average, it's possible to make 35 moves from a given position and a game of chess lasts for around 80 moves, we end up with a search tree of 3580 possible positions. That number is beyond huge. We can write it as 10123, meaning a 1 followed by 123 zeroes. That's how many positions Minimax would have to process to say anything about the value of a position. By comparison, the entire universe, with all its interstellar dust and every known galaxy, contains roughly 1075 atoms. This means two things. First, it's unlikely that chess will ever be solved with complete accuracy. We cannot know whether White can win by playing perfectly or whether a perfect game would end in a draw. In that sense, chess is one of the mysteries of our universe, which is kind of beautiful. Second, since a chess computer can't possibly search through the entire tree, we have to resort to some tricks. Three tricks, to be precise.

The first trick-one that truly separates strong chess computers from weak ones-is creating an evaluation function that approximates how favorable a given position is, without having to search the entire tree. A moderately good chess computer might, for example, simply compare the number of pieces each player has. A slightly better chess computer will assign different weights to different pieces, recognizing that a queen is worth more than a pawn, and so on. No matter how advanced this function is, in the end, it produces a number indicating how favorable a position is.

On to the next trick: Since no computer can search through the entire tree, we need to provide it with a rule regarding how deep to search: a maximum depth. "Only look five moves ahead," the rule might say. However, this rule can cause a serious problem: Move five might involve the computer using its queen to take one of the opponent's pawns, which is good. However, what if this pawn was protected by another pawn, causing the opponent to capture the computer's queen with a pawn, in move number six? The machine would be unable to account for this event and would therefore evaluate the position five moves ahead entirely incorrectly. An algorithm called quiescence search was developed to solve this issue; with quiescence search, the computer will continue searching until it reaches a stable position, where serious events like "pawn captures queen" cannot happen.

And now for the final trick: Computing power is among the most valuable resources search algorithms have. To save computing power, it's important to recognize that some future positions are outright hopeless and not worth examining. To see which future moves are worth pursuing down the tree and which branches are irrelevant, an algorithm called alpha-beta pruning is used. Pruning means to cut away or trim, and the simple purpose is to virtually trim the irrelevant branches from the tree-just like we can trim the bad branches off a fruit tree.

These ingredients-Minimax with a fixed depth, quiescence search, and alpha-beta pruning-are the cornerstones of all chess computers, including Stockfish, the standard chess computer for evaluating players' positions on live chess broadcasts. Today, Stockfish can beat any human chess player using only the computing power found in an iPhone. However, we haven't always had access to all this computing power.

Professor Edward Fredkin was behind many important advances in artificial intelligence. To this day, he is perhaps best known for lending his name to a research prize, announced in 1980 by Carnegie Mellon University. The Fredkin Prize, totaling $100,000, was meant to motivate computer scientists to create a computer that could beat the world's best chess player. However, the researcher who would eventually go on to win the Fredkin Prize never set out with that ambition. Instead, his victory was the result of coincidence and a PhD that went in a different direction than initially intended. The hero of this story is the young PhD student Feng-hsiung Hsu, who had little regard for artificial intelligence. Hsu began working on his PhD at Carnegie Mellon University in 1985 and later stated that, while he didn't consider artificial intelligence to be "bullshit," he had "seen some so-called research in artificial intelligence that really deserved the bullshit label." Hsu also had no particular interest in computers that played chess. He was more of a hands-on computer scientist with a fondness for engineering problems-especially those involving a computer's tiniest building blocks: chips. Simply put, a chip is a tiny flat object with an electronic circuit that, together with other components, makes up computers. And if there was one thing Hsu enjoyed, it was creating, and continuously improving, chips.

Today, you can turn your phone or computer into a chess master by buying the correct app or program, even though neither machine was built specifically for playing chess. This is the charm of digital computers: they can execute any kind of program without being built specifically to do so. But in the late 1980s, chess computers faced a major computing capacity challenge: Even given the three tricks, a chess computer is more successful the more potential future positions it has the capacity to explore. The best chess computers were therefore specifically designed and built for fast searches. And one key ingredient in custom-built computers is high-quality chips. This is how Hsu and his fellow students were recruited-though somewhat reluctantly-to participate in chess tournaments for computers. Hsu only had seven weeks' notice for his first tournament, which meant that his development happened under pressure and without enough testing. He and his team participated with a program they named ChipTest to emphasize that the program had not yet been fully tested. The outcome was mediocre, but less than a year later, the team won a convincing victory with an improved version of the program. At that point, ChipTest was searching through 500,000 chess moves per second. The road from ChipTest to a truly strong chess computer that could beat grandmasters would demand a significant increase in the number of chess moves the computer could search through.

When Hsu first started working with what would become ChipTest, estimates suggested that, if the speed of the hardware could be increased a thousandfold, it might be possible to create an artificial world chess champion. This engineering challenge was enough to ignite a spark in Hsu; his motivation was rooted in finding out whether a substantial increase in speed would truly be enough to solve the chess problem. For Hsu, beating the world's greatest chess player was merely a potential bonus.

After completing his PhD, which ended up being about ChipTest and chess tournaments, Hsu started working at IBM. There, ChipTest was developed further into Deep Thought, which sounds like something out of the Terminator movies. In 1989, Deep Thought challenged the reigning world champion, Garry Kasparov, for the first time, and Kasparov easily defeated Deep Thought in both games they played.

To turn his chess computer into a champion, Hsu needed to find a better, smarter way to search through enough possible future moves to win. And that's exactly what he did. In collaboration with many other engineers, he spent his entire PhD, followed by a decade of development, to...