In early 2000, Ken Thompson told his friend Frederic Friedel about interesting hardware developments concerning FPGAs, and asked whether he was aware of a programmer who could build such a kind of "People's Deep Blue". ChessBase, surely interested in the commercial aspects of such a machine, engaged Chrilly Donninger for the development of a FPGA based chess hardware and program. The work on Brutus started in October 2000, one year later it could calculate its first position, and in January 2002, it played its first game. Soon, programmer, chess expert and opening book author Alex Kure, and in November 2002, Ulf Lorenz, responsible for the surrounding distributed search, joined the Brutus team, with ChessBase and the University of Paderborn cooperating on the project [2].
Brutus partially ran on PCs and partially on FPGA cards. Opposed to a pure move generation approach, and to diminish PCI communication overhead with the PC, the hardware was designed also to perform a kind of iterative search. Brutus’ FPGA definition was written in the Veriloghardware description language, and uses 67 out of 96 BlockRAMs, 534 of 24,576 Flip-Flops, and 18,403 of 24,576 LUTs of the Virtex board [4].
Brutus calculates the last 3 plies of an n-ply search on the FPGA side, inclusively quiescence search and evaluations. It essentially contains a big piece of combinatorial logic, controlled by a finite state machine (FSM) with 54 states for the search. An upper bound for the number of cycles per search node is 9. The Figure below shows a simplified version of the FSM that controls the search on the FPGA card. States must not be interpreted as time points when functions are called. E.g. the move generator and the evaluation are never called in that sense. They are running all the time [6].
The evaluation consists of many small features which are summed up by one large adder tree. All features are determined simultaneously.
Move Generation
The Belle like move generator consists of the generate aggressor module and the generate victim module, both instantiate 64 square modules, one for each square. The squares send piece-signals if any, respectively forwarding the signals of sliding pieces. Each square can output the signal ’victim found’ to indicate the ’victim’ is target square of a pseudo-legal move. The collection of all ’victim found’ signals is the input for a comparator tree, an arbiter, which selects the most attractive, not yet examined victim. The generate aggressor module takes the arbiter’s output as input and sends the signal of a super-piece from the target to find one or more origin squares. Selection criteria are the values of attacked pieces and whether or not a move is a killer move.
Distributed Search
The most sensitive and important part of Brutus search algorithm is distributed among several standard PCs, connected via a high-speed Myrienet. One of the processors receives the current chess position and basically begins a sequential alpha beta search. Idle processors send work requests randomly around the net - when a working processor captures such a request, it distributes part of his own (sub-) problem. Using a tricky messaging system between the processors, the work is dynamically balanced with little search overhead. After a while, all processors have something useful to do. A processor generates approximately 100,000 searches on a FPGA board per second [8].
Tournament Play
A Brutus prototype had its debut at the IPCCC 2002 with an expected 50% score, but Brutus quickly improved and already played a strong WCCC 2002 in Maastricht, where it became third only loosing a spectacular game from later champion Junior. At the IPCCC 2003, Brutus became third again, then, in August 2003, it won the 11th Grandmaster Tournament in Lippstadt with 9 out of 11 [9], and seemed dedicated to win the upcoming WCCC 2003 in Graz, but after two consecutive losses from Shredder and Deep Junior in round 5 and 6, Brutus finished disappointing fourth. As a consequence, ChessBase went out of the project, which then continued under the patronage of the Pal Group of Companies [10] under its new name Hydra.
a FPGA based chess entity developed by Chrilly Donninger, supported by Alex Kure and Ulf Lorenz. Brutus consists of usual PCs with Xilinx Virtex FPGA boards inside, and was designed in dependence on the Belle and Deep Thought chess machines. In fact, it was Ken Thompson who initiated and supported the FPGA chess project. After the WCCC 2003, Brutus evolved to Hydra.
Table of Contents
How it started
In early 2000, Ken Thompson told his friend Frederic Friedel about interesting hardware developments concerning FPGAs, and asked whether he was aware of a programmer who could build such a kind of "People's Deep Blue". ChessBase, surely interested in the commercial aspects of such a machine, engaged Chrilly Donninger for the development of a FPGA based chess hardware and program. The work on Brutus started in October 2000, one year later it could calculate its first position, and in January 2002, it played its first game. Soon, programmer, chess expert and opening book author Alex Kure, and in November 2002, Ulf Lorenz, responsible for the surrounding distributed search, joined the Brutus team, with ChessBase and the University of Paderborn cooperating on the project [2].Etymology
The name Brutus was chosen by Matthias Wüllenweber due to his spot on Ancient Rome. The idea was a "People's Deep Blue" to dethrone "Caesar" Garry Kasparov [3].Description
Brutus partially ran on PCs and partially on FPGA cards. Opposed to a pure move generation approach, and to diminish PCI communication overhead with the PC, the hardware was designed also to perform a kind of iterative search. Brutus’ FPGA definition was written in the Verilog hardware description language, and uses 67 out of 96 BlockRAMs, 534 of 24,576 Flip-Flops, and 18,403 of 24,576 LUTs of the Virtex board [4].FPGA Search
Brutus calculates the last 3 plies of an n-ply search on the FPGA side, inclusively quiescence search and evaluations. It essentially contains a big piece of combinatorial logic, controlled by a finite state machine (FSM) with 54 states for the search. An upper bound for the number of cycles per search node is 9. The Figure below shows a simplified version of the FSM that controls the search on the FPGA card. States must not be interpreted as time points when functions are called. E.g. the move generator and the evaluation are never called in that sense. They are running all the time [6].Evaluation
The evaluation consists of many small features which are summed up by one large adder tree. All features are determined simultaneously.Move Generation
The Belle like move generator consists of the generate aggressor module and the generate victim module, both instantiate 64 square modules, one for each square. The squares send piece-signals if any, respectively forwarding the signals of sliding pieces. Each square can output the signal ’victim found’ to indicate the ’victim’ is target square of a pseudo-legal move. The collection of all ’victim found’ signals is the input for a comparator tree, an arbiter, which selects the most attractive, not yet examined victim. The generate aggressor module takes the arbiter’s output as input and sends the signal of a super-piece from the target to find one or more origin squares. Selection criteria are the values of attacked pieces and whether or not a move is a killer move.Distributed Search
The most sensitive and important part of Brutus search algorithm is distributed among several standard PCs, connected via a high-speed Myrienet. One of the processors receives the current chess position and basically begins a sequential alpha beta search. Idle processors send work requests randomly around the net - when a working processor captures such a request, it distributes part of his own (sub-) problem. Using a tricky messaging system between the processors, the work is dynamically balanced with little search overhead. After a while, all processors have something useful to do. A processor generates approximately 100,000 searches on a FPGA board per second [8].Tournament Play
A Brutus prototype had its debut at the IPCCC 2002 with an expected 50% score, but Brutus quickly improved and already played a strong WCCC 2002 in Maastricht, where it became third only loosing a spectacular game from later champion Junior. At the IPCCC 2003, Brutus became third again, then, in August 2003, it won the 11th Grandmaster Tournament in Lippstadt with 9 out of 11 [9], and seemed dedicated to win the upcoming WCCC 2003 in Graz, but after two consecutive losses from Shredder and Deep Junior in round 5 and 6, Brutus finished disappointing fourth. As a consequence, ChessBase went out of the project, which then continued under the patronage of the Pal Group of Companies [10] under its new name Hydra.Photos & Games
IPCCC 2002
WCCC 2002
WCCC 2002, round 6, Brutus - Deep Junior [13] [14]:WCCC 2003
See also
Namesake
Publications
Forum Posts
External Links
Chess
Maastricht
Lippstadt
Graz
Brutus
Assassination of Julius Caesar from Wikipedia
Et tu, Brute? from Wikipedia
References
What links here?
Up one Level