Computer Chess Club Archives




Subject: Re: How do you represent chess boards in your chess programms

Author: Robert Hyatt

Date: 21:23:43 09/28/99

Go up one level in this thread

On September 28, 1999 at 19:43:04, Dan Newman wrote:

>On September 28, 1999 at 09:42:52, Robert Hyatt wrote:
>>On September 27, 1999 at 05:25:05, Dan Newman wrote:
>>>On September 25, 1999 at 13:56:29, Vincent Diepeveen wrote:
>>>>We should compare speeds.
>>>>What i do after 1.e4,e5 2.d4,d5 is
>>>>generate the move list a few million times (n times).
>>>>Then i divide the time by (n * #semi legal moves).
>>>>#nodes a second generated at a PII450 for diep is 15.5M
>>>>Haven't seen anyone faster so far, though most are not
>>>>reveiling their speed.
>>>>Note that if we have a merced within say 5 years that i
>>>>can implement bitboards for a few eval terms within a day by then.
>>>>No need for rotated bb of course as i keep my current generator
>>>>and makemove.
>>>>Majority of code is not faster using bitboards even at 64 bits
>>>I tried this position out on the (non-rotated) bitboard engine that I'm just
>>>starting.  I compiled with MSVC++5 and get 10.25 M moves generated/s on a
>>>P6/200.  So, (ignoring cache speed differences) I should get something near
>>>2.25 * 10.25 == 23.6 Mm/s on the PII450.
>>>OTOH, my (more developed) 0x88 engine gets 11.3 Mm/s on this position, which
>>>is slightly better than the bitboard program (roughly 25 million moves
>>>generated per second on the PII450).  It seems like if I were to go to a 64
>>>bit machine, the bitboard version would benefit somewhat more and would
>>>probably go faster than the 0x88.
>>>Of course these measurements, made by repetitively calling the move generator
>>>in a tight loop for the same position, may not tell us much because of (among
>>>other things) the branch prediction hardware.  This will artificially inflate
>>>these numbers.  In real life when the move generator is called with different
>>>positions and is continually getting blown out of cache, it may perform quite
>>>Actually, the speed at which moves are generated is not a good reason to
>>>choose between bitboards and 0x88, or whatever.  The last time I profiled
>>>my 0x88 program, the move generation was taking about 20%.  The SEE was
>>>taking 25% and the eval 4%.  If I ever get a decent amount of eval added
>>>(say 50% of cpu time) this will greatly depress the move generation figure.
>>>So a 10% change in move gen speed might change the overall speed by 1% in
>>>a well developed chess program.
>>>Now, if my (non-rotated) bitboards can help speed up the SEE or some of
>>>the (as yet unwritten) eval terms, it might be a good deal faster than
>>>the 0x88--but I don't really have a good feel for this yet.
>>>I do like the way bitboards replace the piece-list structures though.  It
>>>was always a drag trying to figure out what to do with captured pieces,
>>>where to put promoted pieces, and so forth.  All this goes away with
>>>bitboards.  I think this is my favorite aspect of bitboards at this
>>It sounds like you are going very fast.  Are you using incremental update or
>>just direct computation of the attack bitmaps when you need them as I do?
>I haven't actually gotten that far yet.  Currently I've just got the
>move generator and part of make().  I suspect I'll just calculate
>them as I need them, but I'll have to see.  Since I'm not doing the
>rotated bitboards, I only get pseudo attacks for the sliders and must
>scan the board on occasion.  The problem with incremental calculations
>is that you incur the cost on every call to make() whether they get
>used on not...
>Anyway, my bitboard move generator (on the P6) is almost as fast as
>my 0x88 generator.  The last time I tried bitboards they were about
>half the speed of 0x88.  (BSF works wonders.)  Also, I had been
>compiling with Watcom.  When I switched to MSVC5 I got a 17% speedup
>on my 0x88 program.  On the bitboard move generator, I got 30%!  I
>suspect the MS compiler knows more about the P6.

Still sounds very fast.  IE you are generating all the moves, which means you
are doing a very good job of handling sliders already...  When I first tried
this, I had a loop that went thru the 4 directions one at a time to locate the
'blocking piece'.  And required 4 calls to bsf/bsr (depending on the direction)
to find this blocking square so that a mask could be used to cut off attacks
beyond that point...

for comparison, try crafty if you have time.  set up the same position you are
testing with, and then type "perf".  On my PII/300 notebook, I get about 5M
moves generated per second...  this is just calling the move generator over
and over for the same position, to make it use a reasonable amount of time...

here is what you might get from the opening:

White(1): perf
generated 2000000 moves, time=0.53 seconds
generated 3773585 moves per second
generated/made/unmade 2000000 moves, time=2.02 seconds
generated/made/unmade 990099 moves per second

the first two lines are just repeated calls to the move generator...  In
my case one call to GenerateCaptures() and one call to GenerateNonCaptures().
repeated 100K times.  The second two lines generates the same set of moves,
then makes/unmakes each one once.  Then repeat the whole process again..
100K times...

This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.