Computer Chess Hardware Design
Valavan Manohararajah
Given that I am rapidly approaching the end of my undergraduate studies
here at the University of Toronto, I wanted to look at chess specific
hardware as a possible thesis topic.
I have already written a chess program, that goes by the name of Rajah
on ICC. In order to speed the program quite a bit, I am planning on
transferring/rewriting portions of Rajah for a software/hardware combination
program.
Some hardware designs come to mind.... Belle and Deep Blue. I have already
read an overview of the design of Belle and Deep Blue... they are almost
identical except for a few "neat" things in Deep Blue.
Most likely, I will be doing this in an FPGA. Also I will manage to get
only the move generator or utility chip done in time. I doubt that an
FPGA can buy that much performance over a nicely optimized program
running on a Pentium PRO, but the project is being done more as an
exploratory excercise in FPGAs.
The question is this:
What kind of functions or procedures employed in
todays chess programs benefit most from a hardware version?
A more general version of Deep Blue's move generator seems like it can help
move generation routines, see routines and may possibly help the evaluator.
A device that recognizes pins/attacks may help the evaluator but I doubt it
does anything for a move generator.
Also, what are some of the other designs that have been done in the past?
Some sort of design where offsets are added and tested was referred to in
Feng-hsiung Hsu's thesis paper, but there is not much detail there.
Another question is what exactly did the "ChessMachine" hardware sold a while
ago do? Did it perform some sort of hardware acceleration?
--
-------------------------------------------------------------------------------
man...@ecf.utoronto.ca | 3rd year Comp Eng., University of Toronto
Valavan Manohararajah |
-------------------------------------------------------------------------------
Robert Hyatt
Valavan Manohararajah (man...@ecf.toronto.edu) wrote:
: Given that I am rapidly approaching the end of my undergraduate studies
for your last question first, no. Just a different CPU (ARM).
The simplest place to start is to build a "circuit" that holds the
chessboard, and can (a) make moves; (b) unmake moves; and (c) generate
moves in some logical order (typically captures first, using the MVV/LVA
approach.)
This gets you quite a bit with a relatively simple hard ware design. No
fancy stack, no hardware hash table, no hardware replacement for the
recursive search, etc.
the next thing to add would be a fast eval/slow eval, so that after each
make_move() operation, it computes the eval while you are getting ready to
use such an eval.
The next level up is to put "belle on a chip" like Hsu did in the first
DT chips, but that's a horse of a different color and is likely beyond what
you want to attempt using FPGA technology. Even the eval is a problem,
because it will be impossible to modify it, once you blow the diodes...
But the other stuff is reasonably static, and it'd be nice to have a set
of registers that contain the board position, and a few dozen nanoseconds
later a move has been made, or the moves from the current position have
been generated... Probably just make/unmake would save a good bit of
time and would be easiest for a start.
There's a guy running on ICC (DarkBlue) who has taken a microprogrammed
graphics board he designed at work, and has re-microprogrammed it to do some
of the chess-specific things. He's using some pretty old ideas from the
first version of "blitz" that I gave away the source for, and is searching
over 200K nodes per second, and is quite strong. You might also prompt him
for more input...
Sounds like fun... Rajah's been playing well already... faster will be
better. :)
John A. Gregor, Jr.
In article <5hkqmq$6...@juniper.cis.uab.edu>,
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
> The next level up is to put "belle on a chip" like Hsu did in the
> first DT chips, but that's a horse of a different color and is likely
> beyond what you want to attempt using FPGA technology. Even the eval
> is a problem, because it will be impossible to modify it, once you
> blow the diodes...
While the first part of your statement is probably true, the second is
not. Some FPGAs are reprogrammable on the order of milliseconds (they use
an SRAM to hold the state rather than blowing fuses or the like). An FPGA
based machine that adapted its algorithm based on the stage of the game
or other criteria is possible.
-JohnG
Robert Hyatt
John A. Gregor, Jr. (jgr...@engr.sgi.com) wrote:
: In article <5hkqmq$6...@juniper.cis.uab.edu>,
: -JohnG
Haven't looked at them in a while. Last time I looked, they were made up
of a zillion diodes that could be blown or not blown. Something programmable
would be much better as making a mistake with blowing a diode sort of leaves
you in a hole. :)