E.U. and Computer Chess

The Bet

Cocktail time, a break from the discussions of programs, technical analysis, lectures . . . downtime, as the computer men call it ; Whatever the machines do, the human practitioners of artificiai intelligence, gathered here for a seminar at Edinburgh University, could use a drink.

'Care for a game?' inquired John McCarthy pleasantly, over the sherry. He knew, of course, that David Levy, as Scottish Champion, was a good player, a league or two above him. But as one of the world's experts in artificial intelligence whose work at Stanford was known throughout the field, McCarthy was not exactly a slouch at mental calculation either. But chess, of course, is one of those games where the difference in playing ability between even a quite good player and a master more or less rules out a serious contest, anyway for the better player, as Levy was well aware . McCarthy, as an enthusiastic amateur, was wiped out.

'Okay, okay,' he smiled, taking his defeat lightly. 'But I'll tell you something! In the next ten years there'll be a computer which will beat you very easily and beat you regularly.'

'Oh yeah,' said Levy. This was in the autumn of 1969.

'Yeah Believe me, David, I may not know too much about chess, but I know what these machines are capable of doing!'

Levy, in those days a brash and bright young man at the start of his career, more interested in chess than in maths, thought otherwise.

'Listen, I don't want to boast but I do happen to be national champion in Scotland. It just isn't conceivable that you can design a program strong enough to beat players like me.'

'We surely will,' McCarthy reiterated He had no doubts about his own theoretical expertise to back up hls claim.

Levy, fond of poker as well as chess, suggested a modest wager on the outcome. They agreed on a bet of £ 500 that McCarthy could not produce a machine which could beat Levy over the board, under tournament conditions, within ten years. At that time when Levy's annual salary was about £ 1,000 this was quite a substantial sum. They shook hands on it. And that was how the great computer wager came about.

One or two other people, cognoscenti of computers, wanted a piece of the action as well. The head of the Depart ment of Machine Intelligence and Perception at Edinburgh, Professor Donald Michie, opined that David Levy had completely misjudged the state of the art. He wanted to take half of the bet. At a seminar the following year when Levy was on the platform, Seymour Papert from MIT, the author of Mind Storrns, began to heckle Levy from the audience. When Levy invited him to put his money where his mouth was, Papert responded by offering to reduce the period in which the new program would be written to five years. Levy retorted that that would be unfair to his challenger and gave him another £ 250 on the same terms.

News of the wager spread around the academic community and, at a computer chess tournament in Chicago in 1971, Ed Kozdrowicki from the University of California was so sure of his ground that he bet another S1,000. Levy felt he was in far enough, so he bet £ 250 and another academic took the balance. He still thought his bet was safe.

The man who took Levy's side in sharing Kozdrowicki's bet was Ben Mittman of Northwestern University. So not all the experts were so convinced that their technology would prove superior to the a human mind. When they happened to meet again some time later, at a party given by Mittman, Michie told him he wanted to increase his original bet. Levy thought Michie must have got sunstroke, but with the bet now due to be completed in only four years' time, he had no compunction about taking the risk. His total wager had now risen to well over his annual salary when he started.

The Man

Levy had no special aptitude for chess as a child. After learning the game as an eight-year-old he did not become really interested in it until he was eleven. But then the bug got him. He began playing every day at school and started entering competitions. After a variety of minor successes in county championships he was selected to play for England at eighteen. Then he moved on to St Andrews University to study maths and physics. Living in Scotland he became eligible for the national team and played in the student olympiad in Romania. Chess suddenly seemed to open new vistas - foreign travel, minor celebrity, possibly financial rewards.

In 1968 he became Scottish Champion and played in the olympiad in Switzerland. As a result of his standing in Scotland, though the - standard was lower than in England, he was given a place in the Zonal Tournament in Portugal. He almost did not take it, having to pay his own expenses, but the trip was a chance to see a new country. And this light-hearted attitude, backed by considerable preparation in the openings, stood him in good stead: he went through the tournament unbeaten and defeated a number of players who were, in reality, better than him. This result gave him the International Master title, at the time the best performance by a British player for some years.

It was an obvious step on leaving university at St Andrews to make a career in computers. He travelled a good deal to chess I tournaments, wrote a lot and played a lot. By now his bet had given him something of a reputation in academic circles and he was invited to organise several computer tournaments in the US and elsewhere.

The next step was to develop a computer program to be sold commercially. He worked as a consultant to Texas Instruments and left academia behind.

The Computer

It was David Slate, one of the programmers of CHESS 4.6, who devoted some six months' work to the program being prepared at Northwestern University to challenge Levy. The predecessor of this machine, CHESS 4.5, was good enough to beat a number of masters, including Levy, at blitz chess, a game where the moves are played fast, like five-minute games, or each player having to make a move every five seconds. As Botvinnik had noted, in lightning chess the strength of a master is considerably reduced, but that of the computer only marginally so, because a reduction in the computer's breadth of performance in examining its millions of positions reduces only slightly the depth of moves in its search.

The new Northwestern program CHESS 4.7 (CHESS 5.0 was not ready), run on a powerful Control Data Corporation Cyber 176 computer, the fastest available commercially, represented a further advance on its predecessors and was stronger, so Levy declared, than 99.5 per cent of all the world's chess players.

As a poker player, Levy was not averse to covenng his bet. Interest in the match had spread so widely through articles in the press and so on, that the Canadian National Exhibition offered to sponsor him in playing the event in Toronto. Financial considerations apart, it was highly advantageous to Levy's burgeoning career to play the match in a blaze of publicity. And sceptical as he was about the scientists' claims, he was surprised by the advances which chess programs had made before the bet fell due.

For instance, by 'thinking' in its opponent's time, so that it could examine more variations, and running on more powerful computers, a machine could look at three million positions before making each move.

Programs do not of course 'think': they perform a set of instructions. The principles on which they operate give them a different l and distinctive style of play, with its own strengths and weaknesses. It was this fact, in effect a psychological observation, that was at the core of Levy's confidence. Levy intended to play in a style which exploited the machine's weaknesses - poker again.

The Tactics

Computer programs don't have feelings, but their programmers and their opponents do tend to regard them as having almost human moods. That is why they refer to them sometimes as 'he'. And certain tendencies repeat themselves - for instance, Levy had noted that in the standard version of the Sicilian where White has a knight on d4 and Black a knight at c6, whereas a master does not go for the exchange because Black can counter-attack along the b-file, the Northwestern program usually did, because in doing so Black is left with an isolated a-pawn which it 'knows' is a bad thing. What it did not know was that in the Sicilian, Black's isolated rook's pawn does not matter, but having a pawn majority in the centre does. Levy, by making an inferior move in the opening, could tempt the computer to make this exchange, giving him the kind of position he wanted.

Playing the 'man' rather than the board? Yes, he treated the computer like a human opponent who was rigid in certain respects. Human is not quite the right word; as Levy describes it, it was more like a dog or a cat. 'Look at this move it played, such a nice move! What a clever boy!' The responses from the machine, some of which send out messages saying 'Be careful' or 'That was easy', do create a sort of empathy. Some players, even good ones, become very nervous; the machine, however, does not suffer from nerves. Chess can be divided into strategy and tactics. The best programs are excellent tacticians. Their calculating ability gives them an obvious superiority over most humans. They are less adept at evaluating positions and according to Levy do not plan at all. His own tactic, therefore, was to avoid tactics. 'Thus the strategy I adopt is to do nothing. But I do it very carefully. Sooner or later the program will dig its own grave.' So far as tactics were concerned, Levy favoured making a bizarre early move to 'confuse' the program and take it out of the book openings programmed into it. Subtle stuff! In other words, as George Steiner put it in White Knights of Reykjavik, the interactions between immediate perception and stored knowledge are themselves complex and inventive beyond anything reproducible in computers, with their yes-no logic and essentially static memory banks. 'Such key concepts as "advantage", "sound sacri fice", and "simplification by exchange", on which the choice of moves will depend, are far too indeterminate, far too subjective and historically fluid to be rigorously defined and formalized. The idea of "the one optimal move" is, in all but the most elementary or nearly final positions, a crude simplification.' Many celebrated positions and decisions in the history of master play remain disputed and unfathomed to this day, he avers. 'The vital parameters of psychological bluff, of time pressure, of positional "feel", of tactics based on a reading of the opponent's personality largely elude formal notation and judgement. They belong to the unbounded exactitudes of art.'

The Match

To add to the drama of the occasion, Levy wore a dinner jacket for the match, sitting in a glass booth under television cameras. The program was run from its computer in Minnesota via an open telephone line. A specially designed electronic board registered Levy's moves by means of a number of magnetic-sensitive switches located between the squares. When CHESS 4.7 was ready to reply it would switch on the lights on the 'from' square and the 'to' square to show the path of the moving piece.

In the opening game, Levy got into very serious trouble. He underestimated a knight sacrifice, which gave the program the opportunity of developing a very strong attack. As mentioned earlier, sacrifices are the hardest concepts for programs to carry out successfully, because the advantage gained, instead of being in the form of material, is usually positional. Levy saw the sacrifice but thought it was completely unsound and accepted the offer. But the program replied with a crushing blow and then sent him the laconic message, 'That was easy.' At this point the program was in a commanding position. 'My God, this thing is beating me!' Levy thought.

By move 30, three pawns down for his minor piece and his king naked to the winds, White somewhat resembled King Lear on the blasted heath, if that is not putting it too tragically. However, Levy kept his nerve. He managed to finagle back a pawn, then a second one; his position improved from being totally lost to merely hope- less; then he got a third pawn. By move 54 White had re-achieved, at long last, what he started out with on move 1, material equality

Levy had just played 55 b7 ! at which critical point in the proceed- ings the computer had a malfunction and its medical advisers were called in. Twenty-five minutes later, with the program still having plenty of time on its clock it played 55 ... Nxe7! - in Levy's judgement, 'a brilliant decision'. It is probably the only way for Black to draw.

56 dxe7 Rh8! (on . . . 56 Re8 57 Ba5 White wins) 57 Bd6 Kf6 58 b8=Q Rxb8 59 Bxb8 Kxe7 60 Bf4 Kf6 61 Bd2 Kg6 62 Bel Kg5 63 Bf2 Kh5 64 Bel. And David Slate on behalf of the program offered a draw. A remarkable and exciting game and one in which the computer found several moves far beyond the present author's capability.

The next day saw game two of the match. And here Levy as Black contrived to set the program more difficult problems in the opening by going out of the book and then tempting it to exchange knights on move 8 in the Sicilian, in the unstrategic way described earlier. After making this error the year before, the program had been modified in an attempt to prevent it exchanging in such a situation. But the basic tendency evidently remained in the works. By move 18 Levy had an easily won game. Came the third game when Levy chose the English and managed to go out of the book on move 2. Again, the program made an unwise knight swop, which, for the apparent gain of isolating its opponent's a-pawn, lost it the central pawn majority. It was comparatively easy for Levy to transpose quite early into the ending, confident that the program's weakened pawn structure compromised its position. He secured a passed pawn and marched to victory with some ease.

So, leading by 2.5 to 0.5 humankind's gallant representative only needed a half point from the remaining three games to win his bet.

But the match was not over yet. Having demonstrated that his do-nothing strategy worked, Levy decided to experiment in game four by taking on the program at its own game, playing sharp, tactical chess, and trying to out-analyse it.

As Black, he played the risky Latvian Counter-Gambit which gave the program a pawn, followed by an early exchange of queens and a cut-and-thrust middle game. Levy conjured up a fast attack with doubled rooks down the h-file, but failed to spot all the defensive resources open to the program. It neatly repulsed the attack and then built up a pawn roller on the king's side. Levy seemed once or twice to be on the verge of achieving a winning position, or at least to have convinced himself he could hold the draw. Then he blundered by the kind of mistake which humans under pressure tend to make (Diagram 2).

'The final blunder. I had still not noticed White's next move and assumed that the program was going to play 48 Bxc5 +, when either 48 . . . bxc5 or 48 . . . Kxd8 49 Bd4 (of course Bxb6 is also possible, but the program would be expected to go after the g-pawn in order to add to its passed pawns) 49 . . . Rxa2 50 Bxg7 would produce the unbalanced type of endgame at which the program fares less well due to its inferior understanding of passed pawns.

After 47 . . . Kf7 I don't think the program could have won.'

But 48 Bh4+ ! settled it. 48 . . . Kf7 49 g5 g6 50 Rd7+ Kf8 51 fxg6 Rxa2 52 f5 Ra3+ 53 Kg4 Ra4+ 55 Kh5 Rd4 56 Rc7 Be7 and Black resigned. This was the first occasion on which a computer program defeated a master in a serious game, though it must be admitted that Levy's performance was below par for a player of his rank.

In the fifth game, Levy reverted to his no-nonsense approach. Again he went out of the book very early, playing an English opening, tempted the program to exchange a centre pawn for a wing pawn, and rapidly achieved a strategically won game. The computer broke down again, but despite leaving itself only twenty minutes for thirteen moves to the time control, managed to find the best defensive moves, in an inferior position. Levy had no trouble in transposing into an easily won end game, when CHESS 4.7 had yet another breakdown (psychosomatic?). It was all over. David Slate decided to resign the game and with it the match.

Source: 'Total Chess' by David Spanier