Where to generate Attack Tables

[Gerd Isenberg]

Ideal to generate attack sets from scratch is while "waiting" for a hash-probe, for instance x64 prefetch-instruction combined with SSE2 fill-stuff to compute sliding attacks.

Whoah... I'm a member since 1998 ( give or take a few years ), so maybe it's a bit late to introduce myself. I'm a professional business application programmer and I have always worked with high level programming languages ( 4GL's as they used to be called ). The only speed optimization I had ever to worry about where adding indexes to ( or refactoring ) slow queries. I'm a C/C++ autodidact and I am already happy I mastered the syntax.

Although I always find your posts interesting, I am not even close to the level where one would start to understand a small part of them.

Anyway I'm in the designing phase and didn't even think about hashing yet. But when I will come to it, I will put the probe right before the generation of the attack tables

Random reads from huge GB hash-tables burn a lot of cycles, since it is likely a non cached memory read. I am not sure with recent processors (core2 and nehalem), but it may be hundreds of cycles, or two to three times the main memory latency due to tlb issues. This might be nice for hyperthreading, but it is a reason why many programs don't hash huge tables in qsearch.

One may try Dieter Bürßner's dblat to get an idea.

With my current 64-program on an amd K8, and hashing everywhere, using prefetch (as intrinsic C-Function) or not, is something like 1.7 versus 1.5 mnps. As Matthias said this requires some fun and lust with low-level-stuff, understanding generated assembly, simd-istructions (but not necessary snoob - same number of one bits . I use directionwise fill-algorithms to do a lot of pure 128-bit register computation with only rare memory writes of the generated attacks (for both sides) and 16 direction-wise legal-move target bitboards as an unsorted move-list.

As always, exponential improvements and implementing the "right" knowledge in search and eval is much more important (not to mention a good parallel search), than a few percent linear speedup. In my old Dos-program I did incremental update of attack tables and related stuff during make/unmake. While it was quite nice most of the time, performance dropped significantly in queen endings.

[Matthias Gemuh]

As Matthias said this requires some fun and lust with low-level-stuff, understanding generated assembly, simd-istructions (but not necessary snoob - same number of one bits .

Hi Gerd,
my joke was to point out that I never understand your posts, though they always sound very interesting .
I found assembly impossible to learn.
regards,
Matthias.

[Gerd Isenberg]

Hi Gerd,
my joke was to point out that I never understand your posts, though they always sound very interesting .
I found assembly impossible to learn.
regards,
Matthias.

Hi Matthias,
no problem. I grew up with 8/16-bit assembly and today SSE2 within C++ is the fun stuff for me. Instead I have problems to understand all the statistics here recently

Cheers,
Gerd

[Edsel Apostol]

I am sure other people do something more creative but I generate a list of attack bitboards just before I need to detect in check then use them for detecting hanging pieces to narrow the futility cut off, move ordering, evasions, movegen, and many things in eval. Generating them in eval would only make sense to me if you are using a full eval at every node.

I do full eval in every node but I don't use the generated attack tables for other things except inside the eval. It seems I'm trying to do some redundant work on my move ordering and move generation. This gives me some ideas to make my engine faster. Thanks for the post.

Do you currently hash eval? If this is the case speedup might not be spectacular, depends on your hitrate and how expensive your attack tables are of course. I am curious how it works out for you.

I don't hash my eval. My attack tables are used in computing mobility, king attacks and passed pawn.

I'm thinking that if I could calculate it outside of the eval, I could also use it in other things like move generation, SEE, and it seems like a big savings in calculation.

Computation of piece attacks in my engine is not that expensive.

Here's my current data structure for eval:

Code: Select all

typedef struct{
    uint64 atkall[2];
    uint64 atkpawns[2];
    uint64 atkknights[2];
    uint64 atkbishops[2];
    uint64 atkrooks[2];
    uint64 atkqueens[2];
    uint64 atkkings[2];
    int32 open_score[2];
    int32 end_score[2];
    int32 phase;
    pawn_entry_t *pawn_entry;
}eval_info_t;

It's not a table actually but a collection of variable that stores attacks by specific pieces.

I noticed that using this in my king attacks and passed pawn eval is not that accurate. For example if there are more than one specific kind of piece that attacks a specific square, only one bit is being set.

My question is what is the best data structure to hold the attack tables? The most simple (and the only one I could think of for now) is a bitboard array of 64 elements (512 bytes). Another idea might be to use an array of 16 elements for both sides, reducing the table size by half, but I don't want to complicate the code by having piece lists.

[Edmund]

My question is what is the best data structure to hold the attack tables? The most simple (and the only one I could think of for now) is a bitboard array of 64 elements (512 bytes). Another idea might be to use an array of 16 elements for both sides, reducing the table size by half, but I don't want to complicate the code by having piece lists.

I am using 2 bytes per position, 1 for each color:

pawns 2bit
b/n 2bit
r 2bit
q 1bit
k 1bit

I also use this data to address a S16 table[6][256][256] to get the see values for certain captures.

The latter idea is quite close to what Bruce Moreland used.

Before I tried to do something similar with Bitboards
U64 p_att_0[2];
U64 p_att_1[2];
U64 p_att_2[2];
U64 bn_att_0[2];
...

using these structures I got a branchless SEE calculation working, where the whole board was treated at once. Anyway, this wouldn't work in my current implementation, so I stopped using it.

[Edsel Apostol]

My question is what is the best data structure to hold the attack tables? The most simple (and the only one I could think of for now) is a bitboard array of 64 elements (512 bytes). Another idea might be to use an array of 16 elements for both sides, reducing the table size by half, but I don't want to complicate the code by having piece lists.

I am using 2 bytes per position, 1 for each color:

pawns 2bit
b/n 2bit
r 2bit
q 1bit
k 1bit

I also use this data to address a S16 table[6][256][256] to get the see values for certain captures.

The latter idea is quite close to what Bruce Moreland used.

Before I tried to do something similar with Bitboards
U64 p_att_0[2];
U64 p_att_1[2];
U64 p_att_2[2];
U64 bn_att_0[2];
...

using these structures I got a branchless SEE calculation working, where the whole board was treated at once. Anyway, this wouldn't work in my current implementation, so I stopped using it.

This is great for precomputed SEE but I don't think that it could be used for move generation.

Another idea is to use 8 bitboards for 8 queen direction, 4 for the rook, 4 for the queen, 2 for the knight (1 upward and 1 downward) and 2 for pawns. 20 bitboards in total.

[Desperado]

Hi,

i am also very confused about attack-tables because of the following points.

1. i am not sure if you are talking about board-controls or just attacked
pieces, also not sure about "flagging" or "counting".

2. once i played around with incremental updates (board controls counting), and if i remember right, only about 35% (on average) of board controls were kept from ply to ply. For example a pawn push opens files,ranks for bishops,rooks,queens... So there has to be figured out for what pieces the update has to be done. Maybe (of course ) i missed something with the incremental approach, so i would be happy if someone can tell me the clue.

3. i am using magic bitboards, very fast to compute mobility(counter).
But if i am adding info to attacktable like this:

Code: Select all

//PSEUDOCODE
			 case wq: 
					 ctl = Q_MAGIC(occ,sq64);
					 while(ctl)
						{
						 //the multiple bsf64 instruction for any piece in any mobility loop is 
						 //killing my performance totally... :-( 
						 controls.inc_wq(bsf64(ctl));
						 BONUS_WHITE(score,v_mob_q[++cnt]);
						 CLB64(ctl);
						}
					 break;

//so i would like to understand the incremental stuff...

So my main problem seems to be, not to understand how to handle the "passive" changes of board controls in an incremental way !? so i wonder how the people use the incremental approach...

[Aleks Peshkov]

2. once i played around with incremental updates (board controls counting), and if i remember right, only about 35% (on average) of board controls were kept from ply to ply. For example a pawn push opens files,ranks for bishops,rooks,queens... So there has to be figured out for what pieces the update has to be done. Maybe (of course ) i missed something with the incremental approach, so i would be happy if someone can tell me the clue.

My own middlegame perft stats observations that on average no more then 1 sliding attackers for each side (plus the moved piece) should be recalculated each node.

Capturing move change only 1 square. Your attack table should have a fast way to found a set or list of sliding attackers (for both sides) of the square that last moved piece suddenly releases.

Regular move affect 2 squares: from and to. En passant capture affect 3 squares, but otherwise it is not difficult to handle.

[smcracraft]

I tried maintaining attack tables
in the update() and downdate()
portion after making and unmaking
moves.

It was quite expensive with bitboards,
at least, in my implementation, so
I turned the code off.

Now, I only use attack maps as needed
in eval and believe that is the better
course.

The Chess 0.5/4.x group by the Northwestern
group may have done somewhat of a disservice
to the community by making it seem like
these are normal, prudent and best to have
outside of eval.

I don't happen to think that.

They are expensive to maintain, even
with special-purpose coding.

Has anyone done more studies of
attack-map always-on vs. only-when-needed?

Stuart

[bob]

I tried maintaining attack tables
in the update() and downdate()
portion after making and unmaking
moves.

It was quite expensive with bitboards,
at least, in my implementation, so
I turned the code off.

Now, I only use attack maps as needed
in eval and believe that is the better
course.

The Chess 0.5/4.x group by the Northwestern
group may have done somewhat of a disservice
to the community by making it seem like
these are normal, prudent and best to have
outside of eval.

I don't happen to think that.

They are expensive to maintain, even
with special-purpose coding.

Has anyone done more studies of
attack-map always-on vs. only-when-needed?

Stuart

I discarded that within a year of developing Crafty. I don't think the cost is justified by the result...

I just calculate whatever I need, when I need it.