Sep 16, 2021
Chess is a game that came out of 7th century India, originally called chaturanga. It evolved over time, perfecting the rules - and spread to the Persians from there. It then followed the Moorish conquerers from Northern Africa to Spain and from there spread through Europe. It also spread from there up into Russia and across the Silk Road to China. It’s had many rule formations over the centuries but few variations since computers learned to play the game. Thus, computers learning chess is a pivotal time in the history of the game.
Part of chess is thinking through every possible move on the board and planning a strategy. Based on the move of each player, we can review the board, compare the moves to known strategies, and base our next move on either blocking the strategy of our opponent or carrying out a strategy of our own to get a king into checkmate.
An important moment in the history of computers is when computers got to the point that they could beat a chess grandmaster. That story goes back to an inspiration from the 1760s where Wolfgang von Kempelen built a machine called The Turk to impress Austrian Empress Maria Theresa. The Turk was a mechanical chess playing robot with a Turkish head in Ottoman robes that moved pieces.
The Turk was a maze of cogs and wheals and moved the pieces during play. It travelled through Europe, beating the great Napoleon Bonaparte and then the young United States, also besting Benjamin Franklin. It had many owners and they all kept the secret of the Turk. Countless thinkers wrote about theories about how it worked, including Edgar Allen Poe. But eventually it was consumed by fire and the last owner told the secret. There had been a person in the box moving the pieces the whole time.
All those moving parts were an illusion. And still in 1868 a knockoff of a knockoff called Ajeeb was built by a cabinet maker named Charles Hooper. Again, people like Theodore Roosevelt and Harry Houdini were bested, along with thousands of onlookers.
Charles Gumpel built another in 1876 - this time going from a person hiding in a box to using a remote control. These machines inspired people to think about what was possible. And one of those people was Leonardo Torres y Quevedo who built a board that also had electomagnets move pieces and light bulbs to let you know when the king was in check or mate. Like all good computer games it also had sound.
He started the project in 1910 and by 1914 it could play a king and rook endgame, or a game where there are two kings and a rook and the party with the rook tries to get the other king into checkmate. At the time even a simplified set of instructions was revolutionary and he showed his invention off at the Paris where notable other thinkers were at a conference, including Norbert Weiner who later described how minimax search could be used to play chess in his book Cybernetics.
Quevedo had built an analytical machine based on Babbage’s works in 1920 but adding electromagnets for memory and would continue building mechanical or analog calculating machines throughout his career. Mikhail Botvinnik was 9 at that point and the Russian revolution wound down in 1923 when the Soviet Union was founded following the fall of the Romanovs. He would become the first Russian Grandmaster in 1950, in the early days of the Cold War. That was the same year Claude Shannon wrote his seminal work, “Programming a Computer for Playing Chess.” The next year Alan Turing actually did publish executable code to play on a Ferranti Mark I but sadly never got to see it complete before his death. The prize to actually play a game would go to Paul Stein and Mark Wells in 1956 working on the MANIAC. Due to the capacity of computers at the time, the board was smaller but the computer beat an actual human.
But the Russians were really into chess in the years that followed the crowing of their first grandmaster. In fact it became a sign of the superior Communist politic. Botvinnik also happened to be interested in electronics, and went to school in Leningrad University's Mathematics Department. He wanted to teach computers to play a full game of chess. He focused on selective searches which never got too far as the Soviet machines of the era weren’t that powerful. Still the BESM managed to ship a working computer that could play a full game in 1957.
Meanwhile John McCarthy at MIT introduced the idea of an alpha-beta search algorithm to minimize the number of nodes to be traversed in a search and he and Alan Kotok shipped A Chess Playing Program for the IBM 7090 Computer, which would be updated by Richard Greenblatt when moving from the IBM mainframes to a DEC PDP-6 in 1965, as a side project for his work on Project MAC while at MIT. Here we see two things happening. One we are building better and better search algorithms to allow for computers to think more moves ahead in smarter ways. The other thing happening was that computers were getting better. Faster certainly, but more space to work with in memory, and with the move to a PDP, truly interactive rather than batch processed.
Mac Hack VI as Greenblatt’s program would eventually would be called, added transposition tables - to show lots of previous games and outcomes. He tuned the algorithms, what we would call machine learning today, and in 1967 became the first computer program to defeat a person at the tournament level and get a chess rating. For his work, Greenblatt would become an honorary member of the US Chess Federation.
By 1970 there were enough computers playing chess to have the North American Computer Chess Championships and colleges around the world started holding competitions. By 1971 Ken Thompson of Bell Labs, in a sign of the times, wrote a computer chess game for Unix. And within just 5 years we got the first chess game for the personal computer, called Microchess. From there computers got incrementally better at playing chess. Computer games that played chess shipped to regular humans, dedicated physical games, little cheep electronics knockoffs. By the 80s regular old computers could evaluate thousands of moves.
Ken Thompson kept at it, developing Belle from 1972 and it continued on to 1983. He and others added move generators, special circuits, dedicated memory for the transposition table, and refined the alpha-beta algorithm started by McCarthy, getting to the point where it could evaluate nearly 200,000 moves a second. He even got the computer to the rank of master but the gains became much more incremental. And then came IBM to the party.
Deep Blue began with researcher Feng-hsiung Hsu, as a project called ChipTest at Carnegie Mellon University. IBM Research asked Hsu and Thomas Anantharamanto complete a project they started to build a computer program that could take out a world champion. He started with Thompson’s Belle. But with IBM’s backing he had all the memory and CPU power he could ask for.
Arthur Hoane and Murray Campell joined and Jerry Brody from IBM led the team to sprint towards taking their device, Deep Thought, to a match where reigning World Champion Gary Kasparov beat the machine in 1989. They went back to work and built Deep Blue, which beat Kasparov in their third attempt in 1997. Deep Blue was comprised of 32 RS/6000s running 200 MHz chips, split across two racks, and running IBM AIX - with a whopping 11.38 gigaflops of speed. And chess can be pretty much unbeatable today on an M1 MacBook Air, which comes pretty darn close to running at a teraflop.
Chess gives us an unobstructed view at the emergence of computing in an almost linear fashion. From the human powered codification of electromechanical foundations of the industry to the emergence of computational thinking with Shannon and cybernetics to MIT on IBM servers when Artificial Intelligence was young to Project MAC with Greenblatt to Bell Labs with a front seat view of Unix to college competitions to racks of IBM servers. It even has little misdirections with pre-World War II research from Konrad Zuse, who wrote chess algorithms. And the mechanical Turk concept even lives on with Amazon’s Mechanical Turk services where we can hire people to do things that are still easier for humans than machines.