Beating us at our own game – can we take the Risk with AI gamers?
Tuesday 28th June 2016
Could you outmanoeuvre a computer? Mathematician, recent winner of the JOSH Award and game enthusiast Katie Steckles investigates the latest developments in the slightly scary world of AI Gaming.
One of the first games playable against a computer, in 1952, ran on EDSAC (the Electronic Delay Storage Automatic Calculator) and was called OXO, or Noughts and Crosses. The game’s output was displayed on an oscilloscope, and the input used a rotary telephone dial to select a square.
The computer could play a ‘perfect’ game – one in which every move is optimal. OXO could only be played in the University of Cambridge’s Mathematical Laboratory by special permission, as EDSAC could not be moved and it was only intended for academic research purposes – but it was the start of a long tradition of people teaching computers to think like a gamer.
One example is chess. Human chess players try to think ten moves ahead of the current situation, and in an average chess setup, there are around 30 possible moves from each position – so to truly think 10 steps ahead would require analysing around 3010 = 590,490,000,000,000 combinations. Early computers would not be capable of processing this many positions, especially given the time limits on tournament games.
In the late 1970s the first computers started beating human players and winning tournaments. While they made fewer errors than humans did, computers still weren’t able to beat the absolute top world champion human chess players – until 1996, when IBM’s Deep Blue famously defeated world champion Gary Kasparov. More recently, the challenge has been to make the programs more compact – in 2009, a chess program running on an HTC mobile phone achieved Grandmaster level in tournament conditions.
While chess is undoubtedly difficult, some would consider the ultimate challenge for a computer to be the ancient Chinese board game Go. A deeply abstract game of strategy, for a while Go was distinguished from chess in that nobody had come up with a satisfactory Go AI. That all changed earlier this year, when Google’s DeepMind project, and its Go-playing software AlphaGo, successfully won a series of games against the world champion human player, Lee Sedol.
Go has simple rules, but very complex gameplay – you take it in turns to place stones on the crossings of a square grid, and try to capture regions of the board by surrounding groups of stones. Since the grid has 19 x 19 crossings, the number of possible positions in the game is immense – so it’s much more difficult to pick the smartest moves by thinking ahead.
Experts had previously thought that it would take another ten years of development for computers to get good enough at the game to beat a human, but apparently all it took was the terrifying computational power of Google.
So what’s next? A robotic tiddlywinks champion? Computer poker players, with mechanical eyebrows to raise in order to bluff about how good their hand is? Let’s just not teach an AI to play Risk, in case they get any ideas about actually taking over the world…
About Katie Steckles
“Her mathematical passion is only equalled by her knowledge and her clever demonstrations” – Cheltenham Science Festival 2015 brochure
“Like Ghostbusters, but for maths” – BBC Radio Manchester
Katie Steckles is a mathematician based in Manchester, who gives talks and workshops on different areas of maths. She finished her PhD in 2011, and since then has talked about maths in schools, at science festivals, on BBC radio, at music festivals, as part of theatre shows and on the internet. She enjoys doing puzzles, solving the Rubik’s cube and baking things shaped like maths.
In 2016, Katie was awarded the Joshua Phillips Award for Innovation in Science Engagement, which means Katie is the official Science Communicator in Residence for the 2016 Manchester Science Festival, and will be running a large-scale public engagement event as part of the festival.