Belle consists of a special-purpose hardware and associated software, and was pure brute-force. Belle started in the early 70s as a sole software approach, but more and more emerged to a hybrid chess computer, next using a move generator, a position evaluator, and a transposition table inside a special-purpose hardware. In its final incarnation, Belle was composed of a PDP-11/23, and further a LSI-11 processor with several custom boards. The speed increased from 200 nps from the software version to about 160,000 nps of the machine mentioned at the Advances in Computer Chess 3 conference in 1981.
The hardware move generator consists of 64 combinatorial circuits similar for each square, controlled by appropriate latches representing the board, and receiving and transmitting signals from/to neighboring squares to propagate piece attacks. Two single wired op-codes, find victim and find aggressor, locate the highest valued piece (including empty square) under attack and the lowest valued piece attacking it in MVV-LVA manner. Move making and unmaking perform incremental updates not only on the piece registers, but also on a Zobrist like 48-bit hashkey and evaluation registers.
Block Diagram
Transmitter (XMIT), receiver (RECV), piece register, and ray- and directionmultiplexer for each square [12]. The opcode (OP) input is either find victim or aggressor. It controls the transmitters and the order of the receiver outputs as input of the two level priority encoding tree.
╔══╗
┌─────────┐ 64 Disable OP 2 PW ┌╢≥1╟═◄ 2 Pawn Move
│ Disable ╞═/═════╣64|1╟───────┐ │ ╔══/═╡╠══╣ 63 other K ┌──┐
│ Memory │ ╔▼═══▼═══▼═╗ └╢≥1╠═◄ 2 Pawn Capt ►═/══════╡ │ check
└─────────┘ 8 N ╔══╗ ╔══════════╗║Ki ╚══╝ │≥1├───────────►
╕ ╒ in ╔══╗╟ ║ 64 * ╟╫────────────────────────►────────┤ │
►═/════╣≥1╟──────►║ ║║(victim / aggressor) └──┘
╛ ╘ ╚══╝ ║ ║║ Queen / Pawn ┌──────────┐
\|/ 8 K ╔══╗ ║ ╟╫────────────────────────►│ │
- - in ╔══╗╟ ║ ║║ Rook / Knight │ │
From /|\ ►═/════╣≥1╟──────►║ RECV ╟╫────────────────────────►│ │ no square
XMIT ╚══╝ ║ PLA ║║ Bishop / Bishop │ ├───────────►
Neighbors 4 Diag ╔══╗ ║ ╟╫────────────────────────►│ Priority │
\ / in ╔══╗╟ ║ ║║ Knight / Rook │ Network │
/ \ ►═/════╣≥1╟──────►║ ╟╫────────────────────────►│ │
╚══╝ ║ ║║ Pawn / Queen │ │
| 4 Man ╔══╗ ║ ╟╫────────────────────────►│ │
- - in ╔══╗╟ ║ ║║ Empty / King │ │ square 6
| ►═/════╣≥1╟──────►║ ╟╫────────────────────────►│ ╞═════════/══►
╚══╝ ║ ║╝ │ │
╚══════════╝ ►════════/══════►│ │
64 * ▲ 63x6 others └──────────┘
╔══════════════╗ ║ |
╔══════════════╗ P4 ║ - - 4 Man in
║Piece Register╠═/══╣ | ►═/══════════╗ From XMIT Neighbors
╚══════════════╝ ║ OP WTM \ / 4 Diag in ║
║ │ │ / \ ►═/══════╗ ║
╔▼═══▼═══▼═╗ ╔═▼═══▼═══╗
╔══════════╗║Manhattan ╔═════════╗║ Man out 4 |
║ 64 * ╟╫─────────►║ 64 * ╠══════════════/═► - - To RECV and XMIT
║ ║║Diagonal ║ RAY ║║ Diag out 4 | Neighbors
║ ╟╫─────────►║ MUX ╠══════════════/═► \ /
║ ║║Empty ║ ║║ / \
║ XMIT ╟╫─────────>║control ║╝ ╕ ╒ To RECV Neighbors
║ ROM ║║Knight ╚═════════╝ N out 8
║ ╟╫───────────────────────┤*8╠════════/═► ╛ ╘
║ ║║King K out 8 \|/
║ ╟╫───────────────────────┤*8╠════════/═► - -
║ ║║ ╔═════════╗ /|\
║ ║║Pawn ╔═════════╗║Pawn Move out 1
║ ╟╝─────────►║ 64 * ╟╫───────────────► |
╚══════════╝ ║ DIR MUX ║║Pawn Capt out 2
WTM──>║control ╟╝─┤*2╠════════/═► \ / or / \
╚═════════╝
Find Victim
Find victim causes each transmitter (XMIT) to activate signals corresponding to the piece of the side to move on each square. Empty squares activate the sliding ray signals from their neighbors in appropriate directions. All 64 receivers (RECV) are now supplied with signals from their correspondent neighbors, and six disjoint piece (capture target) or empty flags per square are feed into a priority network, which finally outputs the square of the most valuable victim - the target-square. All this takes place simultaneously in propagation delay time of the combinatorial logic of all 64 squares. A king victim on any square, caused by an illegal move is indicated by the chess output flag, ored (>=1) over all 64 square receivers.
Find Aggressor
The find aggressor opcode causes only the addressed victim transmitter to radiate as the union of all other side to move pieces, the super piece, and otherwise applies the same logic as in the find victim cycle. All appropriate pieces of the side to move which receive attacks of the super-piece are potential from-squares of a pseudo-legal move, and piece disjoint signals in reversed order from pawn to king are feed into the priority network to get the from-square of the least valuable aggressor first.
Bookkeeping
Without further sequential logic subsequent find victim and aggressor cycles would always leave the same victim and same aggressor. A stack of 64-bit disable words is used for bookkeeping per ply, keeping the move generation state by consecutively disabling victims, and per victim, its aggressors. After making, processing and unmaking move, the aggressor's from-square of the current victim (to-square) is disabled, so that the next aggressor square is found in consecutive find aggressor cycles, until all from-squares are exhausted. Then, the victim to-square is disabled, and all origin squares of own pieces - always disjoint from their to-squares - are enabled again, to continue with a new find victim cycle until no more are found. In C like pseudo code with Bitboards the control flow looks as follows:
disable[ply]=0;while(( to = findMVV(disable[ply]))>=0){
disable[ply]&= ~ownPieces;/* enable all possible from-squares */while(( from = findLVA(disable[ply]))>=0){
make(from, to);/* ply++ */
....
unmake(from, to);/* ply-- */
disable[ply]|=1<< from;/* disable from-square */}
disable[ply]|=1<< to;/* disable to-square */}
Evaluation
Lazy
The fast incremental lazy evaluation was composed of a material register, a piece position register containing sum from hard wired piece-square tables, and king position registers, in conjunction with 9-bit registers indicating existence of friendly pawns on each wing, the weighted sums of king safety and king centralization, selected by the stage of the game. A conservative fast evaluation could quite often cause a beta-cutoff, without the need for a full evaluation.
Full
The slow and asynchronous full evaluation took eight cycles, and like the move generator, it consists of 64 similar circuits, to evaluate pawn structure and mobility along rays, also considering outposts and surrounding king squares.
Transposition Table
The Transposition Table was implemented within a separate microprocessor system with 1MByte of memory viewed as 128K 8-byte positions for the table, addressed by 16 of the incremental updated 48-bit hashkey bits and White to move. Four of the eight byte entries hold the remaining 32 hash code-bits to resolve index collisions.
Microcode
The microcode was implemented on a 1K x 64-bit microprocessor to perform an alpha-beta search using the move generator, evaluation and transposition table. A value bus was used to perform the minimal calculations, to implement the alpha-beta search and to gate 16-bit values to and from a stack, transposition table, evaluators and LSI-11 processor, with the sole operations of add and compare. A board address and piece bus were used to transfer board memories in the move generator, incremental- and full evaluator. Getting out of check did not count as a ply.
The PVS algorithm in Belle did not do a second search at the root until a second fail high occurred. I don’t know whether or not this idea appears in the literature or not. I would hope it does, but I haven’t been following the literature for about 25 years. In other words, Belle is cleverly going for broke: it knows it’s got a high failure, which is the best move so far, but as long as it doesn’t get a second high failure, the first high failure remains the best move, and it can still avoid doing any more full searches.
Miscellaneous
Most components were Low Power Schottky (74LS) TTL logic, slightly slower than Schottky, but draws much less power, reducing power supply and cooling. The complete machine fits in a rack of 46cm x 38cm by 71cm tall. It weighs about 60kg and was portable.
In 1982, Belle was confiscated by the US State Department at Kennedy Airport when heading to the USSR to compete in a computer chess tournament. Its shipping was considered to be an illegal transfer of advanced technology to a foreign country [15][16]. It took over a month and a $600 fine to get Belle out of customs [17].
QUEEN vs. ROOK by Warren Stenberg and Edware J. Conway, reprinted from the January, 1979 issue of the Minnesota Chess Journal, The Usenet Oldnews Archive, Compilation Copyright (C) 1981, 1996 Bruce Jones, Henry Spencer, David Wiseman » ACM 1978, Endgame Tablebases, Walter Browne
the dominating chess machine in the late 70s and early 80s, was developed by Ken Thompson and Joe Condon [1] from Bell Laboratories. It was five times winner of the ACM North American Computer Chess Championship, the ACM 1978, ACM 1980, ACM 1981, ACM 1982, and ACM 1986, and won the Third World Computer Chess Championship 1980 in Linz [2].
Belle consists of a special-purpose hardware and associated software, and was pure brute-force. Belle started in the early 70s as a sole software approach, but more and more emerged to a hybrid chess computer, next using a move generator, a position evaluator, and a transposition table inside a special-purpose hardware. In its final incarnation, Belle was composed of a PDP-11/23, and further a LSI-11 processor with several custom boards. The speed increased from 200 nps from the software version to about 160,000 nps of the machine mentioned at the Advances in Computer Chess 3 conference in 1981.
Table of Contents
Photos & Games
Blitz 6.5
CHAOS
Hardware Design
The find victim and find aggressor move generation was instrumented by Edward Fredkin, first applied in the Chess-orientated Processing System CHEOPS [8]. The overall architecture of Belle was used for the initial designs of ChipTest, the progenitor of Deep Thought which further evolved to Deep Blue [9], and more recently by FPGA projects, such as Marc Boulé's thesis project around MBChess [10], and notably Brutus [11] and its successor Hydra by Chrilly Donninger et al..Move Generation
The hardware move generator consists of 64 combinatorial circuits similar for each square, controlled by appropriate latches representing the board, and receiving and transmitting signals from/to neighboring squares to propagate piece attacks. Two single wired op-codes, find victim and find aggressor, locate the highest valued piece (including empty square) under attack and the lowest valued piece attacking it in MVV-LVA manner. Move making and unmaking perform incremental updates not only on the piece registers, but also on a Zobrist like 48-bit hashkey and evaluation registers.Block Diagram
Transmitter (XMIT), receiver (RECV), piece register, and ray- and direction multiplexer for each square [12]. The opcode (OP) input is either find victim or aggressor. It controls the transmitters and the order of the receiver outputs as input of the two level priority encoding tree.╔══╗ ┌─────────┐ 64 Disable OP 2 PW ┌╢≥1╟═◄ 2 Pawn Move │ Disable ╞═/═════╣64|1╟───────┐ │ ╔══/═╡╠══╣ 63 other K ┌──┐ │ Memory │ ╔▼═══▼═══▼═╗ └╢≥1╠═◄ 2 Pawn Capt ►═/══════╡ │ check └─────────┘ 8 N ╔══╗ ╔══════════╗║Ki ╚══╝ │≥1├───────────► ╕ ╒ in ╔══╗╟ ║ 64 * ╟╫────────────────────────►────────┤ │ ►═/════╣≥1╟──────►║ ║║(victim / aggressor) └──┘ ╛ ╘ ╚══╝ ║ ║║ Queen / Pawn ┌──────────┐ \|/ 8 K ╔══╗ ║ ╟╫────────────────────────►│ │ - - in ╔══╗╟ ║ ║║ Rook / Knight │ │ From /|\ ►═/════╣≥1╟──────►║ RECV ╟╫────────────────────────►│ │ no square XMIT ╚══╝ ║ PLA ║║ Bishop / Bishop │ ├───────────► Neighbors 4 Diag ╔══╗ ║ ╟╫────────────────────────►│ Priority │ \ / in ╔══╗╟ ║ ║║ Knight / Rook │ Network │ / \ ►═/════╣≥1╟──────►║ ╟╫────────────────────────►│ │ ╚══╝ ║ ║║ Pawn / Queen │ │ | 4 Man ╔══╗ ║ ╟╫────────────────────────►│ │ - - in ╔══╗╟ ║ ║║ Empty / King │ │ square 6 | ►═/════╣≥1╟──────►║ ╟╫────────────────────────►│ ╞═════════/══► ╚══╝ ║ ║╝ │ │ ╚══════════╝ ►════════/══════►│ │ 64 * ▲ 63x6 others └──────────┘ ╔══════════════╗ ║ | ╔══════════════╗ P4 ║ - - 4 Man in ║Piece Register╠═/══╣ | ►═/══════════╗ From XMIT Neighbors ╚══════════════╝ ║ OP WTM \ / 4 Diag in ║ ║ │ │ / \ ►═/══════╗ ║ ╔▼═══▼═══▼═╗ ╔═▼═══▼═══╗ ╔══════════╗║Manhattan ╔═════════╗║ Man out 4 | ║ 64 * ╟╫─────────►║ 64 * ╠══════════════/═► - - To RECV and XMIT ║ ║║Diagonal ║ RAY ║║ Diag out 4 | Neighbors ║ ╟╫─────────►║ MUX ╠══════════════/═► \ / ║ ║║Empty ║ ║║ / \ ║ XMIT ╟╫─────────>║control ║╝ ╕ ╒ To RECV Neighbors ║ ROM ║║Knight ╚═════════╝ N out 8 ║ ╟╫───────────────────────┤*8╠════════/═► ╛ ╘ ║ ║║King K out 8 \|/ ║ ╟╫───────────────────────┤*8╠════════/═► - - ║ ║║ ╔═════════╗ /|\ ║ ║║Pawn ╔═════════╗║Pawn Move out 1 ║ ╟╝─────────►║ 64 * ╟╫───────────────► | ╚══════════╝ ║ DIR MUX ║║Pawn Capt out 2 WTM──>║control ╟╝─┤*2╠════════/═► \ / or / \ ╚═════════╝Find Victim
Find victim causes each transmitter (XMIT) to activate signals corresponding to the piece of the side to move on each square. Empty squares activate the sliding ray signals from their neighbors in appropriate directions. All 64 receivers (RECV) are now supplied with signals from their correspondent neighbors, and six disjoint piece (capture target) or empty flags per square are feed into a priority network, which finally outputs the square of the most valuable victim - the target-square. All this takes place simultaneously in propagation delay time of the combinatorial logic of all 64 squares. A king victim on any square, caused by an illegal move is indicated by the chess output flag, ored (>=1) over all 64 square receivers.Find Aggressor
The find aggressor opcode causes only the addressed victim transmitter to radiate as the union of all other side to move pieces, the super piece, and otherwise applies the same logic as in the find victim cycle. All appropriate pieces of the side to move which receive attacks of the super-piece are potential from-squares of a pseudo-legal move, and piece disjoint signals in reversed order from pawn to king are feed into the priority network to get the from-square of the least valuable aggressor first.Bookkeeping
Without further sequential logic subsequent find victim and aggressor cycles would always leave the same victim and same aggressor. A stack of 64-bit disable words is used for bookkeeping per ply, keeping the move generation state by consecutively disabling victims, and per victim, its aggressors. After making, processing and unmaking move, the aggressor's from-square of the current victim (to-square) is disabled, so that the next aggressor square is found in consecutive find aggressor cycles, until all from-squares are exhausted. Then, the victim to-square is disabled, and all origin squares of own pieces - always disjoint from their to-squares - are enabled again, to continue with a new find victim cycle until no more are found. In C like pseudo code with Bitboards the control flow looks as follows:Evaluation
Lazy
The fast incremental lazy evaluation was composed of a material register, a piece position register containing sum from hard wired piece-square tables, and king position registers, in conjunction with 9-bit registers indicating existence of friendly pawns on each wing, the weighted sums of king safety and king centralization, selected by the stage of the game. A conservative fast evaluation could quite often cause a beta-cutoff, without the need for a full evaluation.Full
The slow and asynchronous full evaluation took eight cycles, and like the move generator, it consists of 64 similar circuits, to evaluate pawn structure and mobility along rays, also considering outposts and surrounding king squares.Transposition Table
The Transposition Table was implemented within a separate microprocessor system with 1MByte of memory viewed as 128K 8-byte positions for the table, addressed by 16 of the incremental updated 48-bit hashkey bits and White to move. Four of the eight byte entries hold the remaining 32 hash code-bits to resolve index collisions.Microcode
The microcode was implemented on a 1K x 64-bit microprocessor to perform an alpha-beta search using the move generator, evaluation and transposition table. A value bus was used to perform the minimal calculations, to implement the alpha-beta search and to gate 16-bit values to and from a stack, transposition table, evaluators and LSI-11 processor, with the sole operations of add and compare. A board address and piece bus were used to transfer board memories in the move generator, incremental- and full evaluator. Getting out of check did not count as a ply.PVS
Recently [13], John Philip Fishburn gave some interesting internals on Belle's principal variation search:The PVS algorithm in Belle did not do a second search at the root until a second fail high occurred. I don’t know whether or not this idea appears in the literature or not. I would hope it does, but I haven’t been following the literature for about 25 years. In other words, Belle is cleverly going for broke: it knows it’s got a high failure, which is the best move so far, but as long as it doesn’t get a second high failure, the first high failure remains the best move, and it can still avoid doing any more full searches.
Miscellaneous
Most components were Low Power Schottky (74LS) TTL logic, slightly slower than Schottky, but draws much less power, reducing power supply and cooling. The complete machine fits in a rack of 46cm x 38cm by 71cm tall. It weighs about 60kg and was portable.In 1982, Belle was confiscated by the US State Department at Kennedy Airport when heading to the USSR to compete in a computer chess tournament. Its shipping was considered to be an illegal transfer of advanced technology to a foreign country [15] [16]. It took over a month and a $600 fine to get Belle out of customs [17].
See also
Selected Publications
[18]Forum Posts
External Links
References
What links here?
Up one Level