Belle (chess machine)
   HOME

TheInfoList



OR:

Belle was a
chess computer Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
developed by
Joe Condon Joe Condon (born 1940 in Waterford, Ireland) is an Irish retired sportsperson. He played hurling with his local club Erin's Own and was a member of the Waterford "Waterford remains the untaken city" , mapsize = 220px , ...
(hardware) and
Ken Thompson Kenneth Lane Thompson (born February 4, 1943) is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programmi ...
(software) at
Bell Labs Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial Research and development, research and scientific developm ...
. In 1983, it was the first machine to achieve master-level play, with a USCF
rating A rating is an evaluation or assessment of something, in terms of quality, quantity, or some combination of both. Rating or ratings may also refer to: Business and economics * Credit rating, estimating the credit worthiness of an individual, c ...
of 2250. It won the ACM
North American Computer Chess Championship The North American Computer Chess Championship was a computer chess championship held from 1970 to 1994. It was organised by the Association for Computing Machinery and by Monty Newborn, Professor of Computer Science at McGill University. It was one ...
five times and the 1980
World Computer Chess Championship World Computer Chess Championship (WCCC) is an event held periodically since 1974 where computer chess engines compete against each other. The event is organized by the International Computer Games Association. It is often held in conjunction with ...
. It was the first system to win using specialized chess hardware. In its final incarnation, Belle used an
LSI-11 The PDP-11 is a series of 16-bit minicomputers sold by Digital Equipment Corporation (DEC) from 1970 into the 1990s, one of a set of products in the Programmed Data Processor (PDP) series. In total, around 600,000 PDP-11s of all models were sold, ...
general-purpose
computer A computer is a machine that can be programmed to Execution (computing), carry out sequences of arithmetic or logical operations (computation) automatically. Modern digital electronic computers can perform generic sets of operations known as C ...
to coordinate its chess hardware. There were three custom
boards Board or Boards may refer to: Flat surface * Lumber, or other rigid material, milled or sawn flat ** Plank (wood) ** Cutting board ** Sounding board, of a musical instrument * Cardboard (paper product) * Paperboard * Fiberboard ** Hardboard, a t ...
for move generation, four custom boards for position evaluation, and a microcode implementation of
alpha-beta pruning Alphabeta is an Israeli musical group. Alphabeta or Alpha Beta may also refer to: *The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters *Alpha Beta, a former chain of Californian supermarkets *Alpha and beta anomers ...
. The computer also had one megabyte of
memory Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
for storing
transposition table {{no footnotes, date=November 2017 A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the ...
s. At the end of its career, Belle was donated to the
Smithsonian Institution The Smithsonian Institution ( ), or simply the Smithsonian, is a group of museums and education and research centers, the largest such complex in the world, created by the U.S. government "for the increase and diffusion of knowledge". Founded ...
. The overall architecture of Belle was used for the initial designs of ChipTest, the progenitor of
IBM Deep Blue Deep Blue was a chess-playing expert system run on a unique purpose-built IBM supercomputer. It was the first computer to win a game, and the first to win a match, against a reigning world champion under regular time controls. Developmen ...
.


Origins

Following his work on the
Unix Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, an ...
operating system, Ken Thompson turned his attention to computer chess. In summer 1972, he began work on a program for the PDP-11, which would eventually become Belle. In competition, this early version encouraged Thompson to pursue a brute-force approach when designing Belle's hardware.Frey 1983 p. 202.


Design

Belle's design underwent many changes throughout its lifetime. The initial chess program was rewritten to utilize move-vs-evaluation
quiescence search Quiescence search is an algorithm typically used to extend search at unstable nodes in minimax game trees in game-playing computer programs. It is an extension of the evaluation function to defer evaluation until the position is stable enough ...
and evaluate positions by prioritizing material advantage. Belle also used a
transposition table {{no footnotes, date=November 2017 A transposition table is a cache of previously seen positions, and associated evaluations, in a game tree generated by a computer game playing program. If a position recurs via a different sequence of moves, the ...
to avoid redundant examinations of positions.


Hardware move generator

In 1976, Joe Condon implemented a hardware move generator to be used with software version of Belle on the PDP-11. His design had several steps: # A 6-bit "from"
register Register or registration may refer to: Arts entertainment, and media Music * Register (music), the relative "height" or range of a note, melody, part, instrument, etc. * ''Register'', a 2017 album by Travis Miller * Registration (organ), th ...
searches the board for friendly pieces. # Once a friendly piece is found, a ∆xy move-offset
counter Counter may refer to: Mathematics and computing * Counter machine, a subclass of register machines * Counter (digital), an electronic device, mechanical device, or computer program for counting * Loop counter, the variable that controls the iter ...
provides a bit-code for the move offset, e.g. (2,2) for a
bishop A bishop is an ordained clergy member who is entrusted with a position of authority and oversight in a religious institution. In Christianity, bishops are normally responsible for the governance of dioceses. The role or office of bishop is ca ...
or (2,0) for a
rook Rook (''Corvus frugilegus'') is a bird of the corvid family. Rook or rooks may also refer to: Games *Rook (chess), a piece in chess *Rook (card game), a trick-taking card game Military * Sukhoi Su-25 or Rook, a close air support aircraft * USS ...
. # This offset is combined with the contents of the "from" register and moved to a 6-bit "to" register. These two registers fully describe a potential
move Move may refer to: People * Daniil Move (born 1985), a Russian auto racing driver Brands and enterprises * Move (company), an online real estate company * Move (electronics store), a defunct Australian electronics retailer * Daihatsu Move Go ...
. # A test circuit compares the move to the existing board to determine whether the move is pseudo-legal. If it is, the "from" and "to" registers are output to software. 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 in
check Check or cheque, may refer to: Places * Check, Virginia Arts, entertainment, and media * ''Check'' (film), a 2021 Indian Telugu-language film * ''The Checks'' (episode), a 1996 TV episode of ''Seinfeld'' Games and sports * Check (chess), a thr ...
.


Second generation

Belle's second generation was completed in 1978. It implemented several improvements over its predecessor. * The move generator had its own stack, which it used to store moves, rather than outputting them to software. * A hardware implementation of the position evaluator was added. * A hardware implementation of the transposition memory. 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.Frey 1983 p. 204.


Third generation

Belle's final incarnation was completed in 1980. It consisted of further improvements to the speed of move generation and evaluation. * The move generator now included 64 transmitter and receiver circuits. Each transmitter remembered the piece on its square and potential moves that piece could make. Each receiver detected incoming moves, or threats, from other pieces. Extra circuitry detected castling and
en passant ''En passant'' (, "in passing") is a method of capturing in chess that occurs when a pawn captures a horizontally adjacent enemy pawn that has just made an initial two-square advance. The capturing pawn moves to the square that the enemy paw ...
. * The evaluator could now examine square control, using 64 specialized circuits, as well as
pawn structure In a game of chess, the pawn structure (sometimes known as the pawn skeleton) is the configuration of pawns on the chessboard. Because pawns are the least mobile of the chess pieces, the pawn structure is relatively static and thus plays a large ...
. * The transposition memory was increased to 1 Mb. * Belle's alpha-beta algorithm was now implemented in microcode, controlling the move generator, evaluator, and transposition table. 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.


Career


Early competitions

Ken Thompson's software version of Belle competed in the 1972
U.S. Open Chess Championship The U.S. Open Championship is an open national chess championship that has been held in the United States annually since . History The tournament was originally the championship of the Western Chess Association, and was called the Western Open. ...
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. In a pivotal game against
Chess 4.7 Chess was a pioneering chess program from the 1970s, written by Larry Atkin, David Slate and Keith Gorlen at Northwestern University. Chess ran on Control Data Corporation's line of supercomputers. Work on the program began in 1968 while the a ...
, the runner-up, Belle examined 5,000 positions per second, while Chess 4.7 examined 3,500.


World Championship

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 the
Chaos Chaos or CHAOS may refer to: Arts, entertainment and media Fictional elements * Chaos (''Kinnikuman'') * Chaos (''Sailor Moon'') * Chaos (''Sesame Park'') * Chaos (''Warhammer'') * Chaos, in ''Fabula Nova Crystallis Final Fantasy'' * Cha ...
chess machine. In a tie-breaker for the world-champion title, Belle broke through Chaos's
Alekhine's Defense The Alekhine's Defence is a chess opening that begins with the moves: :1. e4 Nf6 Black tempts White's pawns forward to form a broad , with plans to undermine and attack the white structure later in the spirit of hypermodern defence. White's im ...
and went on to declare checkmate in eight moves, winning the game on move 41. During the game, Belle searched 160,000 positions per second.


Master rating

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.Newborn 1997 p. 92. 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. It managed one more win at the ACM Championships in 1986 before retiring.


Performance analysis

Because of its ability to generate and analyze many chess positions, Belle represented the brute-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 of search 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. This effect has been replicated in self-play experiments with different machines. Beyond 2,000 points, however, Thompson found that improvements leveled off.Newborn 1997 p. 123.


See also

*
Computer chess Computer chess includes both hardware (dedicated computers) and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysi ...
* Glossary of computer chess terms *
Ken Thompson (computer programmer) Kenneth Lane Thompson (born February 4, 1943) is an American pioneer of computer science. Thompson worked at Bell Labs for most of his career where he designed and implemented the original Unix operating system. He also invented the B programmi ...
* Joseph Henry Condon *
Endgame tablebase An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of chess endgame positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysin ...
*
Bell Labs Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial Research and development, research and scientific developm ...
* Pawnless chess endgame#Browne versus BELLE


Notes


References

* * Condon, J.H. and K. Thompson, "Belle Chess Hardware", In ''Advances in Computer Chess 3'' (ed. M.R.B.Clarke), Pergamon Press, 1982.
Computer History Museum
* * * * {{Ken Thompson navbox Chess computers History of chess One-of-a-kind computers