| This article is part of the series on |
| Chess programming |
|---|
 |
Tuning and training algorithms |
Belle is achess computer that was developed byJoe Condon (hardware) andKen Thompson (software) atBell Labs. In 1983, it was the first machine to achievemaster-level play, with aUSCFrating of 2250. It won theACMNorth American Computer Chess Championship five times and the 1980World Computer Chess Championship. It was the first system to win using specialized chess hardware.
In its final incarnation, Belle used anLSI-11 general-purposecomputer to coordinate its chess hardware. There were three customboards for move generation, four custom boards for position evaluation, and amicrocode implementation ofalpha-beta pruning. The computer also had onemegabyte ofmemory for storingtransposition tables.
At the end of its career, Belle was donated to theSmithsonian Institution. The overall architecture of Belle was used for the initial designs ofChipTest, the progenitor ofIBM Deep Blue.[1]
Following his work on theUnix operating system, Ken Thompson turned his attention to computer chess.[2] In summer 1972, he began work on a program for thePDP-11, which would eventually become Belle. In competition, this early version encouraged Thompson to pursue a brute-force approach when designing Belle's hardware.[3]
Belle's design underwent many changes throughout its lifetime. The initial chess program was rewritten to utilize move-vs-evaluationquiescence search and evaluate positions by prioritizingmaterial advantage. Belle also used atransposition table to avoid redundant examinations of positions.[3]
| a | b | c | d | e | f | g | h | ||
| 8 |      | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
In 1976, Joe Condon implemented a hardwaremove generator to be used with software version of Belle on the PDP-11. His design had several steps:
A similar series of steps uses the move generator to test whether the pseudo-legal move is in fact legal. This ensures that the move does not place the moving side incheck.[4]
Belle's second generation was completed in 1978. It implemented several improvements over its predecessor.
These changes reduced the role of the PDP-11 software. Now, the software controlled these three devices and ran the alpha-beta pruning algorithm. The second generation of Belle could search 5,000 positions per second.[5]
Belle's final incarnation was completed in 1980. It consisted of further improvements to the speed of move generation and evaluation.
The third generation of Belle was controlled by an LSI-11 computer. Depending on the stage of the game, it examined 100,000 to 200,000 moves per second.[8]
Ken Thompson's software version of Belle competed in the 1972U.S. Open Chess Championship and the 1973 ACM Computer Chess Championship. Over the next year, Belle played several UCSF games and finished 3-1 in the 1974 ACM Computer Chess Championship.
In 1978, the second generation of Belle competed at the ACM Computer Chess Championships, winning with a perfect four wins in four games.[5] In a pivotal game againstChess 4.7, the runner-up, Belle examined 5,000 positions per second, while Chess 4.7 examined 3,500.[9]
In 1980, the third generation of Belle won the third World Computer Chess Championship in Linz, Austria. After four rounds, it had a score of 3.5 in four games, tied with theChaos chess machine.[10] In a tie-breaker for the world-champion title, Belle broke through Chaos'sAlekhine's Defense and went on to declarecheckmate in eight moves, winning the game on move 41.[11] During the game, Belle searched 160,000 positions per second.[12]
In 1982, theUnited States Customs Service impounded Belle for violating theExport Control Act as Thompson attempted to travel with it to the Soviet Union for a chess exhibition. Thompson said that the computer was made ofcommercial off-the-shelf components, and that its only military use was "to drop it out of an airplane. You might kill somebody that way".[13]
In 1983, Belle competed in the U.S. Open, where it scored 8.5 points in twelve games with a performance rating of 2363. Later that year, the USCF awarded Belle the rank of master.[14] Because it reached this level before any other chess computer, Belle was awarded the $5,000 Fredkin prize. Belle's reign ended when it placed sixth in the Fourth World Computer Chess Championship, despite being the favorite to win.[14] It managed one more win at the ACM Championships in 1986 before retiring.
Because of its ability to generate and analyze many chess positions, Belle represented thebrute-force approach to chess computing. In the late 1970s, Thompson became interested in the limits of this method, playing different versions of Belle against one another. Using identical machines allowed him to minimize effects of the individual machine's play style while isolating the effects ofsearch depth. For instance, if one Belle computer searches three levels deep, the other might search to four. Thompson concluded that for each additional level of search, Belle improved by approximately 250 rating points.[15][16] This effect has been replicated in self-play experiments with different machines.[17] Beyond 2,000 points, however, Thompson found that improvements leveled off.[18]