The unwinnable game
- 24 November 2013
- From the section Magazine
Two humans - one Norwegian and one Indian - have been competing for the World Chess Championship. Neither of them would fancy their chances against the best computers. The machines have come a long way and their progress has taken us closer to achieving artificial intelligence.
In 1968 chess master David Levy made a bet that by 1978 no computer could beat him in a series of games. He won the bet.
In fact, it took most of the 1980s before he was finally beaten. "After I won the first bout, I made a second bet for a period of five years. I stopped betting after that. At that point I could see what was coming."
In 1997, the best player in the world Garry Kasparov was beaten by the IBM computer Deep Blue in a controversial series.
Today, the world's best player Magnus Carlsen would be foolish to make a Levy-style bet. The best computers would beat him.
But the progress that computers have made against one task - beating the best humans at chess - offers a lesson for the whole way people think about the future of artificial intelligence.
The man who coined the term "artificial intelligence" - the American scientist John McCarthy - identified early on that chess matches, and other complex games, were a good way of testing the progress of machines.
"One has an absolute measure and target to beat," says Levy. "In many games, there are rating systems - we can have an object measure. For all these reasons, games are a very good vehicle for AI. Playing a game requires a combination of skills, including intelligence."
McCarthy oversaw the creation of the first chess programme to play convincingly. By 1962 the programme - Kotok-McCarthy - was as good as a mediocre human. But it later lost the first match between computers when pitted against a Soviet rival.
That match spawned a tradition of computer v computer battles that eventually led to the World Computer Chess Championship. For 40 years, programmers have been doing battle against other programmers. A film comedy released in the UK this week, Computer Chess, uses these singular contests as its backdrop.
It's not just chess. In 2007, a team led by Jonathan Schaeffer at the University of Alberta "solved" draughts. That is, it was worked out that if both sides played perfectly, the result had to be a draw. It had taken 18 years of computer calculation.
For fans of the games that have been mastered by computers there can be an occasional nostalgic longing for the pre-machine age.
A commentator in the current Carlsen-Anand series used the phrase: "A very human move." The point is that humans make mistakes. The subtlest of mistakes, the "sub-optimal" moves, can create beautifully poised situations.
And the bad mistakes committed by the best humans - as with missed open goals in football - provide light relief for lesser mortals. Former world champion Vladimir Kramnik committed one of the most famous blunders in chess, while playing a series against a computer in 2006, missing an obvious checkmate. It was the kind of mistake that a parent would have been disappointed at their novice eight-year-old committing.
Computers offer no such fun.
Their triumph led programmer Omar Syed to try and come up with a game where computers would be at an inherent disadvantage against humans.
"When Deep Blue won, I felt sorry for Kasparov. I knew what an incredible mind he had. But he was not able to outdo a computer."
Syed created Arimaa, a game using pieces similar to those used in chess but moving in a simpler fashion and set up on the board in a pattern decided by the player. Its creation wasn't easy.
"Whenever you make the game more difficult for computers, it gets more difficult for humans," notes Syed.
But he eventually cracked it. "If you use simple movements, we could increase the branching factor and still keep the game easy enough for humans."
In keeping with the traditions of AI buffs, he made a bet that a computer could not beat the best Arimaa players. January will see the 10th year of the competition and computers haven't come near to winning. But by 2020, Syed predicts the machines will have the upper hand.
The reason is the same as their triumph in chess - "brute-force calculation".
Computers approach a game in a different way to a human. A typical chess - or draughts, or Reversi, or Go, or Shogi - master may "feel" a particular move is right and then test it in his head, looking several moves ahead.
But the human can do nothing against a computer that has the power to look at even "wrong" moves and then test what would happen dozens of further moves into the future.
"Humans don't like to look very deeply forward but they have this innate sense without working out the fine detail," says Syed, who now works at Hedgechatter, creating software that uses AI to gauge social media sentiment about share prices.
Computers didn't win by "learning" to play chess like humans. They won because their calculating power increased exponentially.
This was something that pleased McCarthy, remembers Levy.
"If one can solve a problem like chess in a completely different way to humans, one has achieved something. It doesn't matter how the computer does it."
Now there is a greater target than winning at board games. The Loebner Prize is awarded to the programme that can best have a conversation with a human. David Levy, also an AI expert, has won twice.
"That's the most difficult task remaining in AI for all sorts of reasons. There is so much that's involved in understanding what we say to each other."
Most humans aren't consciously aware of it, but the average conversation is an extraordinary verbal and non-verbal symphony comprising body language, tone, emotion, double meaning, humour, historical references and sundry other intricacies.
How would a computer know when it's generally polite to interrupt?
But Levy - author of Love and Sex with Robots - thinks it will be mastered.
We will reach a point where computers can have convincing conversations with humans, he believes. In certain circumstances, that could even lead to cheating.
Just as there have been cases where humans have been accused of communicating with computers to win at chess, so humans might one day conceivably cheat in an interview. "That's something that will happen in all sorts of walks of life," says Levy.
With hindsight, getting a computer to win at chess was easy. But getting one to make up a funny anecdote will be a mindboggling achievement.