Chess algorithms

Episode Summary

Title: Chess algorithms In this episode, host Tim Harford discusses the history and development of chess-playing algorithms. He begins by describing a 2012 game between chess grandmaster Garry Kasparov and Turochamp, a rudimentary chess program written in 1948 by mathematician Alan Turing. Turing's algorithm could analyze a few hundred moves per turn, taking 30 minutes to calculate each move. This demonstrated that algorithms could be executed by humans, not just computers. Harford traces the history of algorithms back thousands of years to ancient Babylon and Greece. In the 1950s, Claude Shannon showed how Boolean algebra could be applied to circuits, enabling algorithms to be processed digitally. Early computer scientists saw chess as a way to explore machine intelligence. But as chess programs like IBM's Deep Blue showed, beating humans didn't require human-like cognition. Modern algorithms like CloudCV can now surpass humans in specialized tasks without general intelligence. DeepMind's AlphaZero took this further by learning entirely through self-play, mastering chess and Go in mere hours. Kasparov argues AlphaZero essentially programmed itself. While not yet exhibiting general intelligence, modern algorithms can outperform humans in an expanding array of tasks through brute-force computation. Harford concludes that step-by-step algorithms can go a long way, despite lacking human-style planning.

Episode Show Notes

In 1997, Garry Kasparov, widely regarded as the world's greatest chess player, was defeated by Deep Blue, a computer. But how much did that reveal about the 'brainpower' of machines? Tim Harford explains by delving into the history of algorithms. They've been used by mathematicians and scientists for millennia, but have acquired a new level of power and importance in the digital age.

Episode Transcript

SPEAKER_06: Amazing, fascinating stories of inventions, ideas and innovations. Yes, this is the podcast about the things that have helped to shape our lives. Podcasts from the BBC World Service are supported by advertising. SPEAKER_03: Ryan Reynolds here from Mint Mobile. With the price of just about everything going up during inflation, we thought we'd bring our prices down. So to help us, we brought in a reverse auctioneer, which is apparently a thing. Mint Mobile Unlimited Premium Wireless. SPEAKER_02: How did it get 30? 30? How did it get 30? How did it get 20? 20? How did it get 20? How did it get 15? 15? 15? Just 15 bucks a month? Sold! Give it a try at mintmobile.com SPEAKER_03: slash switch. New activation and upfront payment for a three month plan required. Taxes and SPEAKER_00: fees extra. Additional restrictions apply. See mintmobile.com for full terms. SPEAKER_05: 50 things that made the modern economy with Tim Harford. SPEAKER_02: On the 25th of June 2012, Garry Kasparov, regarded by many as the greatest player in the history of chess, sat down to play a game against a computer. He wasn't sitting down for long. Checkmate took 16 moves and a mere 40 seconds, leaving Kasparov apologising for winning so quickly. The computer programme, Turochamp, is noteworthy not for its strength, but its history. It had been written in 1948 by the mathematician, code breaker and computer pioneer Alan Turing. The programme looked at a few hundred options and made the move that produced the position with the highest value. On a modern laptop, that calculation takes a fraction of a fraction of a second. Alan Turing had no computer and took half an hour per move to make the calculations using a pencil and paper. Kasparov was in awe that Turing had written a computer algorithm without a computer. An algorithm is a step-by-step procedure, a set of well-defined instructions that one follows to produce a result, a recipe written by an infinitely pedantic chef. These days we think of algorithms as something rather mysterious that computers do, but as Turochamp demonstrates, algorithms can be executed by humans. For most of the history of algorithms, there was no other way. The word algorithm derives from the name of a brilliant Persian mathematician active about 1200 years ago. His name was Muhammad ibn Musa al-Khwarizmi and European scholars later called him Algorhythmi. Algorithms themselves predate al-Khwarizmi. They were used in Babylon nearly 4000 years ago to calculate the solutions to algebraic problems. More than 2000 years ago, the Greek mathematician Euclid published an algorithm for producing the greatest common divisor of two numbers. In the 1850s, George Boole, professor of mathematics at Queen's College Cork in Ireland, published The Laws of Thought, simplifying logical propositions into mathematical operations. Boolean algebra then languished for 80 years until the American mathematician Claude Shannon showed that Boole's laws of thought could be obeyed by electrical circuits. True or false became on or off. The digital age was arriving and that meant that algorithms could realise their full potential. Computer chess is far too complex to solve by brute force, as Claude Shannon noted in 1950 in the first ever academic paper written about computer chess. Shannon wrote... SPEAKER_01: The problem is not that of designing a machine to play perfect chess, which is quite impractical, nor one which merely plays legal chess, which is trivial. We would like to play a skillful game, perhaps comparable to that of a good human player. SPEAKER_02: Comparable to that of a good human. That's where all this is going, is it not? Could a mere algorithm, grinding mindlessly through a pre-specified procedure, outperform the human mind? And what else might such an algorithm achieve? Turing and Shannon were intrigued by computer chess as a way of exploring how machines could think. For a long time, chess mastery seemed to be ineffable. Think about Alan Turing the man versus Alan Turing the human calculator following the churro champ algorithm. Turing could have played a better game of chess by relying on his intuition, and with far less effort, but he could never have explained quite how. Douglas Hofstadter, the author of Gödel, Escher, Bach, a 1979 book about the emergence of intelligence, argued that a computer that was sophisticated enough to be the world champion at chess simply couldn't help but be intelligent in other ways. I'm bored with chess, it might reply, when challenged to a game. Let's talk about poetry. SPEAKER_02: But computer chess proved to be more routine than Hofstadter had expected. The first computer to beat a human world champion, Kasparov himself in 1997, was IBM's Deep Blue. It never broached the topic of poetry. It worked much like Churro Champ, except that it examined 150 million positions a second and was supported by a huge library of human game openings. One move that dismayed and defeated Kasparov was simply plucked out of Deep Blue's library of games played by humans. How mundane. Hofstadter was exasperated by Deep Blue's failure to be a truly general artificial intelligence. Problem solving without human-like thought, he complained, was trickery. IBM's attitude is typical of successful algorithmic design today. Programmers don't try to emulate human cognition. They want their computers to deliver results. And these days, despite a continued lack of interest in discussing poetry, delivering results is what computers do. Consider, for example, CloudCV, a system which accurately answers informally phrased questions about photographs. I tried it out on a picture of some young people hanging out in someone's front room. What are they doing? I typed. What are they drinking? CloudCV promptly and correctly told me that they were playing on a Wii and drinking beer. Similar systems can diagnose skin cancer, breast cancer or diabetes at a level that is rapidly surpassing skilled medical professionals. They are still algorithms, but not algorithms that Euclid or even Alan Turing would have recognised. Then there's AlphaZero, the game learning algorithm developed by DeepMind, a sister company of Google. In 2017, AlphaZero trained itself in a matter of a few hours to thrash the best chess-playing software, Stockfish, and the best Go program, AlphaGo Zero, both of which easily beat the best humans. Kasparov points out that AlphaZero effectively programs itself. Humans wrote the learning algorithm, then the learning algorithm, wrote a program to play chess far better than any human. While AlphaZero is exceptional, there's nothing exceptional about computers writing their own programs. Many modern algorithms work by generating their own rules to fit the data they're being shown. If the last decade is any guide, then algorithms may be able to outperform humans at far more than chess and Go. Step by step can take you a very long way, as long as you don't have to plan each of those steps with paper and a pencil. SPEAKER_04: A frontline guide to the world of chess algorithms is Gary Kasparov's Deep Thinking. SPEAKER_05: For a full list of our sources, please see bbcworldservice.com. SPEAKER_07: into audio adventures. My question for crowd science is why and when did humans first start SPEAKER_05: cooking food? It's all fair! I'm Marnie Chesterton and each week we put your questions to scientists SPEAKER_07: working at the limits of human knowledge. I wanted to know how cells, how do they know what to do? SPEAKER_06: They're yanking on their neighbors, they're pushing on their neighbors. We also try and SPEAKER_07: demonstrate exactly what they're telling us. What are the limits of human endurance? You've just SPEAKER_07: run a marathon and been hit by a car. How are you? That's CrowdScience from the BBC World Service. So if you'd like to inject a bit more science into that, just search for CrowdScience wherever SPEAKER_07: you get your podcasts. I knew it! Amazing!