magic bitboards

[Pierre Bokma]

Hi Friends,

During my holiday i restarted working on my engine. I have replaced my own rotated bitboard code by magic bitboards using Pradyumma Kannan 's code. To my surprice (or rather disappointment) there was no speed gain at all! So, any ideas about what can be worng and does anybody know a reference to a good explaination of rotated bitboards?

regards Pierre

[bob]

Hi Friends,

During my holiday i restarted working on my engine. I have replaced my own rotated bitboard code by magic bitboards using Pradyumma Kannan 's code. To my surprice (or rather disappointment) there was no speed gain at all! So, any ideas about what can be worng and does anybody know a reference to a good explaination of rotated bitboards?

regards Pierre

The original explanation for rotated bitboards can be found in the ICGA journal, or on my web page at www.cis.uab.edu...

However, magic bitboards are not faster than rotated. I have posted this previously. What they gain you is that you don't have to maintain the rotated versions, which simplifies your code and might make your cache footprint smaller; but more importantly, it is easier to change just one occupied square bitboard and then do a magic move generation to see how that changed affected mobility, or legal moves, or whatever. With rotated, you have to change all 4 rotated/normal boards, do the movgen lookup, and then restore the rotated stuff back.

So you probably won't see much of any speed advantage until you start to figure out how you can use the extra flexibility of magic generation as mentioned above...

[Mincho Georgiev]

The reason for me to start dealing with magics was not speed gain, but their execution simplicity compared to rotated bitboards. This comes with a price, which is the memory consumed for the hash table. So for me the optimal approach was Pradu's reduced array size appr. There are faster, but this one I like the most.

[lucasart]

The reason for me to start dealing with magics was not speed gain, but their execution simplicity compared to rotated bitboards. This comes with a price, which is the memory consumed for the hash table. So for me the optimal approach was Pradu's reduced array size appr. There are faster, but this one I like the most.

I quite like rotated bitboards, because:
1/ simpler to understand and implement than magic (IMO)
2/ use less memory
The only advantage I can think of with magic bitboards is that you need only one occupancy bitboard.. But that's not really a problem. In my code, I basically have an "object" for occupancies, and methods to manipulate it

Code: Select all

typedef struct {
	U64 all, all_sym, all_a1h8, all_a8h1;
} occ_t;

void clear_occ(occ_t *occ, int sq)
{
	assert(square_ok(sq));
	clear_bit(&occ->all, sq);
	clear_bit(&occ->all_sym, square(file(sq), rank(sq)));
	clear_bit(&occ->all_a1h8, rot_a1h8[sq]);
	clear_bit(&occ->all_a8h1, rot_a8h1[sq]);
}

void set_occ(occ_t *occ, int sq)
{
	assert(square_ok(sq));
	set_bit(&occ->all, sq);
	set_bit(&occ->all_sym, square(file(sq), rank(sq)));
	set_bit(&occ->all_a1h8, rot_a1h8[sq]);
	set_bit(&occ->all_a8h1, rot_a8h1[sq]);
}

U64 rook_attack(const occ_t *occ, int sq)
{
	assert(square_ok(sq));
	int r = rank(sq), f = file(sq);

	return &#40;rank_slides&#91;f&#93;&#91;&#40;occ->all >> &#40;r * 8&#41;) & 0xFF&#93; << &#40;r * 8&#41;)
	       | &#40;file_slides&#91;r&#93;&#91;&#40;occ->all_sym >> &#40;f * 8&#41;) & 0xFF&#93; << f&#41;;
&#125;

U64 bishop_attack&#40;const occ_t *occ, int sq&#41;
&#123;
	assert&#40;square_ok&#40;sq&#41;);
	int r = rank&#40;sq&#41;, f = file&#40;sq&#41;,
	    diagno_a1h8 = r + f,
	    diagno_a8h1 = 7-r + f;

	U64 occ_a1h8 = &#40;occ->all_a1h8 >> diag_shift&#91;diagno_a1h8&#93;) & diag_mask&#91;diagno_a1h8&#93;,
	    occ_a8h1 = &#40;occ->all_a8h1 >> diag_shift&#91;diagno_a8h1&#93;) & diag_mask&#91;diagno_a8h1&#93;;

	return diag_a1h8_slides&#91;sq&#93;&#91;occ_a1h8&#93; | diag_a8h1_slides&#91;sq&#93;&#91;occ_a8h1&#93;;
&#125;

This ensures never screwing things up (modifying one of the rotate BB and not the others accordingly etc.) And in the end the code for using it is very simple. In C++ you could even have a cast operator and bitwise operators overloaded to manage occ_t as if they were normal bitboards...

In terms of perf:
1/ rotated BB requires 4 calls to clear/set bit every time i/o 1 for magic
2/ magic on the other hand use a lot of ram, and maybe that's not very cache friendly. I don't know though.
3/ bishop and rook attacks are faster to compute with magics, but diluted in all the other things that your program is doing, I don't think that's going to be a significant waste of time.

So really you shouldn't expect any improvement in terms of speed, nor in terms of code simplicity. However it's true that magics have a certain inner beauty, and that alone is a good reason to play with them

[Mincho Georgiev]

I was talking about simpler for execution, not simpler to understand. Plus the code overall is simpler with magics, IMO. Agreed with the memory issue though but that's the price.

[Desperado]

Hi Friends,

During my holiday i restarted working on my engine. I have replaced my own rotated bitboard code by magic bitboards using Pradyumma Kannan 's code. To my surprice (or rather disappointment) there was no speed gain at all! So, any ideas about what can be worng and does anybody know a reference to a good explaination of rotated bitboards?

regards Pierre

Hello Pierre,

well the thoroughly efficient magics and rotated approaches are not the
only fast ones. If you never heard of OD (Obstruction Difference) it might
be worth a look. It has a very easy, transparent to follow, and undestandable code.
Its memory requirements may be neglible (it belongs to the direct computing category)
and the speed is comparable with rotated bitboards, while it is handy as magics (in usage) at the same time.
You can find an introduction at chessprogramming wiki, or if you search
the forum you will even find complete implementations.

Michael

[Desperado]

Hi Friends,

During my holiday i restarted working on my engine. I have replaced my own rotated bitboard code by magic bitboards using Pradyumma Kannan 's code. To my surprice (or rather disappointment) there was no speed gain at all! So, any ideas about what can be worng and does anybody know a reference to a good explaination of rotated bitboards?

regards Pierre

Hello Pierre,

well the thoroughly efficient magics and rotated approaches are not the
only fast ones. If you never heard of OD (Obstruction Difference) it might
be worth a look. It has a very easy, transparent to follow, and undestandable code.
Its memory requirements may be neglible (it belongs to the direct computing category)
and the speed is comparable with rotated bitboards, while it is handy as magics (in usage) at the same time.
You can find an introduction at chessprogramming wiki, or if you search
the forum you will even find complete implementations.

Michael

full implementation you can find here at page 2 ...

full implementation OD

and the introduction...

introduction OD

cheers