The intelligent gamer. (Looking toward the future) David Levy.
The decade 1974-84 was notable for a number of giant leaps in the field of Artificial Intelligence, not the least of which has been in computerized game playing. It has long been recognized that writing a program to outthink a strong human player at a skillful game, such as chess, would take mankind further along the road towards producing a totally artificial intellect.
The very idea of a genuinely "intelligent" computer program conjures up disbelief in many minds, yet those same minds would not dispute the fact that human chess masters are intelligent. It must surely follow that a program that outperforms a human at an activity requiring intelligence is itself exhibiting intelligence. This philosophical argument is one of many reasons that there has been considerable interest during the past decade in the programming of "intelligent" games.
Amongst the games which require intelligence to play and which have been successfully programmed on computers, I shall single out three: backgammon, reversi (also known as Othello), and chess. I feel that these three games provide a representative spread between tasks which require far more subtle methods and heuristics. Backgammon is not a game of pure skill. The player decides which men to move, but his decisions are constrained by the roll of the dice. Expert backgammon players play largely "With the odds," which means that they usually know which particular play is most likely to work out best over a very large number of games. Armed with this type of knowledge and/or intuition, a strong backgammon player will normally fleece a weaker player over a long playing session, even though the dice may present a large element of luck in any one game.
There has been considerable research into the mathematics of backgammon, including various studies into the optimal uses of the doubling cube, and the results of this research have been tabulated. A good backgammon program must possess the result of this tabulated information, as well as a sophisticated evaluation function for dealings with less specific situations.
Dr. Hans Berliner, working in the Computer Science Department at Carnegie Mellon University, is not only a former world champion at Correspondence Chess, he is also the author of the world's strongest backgammon program. In July 1979, Berliner's program, BKG 9.8, beat the reigning World Champion, Luigi Villa of Italy, in a $5000 winner-take-all match in Monte Carlo. The score in the match was an amazing seve games to one.
Berliner admits that the program was luckier than Villa when rolling the dice, but even so, such a score against a world champion cannot be attributed entirely to good luck. This was the first time in history that a computer program had won against a human world champion in a game in which good play require intelligence. Berliner's program clearly exhigbits some intelligence ine the way it plays, although this is limited by the fact that many of the decisions made by it are based on nothing more than a table lookup. Reversi
The game of reversi (also known as Othello) is, on the other hand, a game of pure skill, though it lags far behind chess as an intellectual challenge. It was improved in late 19th century England, but did not become popular until around 1970 when it was renamed Othello by a Japanese gentleman, who has since made a small fortune from licensing the rights to the game.
The rules of revesi are simple enough to be learned by a child in less than two minutes, yet the game is sufficiently deep and complex in nature to be on a par with checkers. Suffice it to say that one cannot play reversi by looking up the right move in a table. The game requires most of the attributes of a strong chess player, including analytical skill and intuition.
Reversi is an ideal game to program because of the simplicity of its rules, and many computer enthusiasts have written reversi programs, some of which play rather well. Since 1981 they have even been winning games from time to time against the world's strongest human players. The first time this happened was during a man vs. machine Othello tournament held at Northwestern University on June 19, 1981.
On that day a program called The Moor, written in my company in London, won a tournament game against the reigning World Champion, Hiroshi Inoue of Japan. This was the first time a reigning human world champion had lost to a computer program in a game of pure skill, and subsequently The Moor thrashed the 1981 British Champion, Neil Cosel, by the amazing score of 61 to 2, which is about as easy as my winning Boby Fischer's queen in a chess game. Chess
Chess and Go are the most profound of all games of skill, and it has long been one of the fundamental aims of A.I. researchers to produce a chess program that can play as well as a world champion. During the past decade there has been a notable improvement in the standard of the best chess programs, but they are still not yet near world championship caliber.
In 1974, at the time of the first World Computer Chess Championships in Stockholm, the strongest programs were Chess 4.0, written at Northwestern University, and Kaissa from the U.S.S.R. Both of these programs played at just above the 1600 level on the U.S. Chess Federation rating scale (Masters are rated 2200 and above; most Grandmasters are 2500 or above; Bobby Fischer was 2780 when he retired).
Four years later, in August 1978, I successfully defended a bet I had made in 1968, in which I had asserted that no computer program would win a match against me within ten years. My opponent in the key match was the latest version of the Northwestern program, Chess 4.m, with a playing strength of around 1850.
Now, in 1984, we have a computer program with a Master rating. Ken Thompson's chess machine Belle, which was designed at the Bell Telephone Labs in Murray Hill, NJ, became the first program to attain the rank of U.S. Master when it achieved a 2203 rating in September 1983. From the standpoint of the professional chess player this is still a far cry from the likes of Bobby Fischer, but it is strong enough that the man in the street would not be able to tell the difference. Both Belle and the current World Computer Champion, Cray Blitz, have beaten players rated over 2300 in tournament games. Furthermore, in blitz chess, where each player moves so quickly that tactical oversights are common, the best computer programs have defeated International Masters and Grandmasters on a number of occasions. Chess 4.7 once defeated Robert Hubner of West Germany in a blitz game at a time when Hubner was one of the world's top 10 ranked players. If they can already perform at that level in blitz games, it can be only a matter of time before the strongest chess programs are vying with human world champions under tournament conditions. The Future
What about the future? I shall stick my neck out and predict that by the time of Creative Computing's 20th anniversary issue, the following events will have taken place:
* A computer program will have won a tournament chess game against a Grandmaster.
* A program will have the ability to play Bridge as well as a strong club player.
* No program will be able to play Go at anything above beginner level.
* Fewer that 1% of personal computer owners, when playing their favorite game of skill, will be able to beat the strongest micro-based comptuer programs.