*Help* my chess program is too slow
Joe Stella
I am writing a chess program in C++ on my 486/33 PC, using Microsoft Visual
C++. The program runs under Windows.
The move generator uses the GNU chess algorithm. Move ordering is as follows:
1) Suggested move from hash table (if hit)
2) Value of captured piece
3) The history heuristic
The tree search is Principal Variation Search, using null move pruning. The
quiescence search considers captures only, but captures which are also checks
are detected as checks.
The evaluator is very simple, considering material, doubled pawns, passed
pawns, mobility, and (in the opening) the number of pieces developed.
I also use piece-value tables. Material and PV scores are updated
incrementally when a move is made.
It takes an average of about 25 seconds to do a 5-ply search on my 486/33.
Moves that get out of check don't count as a ply. The node count is about 2000
nodes per second, with a "node" defined as any *legal* move made in the tree
search. Nodes visited more than once by PVS are counted as two nodes.
It seems to me that 2000 nodes per second is too slow for a 486/33. My Novag
Super Expert C (6 MHz 6502) is almost this fast, and it has a much more
complicated evaluator.
I have read books like "How Computers Play Chess by Levy and Newborn, and
"Computer Chess" by Welsh. I also have *all* the back issues of the ICCA
journal (that is where I got the algorithm for Null Move Pruning; "Null Move
and Deep Search", by Chr. Donniger, Vol 16 No 3, which I founnd extremely
helpful). The above references give very good high-level descriptions of
algorithms but say very little about efficient implementation issues.
Can anyone give me some advice about efficient chess programming? I have 12
Meg. RAM in my system but am only using 3 Meg for the program (2 Meg for hash
tables). Is there a way to use the memory to increase search efficiency?
Can moves be generated one (or a few) at a time so that time is not wasted
generating moves that are not searched? If so, how does one know which moves
(for which piece) to generate? Or maybe I am missing the boat completely, and
there is a better way to search than PVS?
Are there any references I could read about this?
Andy Monks
: Last post happened to soon by accident, please ignore.
: I am writing a chess program in C++ on my 486/33 PC, using Microsoft Visual
: C++. The program runs under Windows.
: The move generator uses the GNU chess algorithm. Move ordering is as follows:
: 1) Suggested move from hash table (if hit)
: 2) Value of captured piece
: 3) The history heuristic
: It seems to me that 2000 nodes per second is too slow for a 486/33. My Novag
: Super Expert C (6 MHz 6502) is almost this fast, and it has a much more
: complicated evaluator.
I have a 486/50 (Not DX2) with 20MB RAM, running Chessmaster 4000 Turbo. This
can only do 2300 moves per second. So I think, your doing pretty well.
--
Best Regards,
Andy Monks United Kingdom Country Response Centre
Hewlett-Packard Ltd. Mail a...@hpwin064.uksr.hp.com
-----------------------------------------------------------------------------
De' ll' Sovlu'DI' chaq Do'Ha' or Knowledge of useful information may be
unfortunate.
Jon Dart
>I am writing a chess program in C++ on my 486/33 PC, using Microsoft Visual
>C++. The program runs under Windows.
>It takes an average of about 25 seconds to do a 5-ply search on my 486/33.
>Moves that get out of check don't count as a ply. The node count is about 2000
>nodes per second, with a "node" defined as any *legal* move made in the tree
>search. Nodes visited more than once by PVS are counted as two nodes.
>
>It seems to me that 2000 nodes per second is too slow for a 486/33. My Novag
>Super Expert C (6 MHz 6502) is almost this fast, and it has a much more
>complicated evaluator.
Actually, 2000 nodes per second is pretty good, about on the order of what
I'd expect given your hardware and implementation language. You also have
to rememeber that under Windows, you don't get all of the CPU. During a
GetMessage or PeekMessage call, the system will yield to other tasks
(e.g. the Clock, Program Manager, etc.) and they will get some CPU cycles.
Remember, the Novag Super Expert is coded in assembly language. You can
get a several times speed improvement by coding yours in assember (not
that I'd recommend it).
>Can anyone give me some advice about efficient chess programming?
Bob Hyatt and several others have recently discussed using bitboards for
move generation, which appears to be more efficient than the Gnu Chess
algorithm.
Move ordering is also extremely important. It sounds like you have a
reasonably good move ordering mechanism, but more effort in this area
might pay off. Also, I believe Visual C++ has a profiler, so you
might try running that over your code to see where the hot spots are.
--Jon
--
--
-- Jon Dart, Rational Software Corp., jd...@rational.com
-- 2800 San Tomas Expy., Santa Clara CA 95051 tel: (408)-496-3656
Christian Schlender
>Joe Stella (jo...@ultranet.com) wrote:
>: Last post happened to soon by accident, please ignore.
>
>: I am writing a chess program in C++ on my 486/33 PC, using Microsoft Visual
>: C++. The program runs under Windows.
>: The move generator uses the GNU chess algorithm. Move ordering is as follows:
>: 1) Suggested move from hash table (if hit)
>: 2) Value of captured piece
>: 3) The history heuristic
>
>: It seems to me that 2000 nodes per second is too slow for a 486/33. My Novag
>: Super Expert C (6 MHz 6502) is almost this fast, and it has a much more
>: complicated evaluator.
I don't think the nodes per second are important for a good chess
program. My Chessmaster 4000 turbo (?) runs with 900 nodes p.sec.
on my 486/33 and his playing is quite good !
Christian Schlender
Internet: ch...@case.gerwin.net
Compuserve: 100025,3044
"we trust in god - all other pay cash"
Thorsten Greiner
your chess program is too slow, well, whose isn't ? :-)
I am busy with chess programming for about a year, maybe I can give you some
hints.
First of all, in my opinion C++ isn't the perfect language when it comes
to performance. From my experience, programs in C++ that use classes etc.
typically run a factor 2 to 10 slower than their C counterparts. I must say
though, that I don't have any experience with Visual C or Visual C++.
Second you could try to improve your move ordering. My chess program Amy uses
the following ordering:
1. Null move
2. Move from the transposition table
3. Gaining captures
4. Killer moves
5. Loosing captures
6. All other moves (with some static ordering)
A gaining capture is defined as a capture to an undefended piece, or if the
piece is defended, if it has higher value (e.g. pawn takes queen). Since I am
using bitboards for move generation, the test for being defended can be made
fairly quick. In your case this test probably is much harder to make (i.e.
time consuming).
Two killer moves together with the frequency of cutoffs they caused are
maintained for each ply level. Both of them and the best killer from two plies
earlier are tried. It is important NOT to put captures into the killer list!
Third, PVS search is a well known method which I think is used by all chess
programs. I don't know any practical alternatives.
Fourth, the evaluation function. I have divided it into two parts, a slow and
a fast evaluation function. The fast eval score is maintained in the
DoMove/UndoMove routine. It covers things like material balance, piece
placement, pawn advancement etc.
The slow eval deals with things like mobility, pawn structure etc. This
routine is called only if the fast eval score is in the range
[alpha-MaxPos , beta+MaxPos], where MaxPos is something like 3/4 of a pawn
(materialwise). This alone makes the program a factor 1.5 to 2 faster in terms
of nodes/sec.
Hope that helps
-Thorsten
--
Thorsten Greiner // gre...@wpts0.physik.uni-wuppertal.de
Department of Physics \\ //
Wuppertal University \X/