Sunday 6 January 2013

Computer chess and human error

When I was a teenager I was a keen chess player, and when I discovered the joys of programming a computer I was naturally interested in how computers could be programmed to play chess.  This was in the days before PCs, the mid 1970s, when computer time was a rare resource, and when the possibility that a computer could beat a good human chess player seemed at best a long way away.

It was also a time when the less perspicacious of us, like me, believed that playing chess was a serious test of computer power; a demanding human activity which was a pinnacle of intelligence.  Now, of course, we realise how much more difficult it is to programme a machine to recognise faces or interpret speech or read handwriting, and other activities which are very difficult for a computer but which human beings do automatically.  (Well, I am embarrassingly bad at recognising faces, as it happens!)  Of course, in his seminal paper 'Computing Machinery and Intelligence' Alan Turing had actually included solving a chess problem as a suitable task for a potentially intelligent computer, but he had, with is usual perceptiveness, also included writing poetry.

Anyway, in the 1970s we seemed a long way away from computers being able to play chess at the top human level.  Indeed, the Scottish chess player David Levy made, and won, a series of bets against proponents of computer chess at the time that no computer could beat him.

I was delighted when I found in the university library Alex Bell's book The machine plays chess? (1978), which was a very entertaining account of our attempts to get computers to play chess.

I remember his hilarious account of an early programme, which (playing against a weak human opponent) got into a wining position.  The opponent wanted to resign when the computer got to an ending with king and two queens against king but the programmers insisted the game be played out to its conclusion.  Unfortunately, the simple way to force mate was slightly too long for the computer to calculate, so, knowing that pieces are most powerful in the centre, it moved its queens to the centre of the board.  Its strategy was essentially to keep its queens in the centre, but it knew about draws by repetition of position, so as the game continued the computer's queens gradually spiralled away from the centre, but failed to progress towards a mate.

Bell's book was very funny, and full of lessons and entertainment for any aspiring programmer, but growing computer power meant that humans were no longer unbeatable.  First, a computer beat the backgammon world champion, albeit with a huge amount of luck, and eventually in 1997 the computer Deep Blue beat the great Garry Kasparov in a best-of-six-games chess match.

Having enjoyed Bell's book so much, I was fascinated to read in Nate Silver's recent book about mathematical predictions, The signal and the noise, an account of Kasparov's defeat which presents Deep Blue's triumph as the result of a programming error!  Kasparov won the first game, but was puzzled when, in a losing position, Deep Blue chose what appeared to be an inferior move, rather than one which would seem to have held off defeat for longer.  According to Silver, Kasparov tried to work out Deep Blue's logic, and concluded that the computer was looking so far ahead that it could see that the "better" move lost just as badly as the "inferior" one.

In the second game, Deep Blue had a slight advantage.  At a key point, it could either play a move which would lead to a complex tactical situation - which one would expect to favour the computer - or one which led to a simpler game in which Deep Blue had an edge which might not be sufficient to force a win.  To everyone's surprise, it chose the latter.  In fact Kasparov had the opportunity to force a draw, but missed it.  It seems that, knowing from the first game how far ahead Deep Blue was calculating, Kasparov assumed that there could not possibly be a way for him to draw, or Deep Blue would have played the other move.  Since he assumed the game was lost, inevitably he missed the draw.

Demoralised by this defeat in the second game, Kasparov then blundered in the final game and lost the match by 3.5 to 2.5.

But according to Silver, Deep Blue's choice of losing move in the first game wasn't due to its seeing a long way ahead.  It was due to a programming error!  So Kasparov's attributed the move to deep analysis when in fact it was a simple bug in Deep Blue's programme, and this mistaken analysis of Deep Blue's abilities led Kasparov to defeat in the match.  Rather than being the triumph of the infallible calculating machine, Deep Blue's victory was due to Kasparov's very human response to a computer error!

As always, there is more to both human and artificial intelligence than a strict logical analysis appears to suggest!

No comments:

Post a Comment