Author: martin fierz
Date: 03:21:13 09/25/04
aloha!
[OT]autumn has hit switzerland, it's cold and raining outside & my girlfriend is
on a holiday so i have resumed looking at my engine => a zillion questions,
here's the first[/OT]
when i started programming my chess engine on july 1st 2003, i didn't do much
research on it at all and started hacking away happily. the result is a "grown",
undesigned program and i'm wondering about whether i should start some major
rewrites/cleaning up.
back then, i chose bitboards as board representation since i figured that if now
both 0x88 and bitboards are popular, the advent of 64-bit computing would shift
the balance in the direction of bitboards. back then too, i figured that i
better get something working instead of worrying too much about the details, and
didn't bother to understand rotated bitboards, thinking i could always add that
later. sorry for the lengthy introduction, but i think it may help to understand
what i want to do/know :-)
today, my engine is ultra-slow in terms of kN/s (about like gothmog, which also
goes to show that my thing could be much better despite being so slow). one of
the reasons for the slowness is that in my eval (which i do everywhere in the
tree) i compute all attacks since this comes in handy for stuff like evaluation
and SEE. according to my profiler, this attack computation takes most time.
now, here's how i do attacks today, i call it "raytracing":
int64 empty, org, attack, tmp, y;
empty = ~p->occupied;
tmp = p->wrook;
while (tmp)
{
org = tmp & -tmp; // starting square of the slider
tmp ^= org; // remove this slider
attack = 0;
x = forward(org); // x traces a ray forward; forward(x) is a macro
// forward(x) <--> (x = x<<8);
while(x & empty)
{
attack |= x;
x = forward(x);
}
// attack now contains all attacks in the forward direction of this slider.
// the rest of the rook attacks would be similar
return(attack);
}
then there are two other appoaches, the rotated bitboard approach which needs a
table lookup, and the kogge-stone fills which i believe originate from steffan
westcott and which gerd propagates here from time to time.
here are my first 3 questions
1) does anybody here have an idea how these 3 ways of generating attacks for
sliders compare speedwise for both 32-bit and 64-bit processors? (reason: if
kogge-stone will be comparable to rotated bitboards, i'd rather not bother to
implement rotated bitboards, and if both are not much better than my current
code, i'd also rather not bother with a rewrite).
2) in the code above, to make things more readable and compact i could write
functions like this (same for kogge-stone):
forwardattack(org, empty)
{
int64 attack;
x = forward(org); // x traces a ray forward; forward(x) is a macro
// forward(x) <--> (x = x<<8);
while(x & empty)
{
attack |= x;
x = forward(x);
}
return attack;
}
and then put together my rook attack function as
for-all-rooks-do...
attack =
forwardattack(rooksquare)|backwardattack(rooksquare)|leftattack(rooksquare)|rightattack(rooksquare);
this would be much much cleaner instead of writing out the code all the time for
all attackers.
question: would that be slower than writing it out? will the compiler inline
such functions anyway?
3) the ray-tracing method is probably slower, but one of the benefits is that
you can continue ray-tracing once you hit an occupied square, so you can get
pins or x-ray-attacks. i don't see how to get such attacks easily in rotated
bitboard or kogge-stone formalism. am i missing something?
cheers
martin
occupied = p->
This page took 0.02 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.