Brutus

From Chessprogramming wiki
Jump to: navigation, search

Home * Engines * Brutus

Brutus [1]

Brutus,
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.

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 Paderborn University 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].

Brutusfpga2002.jpg

Brutus on a Xilinx Virtex V405E FPGA development board [5]

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].

FPGASearch.JPG

Search in Hardware: Simplified state diagram [7]

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. Based on work stealing, one processor receives the current chess position and basically begins a sequential alpha beta search, while 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

AlexChrilly.JPG

IPCCC 2002: Alex Kure, Chrilly Donninger, Mathias Feist, Brutus vs. Fritz 0 - 1 [11]

[Event "IPCCC 2002"]
[Site "Paderborn GER"]
[Date "2002.03.03"]
[Round "07"]
[White "Brutus-XPa"]
[Black "Fritz"]
[Result "0-1"]
[ECO "E34"]

1.d4 Nf6 2.c4 e6 3.Nc3 Bb4 4.Qc2 d5 5.cxd5 Qxd5 6.Nf3 Qf5 7.Qxf5 exf5 8.a3 Be7 9.Bf4 c6 
10.e3 Nbd7 11.Bc4 Nb6 12.Ba2 Be6 13.Be5 h6 14.Ke2 a5 15.Rhc1 a4 16.Kf1 O-O 17.Ne2 Ne4 
18.Bxe6 fxe6 19.Nf4 Kf7 20.Bxg7 Kxg7 21.Nxe6+ Kf6 22.Nxf8 Bxf8 23.Ke2 Bd6 24.g3 h5 
25.Nh4 Nd5 26.f3 Ng5 27.Kd3 Rd8 28.e4 Ne7 29.Ke3 Bc7 30.Nxf5 Nxf5+ 31.exf5 h4 32.f4 
Re8+ 33.Kd3 Nf3 34.d5 Nxh2 35.dxc6 hxg3 36.cxb7 Bxf4 37.Rc4 Kxf5 38.Rxa4 g2 39.Ra5+ Kf6 
40.Ra6+ Kf7 41.Ra4 Bb8 42.Ra5 Kf6 43.Ra6+ Kf5 44.Ra5+ Kf4 45.Ra6 Nf3 46.Rf6+ Kg3 47.Rg6+ 
Kf2 48.Rg7 g1=R 49.Raxg1 Nxg1 50.Rf7+ Nf3 51.a4 Kg3 52.Rg7+ Kf4 53.Rf7+ Kg4 54.Rh7 Ng5 
55.Rd7 Kf5 56.a5 Ke6 57.Rd4 Nf3 58.Ra4 Kd5 59.a6 Ba7 60.Kc3 Re3+ 61.Kc2 Nd4+ 62.Kd2 Nc6
63.Kc2 Kc5 64.Kd2 Kb5 65.Ra1 Re7 66.Rc1 Rd7+ 67.Ke1 Nb4 68.Ke2 Kxa6 0-1

WCCC 2002

WCCC 2002, round 6, Brutus - Deep Junior [12] [13]:

[Event "WCCC 2002"]
[Site "Maastricht, The Netherlands"]
[Date "2002.07.09"]
[Round "6"]
[White "Brutus"]
[Black "Deep Junior"]
[Result "0-1"]

1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be2 e5 7.Nb3 Be7 8.O-O O-O 9.Kh1 Qc7 
10.f4 b5 11.fxe5 dxe5 12.Bg5 Nbd7 13.Bd3 Bb7 14.Qf3 b4 15.Ne2 a5 16.Ng3 g6 17.Rad1 a4 
18.Nd2 Ba6 19.Ne2 Rfc8 20.b3 Kg7 21.Qh3 h5 22.Qf3 Qc6 23.Bc4 Bxc4 24.Nxc4 Qe6 25.c3 
axb3 26.axb3 Rxc4 27.bxc4 b3 28.h3 b2 29.Ng3 Qxc4 30.Rb1 Rb8 31.Rfd1 Rb3 32.Rd3 Nc5 
33.Re3 Rb6 34.Re2 Na4 35.Rd2 Qa2 36.Rdd1 Rc6 37.Ne2 Qc4  38.Rf1 Rb6 39.Rbd1 Kf8 
40.Bh6+ Ke8 41.Bg7 Qxe4 42.Bxf6 Qxf3 43.gxf3 Rxf6 44.Rb1 Ba3 45.f4 exf4 46.Rf3 g5 
47.c4 Bc5 48.Rd3 g4 49.Rb3 Kd7 50.Rf1 f3 51.Ng3 Rb6 52.Rxb6 Nxb6 0-1 

WCCC 2003

BrutusDiep.jpg

WCCC 2003, Brutus - Diep [14], Vincent Diepeveen, Ulf Lorenz and Chrilly Donninger [15]

[Event "WCCC 2003"]
[Site "Graz, Austria"]
[Date "2003.11.27"]
[Round "8"]
[White "Brutus"]
[Black "Diep"]
[Result "1-0"]

1.e4 c5 2.Nf3 d6 3.d4 cxd4 4.Nxd4 Nf6 5.Nc3 a6 6.Be3 e5 7.Nb3 Be6 8.f3 Nbd7 9.Qd2 b5 
10.a4 b4 11.Nd5 Bxd5 12.exd5 Nb6 13.Bxb6 Qxb6 14.a5 Qb7 15.Bc4 Be7 16.Ra4 Rb8 17.Nc1 
O-O 18.b3 Bd8 19.Na2 Nd7 20.Kd1 Qc8 21.Nxb4 Nc5 22.Ra2 Bg5 23.Nc6 Qxc6 24.dxc6 Bxd2 
25.Kxd2 Rfc8 26.Bd5 Ne6 27.Rd1 Nd8 28.c3 Kf8 29.g4 Ke7 30.h4 Rc7 31.Ra4 f6 32.h5 Nxc6 
33.Rc4 Kd7 34.b4 h6 35.f4 exf4 36.Rxf4 Ne5 37.Re1 Rb5 38.Bb3 Rbb7 39.Re3 Rb8 40.Rd4 
Rbc8 41.Bd5 Rc4 42.Rde4 R4c7 43.Kc2 Rb8 44.Rd4 Rb5 45.Kb3 Nc6 46.Be6+ Ke7 47.Bc4+ Re5 
48.Rdd3 Ra7 49.Bd5 Nd8 50.Re4 Ne6 51.Rd2 Kd7 52.c4 Nc7 53.Red4 Nxd5 54.Rxd5 Rxd5 
55.Rxd5 Ke6 56.Kc3 Ra8 57.Kd4 g6 58.hxg6 Rg8 59.c5 dxc5+ 60.bxc5 Rxg6 61.c6 Rxg4+ 
62.Kc5 Ra4 63.Rd8 Rxa5+ 64.Kb6 Ra2 65.c7 Rc2 66.c8=Q+ Rxc8 67.Rxc8 Kf5 68.Rh8 Kg5 
69.Kxa6 h5 70.Kb5 h4 71.Kc4 Kg4 72.Kd4 Kg3 73.Ke3 Kg4 74.Rh7 h3 75.Rh6 f5 76.Rg6+ 
Kh4 77.Kf4 1-0 

Namesake

See also

Publications

Forum Posts

2002

2003

2004 ...

External Links

Chess Entity

Maastricht

Lippstadt

Graz

Brutus

Assassination of Julius Caesar from Wikipedia
Et tu, Brute? from Wikipedia

References

Up one Level