Computer Chess Club Archives




Subject: Move generation question for the big boys

Author: Sune Fischer

Date: 08:14:36 09/15/01


When I discovered that Crafty had some neat assembler rutines, I decided to test
if they where faster than my humble rutines.
I have up until now used a "raytracing" or boardtracing rutine to find the legal
moves for the sliding pieces. And for the knights, pawns and king I simply check
if the board has an allied piece on that square.
It's a simple way of generating the legal moves.
I still generate the attack bitboards to get the legal king moves though.

I then tried to find all the moves directly from the bitboards by using one of
Crafty's assember functions.
This part of my program is only a minor part, but none the less it runs a full 8
percent slower than my previous raytracing algorithm!!

This is what I have now:

void FindMovesQueen(..loads of pointers...)
 int to_square;
 BITBOARD bb=(~allied.occupied) & allied.attack[[from_square]];

 while (bb)
   to_square=63-FirstOne(bb);    // get a bit
   bb ^= mask[to_square];        // remove the bit


(movelist, counter, from_square etc. are passed in the argument)

I know why it is slow too.
First I have to form the bb, that's 2 bitboard operations.
Then I need to run an algorithm, FirstOne from crafty, to find the first bit.
Then I need to mask out that found bit.
Both of these run several time pending on the while loop.
Next is 4 lines I always have, no matter how I do it, so we can safely ignore
The while loop is a conditional much like the if's I use when raytracing, so
probably the if's and while almost cancel out.

All in all I have added a lot of operations to my program, I am not surprized it
is a lot slower. Given that the entire program suffer a slowdown by about 8.1
percent, I estimate that this technique is more than twice as slow as the
The upside of things is that I reduce my code by about 1000 lines or so, but is
this worth 8 percent in speed?
I know the use of 64 bit processors will give a nice boost to this method and I
probably can't expect anything like that for my tracing function, but frankly
I'm not sure it would be enough to catch up.

Am I mistaken, are the big boys doing something else?
Is there an even faster way?
I need to know :D :D


This page took 0.03 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

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