Forty years ago, the first workers in the field of Artificial Intelligence set out to construct a computer capable of defeating any human being on the planet at the game of chess. Since chess was regarded as the ultimate thinking man's game, many thought that if such a machine could be built, it would prove once and for all that machines could think. It was also thought that this lofty goal could be reached within ten years.
Four decades later two things are clear. First, playing chess at the level of a grand master turned out to be much more difficult than even the pessimists imagined. And second, we now understand that compared with the simple games of a two-year-old, even grandmaster chess is, well, child's play. Seeing a bouncing ball, walking through a door, playing with blocks, singing nursery rhymes: this is where true intelligence lies. Next to these awesome feats, a world class game of chess is no more than the first trembling step of an infant.
Still, it is a stirring challenge. And from the beginning, skeptics sneered and hooted at the idea that a computer could beat a grandmaster.
So the race was on. At first it was difficult just teaching a machine to play at all. (This was well before the days of HyperCard). But gradually, the machines improved. It took eight years before a machine could even follow the rules, and another eight years before a computer could reach the standard of an average player. And seventeen more years passed before a computer reached the master level.
The 80's saw the rise of supercomputers, winning at world computer chess tournaments through sheer brute force. Expensive, corporate-backed machines like Hitech and the Cray Blitz could search through 120,000 possible chess moves per second. Very impressive, but not enough to defeat a grand master.
Then, in 1987, something extraordinary happened. At the North American Computer Chess Championship, all of these mega-machines were blown out of the water by a little box put together by some grad students in their spare time. Less than two years later, grandmaster Bent Larsen, a former contender for the world title, was defeated by this same little box.
An account of this great race including a description of the inner workings of the "little box" is presented by these same grad students in this month's issue of Scientific American. Their creation, which they call "Deep Thought," has not yet attained the ultimate goal of winning the (human) world championship, but it is getting very close!
Included in the article is a blow by blow account of a game played last February between Deep Thought and former world champion Anatoly Karpov (Karpov will be challenging Gary Kasparov again this year for the title). This month's installment of Mr. Wizard gives you a ringside seat.
WHAT IT DOES
Since this is the first installment of Mr. Wizard under the aegis of the new and improved Archipelago 2.0, I thought it might be appropriate to revisit a concept which appeared in the very first Wizard stack: the Looking Glass.
The idea is the same. Instead of trying to visualize a game by reading the transcript, why not conjure up a chess board and animate the pieces step by step?
I have entered the entire transcript of the game, comments and all, into a scrolling field. Every time you push the forward arrow button, my script locates the next move in the transcript, hilites it, and moves the corresponding piece across the chessboard on the right half of the screen. You can reverse the process by pushing the backward arrow, or push the reset button to redraw the board and start over. A comment button displays the bibliographic credits.
The most exciting thing about this stack is that it is general purpose. Type in any transcript you like and the stack will display it. (Actually, to make it fully functional, I need to add handlers for a few special cases that did not come up in this game: Queen side castling, en passant captures, and pawn promotion.) It would be quite easy to expand this stack so that each card displayed a different famous game.
HOW IT WORKS
I'm rather proud of this one. The script inside the forward arrow button finds each move even when it's buried inside a paragraph of commentary, parses it (that is, figures out what it means), and then performs the move on the animated chess board. And yet it took less time to write this script than it took to type in the text of the transcript. The entire stack was finished, debugged, and polished four or five hours after the idea first popped into my head.
Basically, there are three tasks: find the next move, parse it, and display it. This is all made much easier by the fact that chess transcripts, like footnotes, follow a fairly rigid format.
A standard line in a transcript has three columns: the move number, White's move, and Black's move. The move is in the form cr-cr where c is the column (a-h) and r is the row (1-8). Thus d4-d5 means "move the piece located at d4 to position d5".
For added clarity, moves with pieces other than pawns are preceeded by a one letter abbreviation (B for Bishop, N for Knight, R for Rook, Q for Queen, and K for King). And if a piece is captured, the dash is replaced by an x. Thus Bd4xe5 means "The Bishop at d4 takes the piece at e5."
In addition, some moves are followed by punctuation; "?" in the case of a questionable move, "!" or "!!" in the case of a great move. And then, of course, there are oddball moves like castling. And sometimes commentary is inserted between White's move and Black's move (in which case Black's move is preceeded by an elipsis).
All of this is not as bad as it might seem. First, I assume that a move always begins with a move number or an elipsis. This separates the moves from the commentary. As for the move itself, I just strip away everything except the essential five character cr-cr description. A simple formula transforms the row and column formation into an x,y screen coordinate. I can then refer to a given piece as the button at location 240,289.
The essential trick to displaying each move is creating 32 icon type buttons for the pieces and placing them precisely on the screen. Once I had the icons (imported from my HPL library), the creation and placement was accomplished in less than two minutes (Copy-Paste-Shift Drag).
The forward arrow script is made shorter and more elegant through the use of several user-defined functions and handlers placed at the card level. Since I wanted the columns in the transcript to line up, I used a non-proportional font (Monaco 9), and to speed text entry, I placed the following script inside the scrolling text field:
repeat until number of chars
of last line of me > 17
With this script, every time I hit the tab key the computer automatically spaced over to the Black Move column.
And that's about it. Since this is the first card in the new format, I should explain that the "Push Me" button will take you to whatever Wizard stack appears in the card's title, and pressing the "Mr. Wizard" button just below this text field will take you to the Mr. Wizard Archive stack. Next time I will ship an archive with all the cards to date, and from then on it will be up to you to add each new card to your archive by hitting the "Export" button.
So, push the "Push Me" button and study this fascinating contest between man and machine. Enjoy!
It seems inevitable that Deep Thought will soon be pitted against a man some regard as the greatest chess player who ever lived, Gary Kasparov. Mr. Kasparov, who can occasionally be seen on the David Letterman show, is ever defiant. In a private communication with the creators of Deep Thought, Kasparov "acknowledged that a machine searching a billion positions per second might defeat the general run of grandmaster, then added 'But not Karpov and me!'"
The Creators of Deep Thought close their article with the following observation:
"When the two opinions collide over the board, the ingenuity of one supremely talented individual will be pitted against the work of generations of mathematicians, computer scientists, and engineers. We believe that the result will not reveal whether machines can think but rather whether collective human effort can outshine the best achievement of the ablest human beings."