Throughout our History of AI series, we’ve looked at some pivotal entries in the videogames industry such as Left 4 Dead, Thief, Shadow of Mordor, and The Sims. But if you really want to get to the heart of artificial intelligence and games, we have to go back to the very origins of computing itself.
The First Automated Chess Players
The classic board game Chess is not only one of the most popular games in the western world but also a source of scientific curiosity. It’s a game that has been enjoyed by players for more than a millennium and has been the subject of championship tournaments for centuries. But perhaps more critically, for us anyway, it has played a major role in AI history.
Chess was important for computing even before the existence of a working computer. The ‘Mechanical Turk’ was a famous, and later infamous, Chess-playing machine from the 18th century developed by Wolfgang von Kempelen. Built originally to impress the Austrian Empress Maria Theresa, it toured around the world playing against human chess players as an example of an intelligent machine. However, it was later revealed to be nothing more than a hoax. The secret to the Turk’s success was that it was not actually a machine – and instead, a person could fit inside the box and make moves with an elaborate collection of levers that could move magnetic pieces across the board.
However, the Mechanical Turk inspired many designs for actual computing machines, including Charles Babbage’s Analytical Engine: a system that could have been one of the first general-purpose computing machines. Though sadly for numerous reasons, it was a concept that was designed but not built during Babbage’s lifetime. Similarly, there’s El Ajedrecista: a chess-playing machine from 1912 that could actually control and move chess pieces based on a predefined algorithm. A concept that for all intents and purposes, makes it the first computer game in history.
AI for Chess
While Chess proved influential in the early days of computing, it was also at the forefront of artificial intelligence research for much of the first 50 years of the field. Alan Turing, one of the grandfathers of computer science, was not only an avid chess player but by 1950 had written his own algorithm for a computer to play chess. However, at that time there wasn’t a general-purpose computer that could be programmed to run it – nor the finance to manufacture one purely to play the game – so he demonstrated it by hand. Working with a friend, Turing played a game of chess and assumed the role of the algorithm, computing its moves by hand. The ‘computer’ lost in 39 moves, but it wasn’t a bad effort!
But why Chess? Well, it seems, or seemed too early for AI researchers, to encapsulate the core of thinking. It seemed like you would need to be intelligent to play Chess, so it was a good problem to work on.
Chess is a game of long-term planning and predicting the moves of your adversary, so it’s been a great test-bed for AI research. Being able to anticipate what’s going to happen 5,10,20 moves from now and comparing possible outcomes, balancing their risk and reward. It’s pretty difficult even for most humans.
The algorithm behind most Chess-playing programs is the Minimax algorithm. It works by simulating all the possible actions for the white player, and for each of the resulting board positions simulatess all moves for the black player, and so on for a number of steps. Then you assume that white wants to maximize the value of their board, and black wants to minimize it – from the perspective of the white player, that is. If you had infinite time, you could calculate the optimal way of playing this way. But in practice, when you don’t have infinite time, you have to add variously.
Chess was core to AI research until 1996 when IBM presented Deep Blue, the world’s best Chess computer. Deep Blue was a massive effort, led by Murray Campbell who is himself an accomplished Chess player, which in addition to the Minimax algorithm included tons of domain knowledge about the game.
In a highly publicized set of matches, Deep Blue won over Garry Kasparov, the reigning world champion of Chess. That a computer had beaten the best human at Chess made computer scientists, philosophers, and commentators wonder if we had truly achieved a major breakthrough in AI. But at the end of the day, this was but a formative first step in a much larger journey.
Why is this? Well fundamentally, Deep Blue is great at Chess, but that’s all it is good at. It can’t play other games, or do other tasks of different forms, that we might expect of a general intelligence system. Also, despite its complexity, Chess is still kind of simple. It has perfect information – meaning we can see the entire board – and it’s deterministic, so we always know the outcome of any move we make. It’s a demanding game for sure, but for AI there are bigger challenges, and different kinds of challenges, out there.
Chess is but one of many games that have had a big impact on artificial intelligence development. So be sure to stick around for more episodes of our History of AI series, to find out which of your favourites have had an impact on the field.