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
magic bitboards
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: magic bitboards
The original explanation for rotated bitboards can be found in the ICGA journal, or on my web page at www.cis.uab.edu...Pierre Bokma wrote: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
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...
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: magic bitboards
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.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: magic bitboards
I quite like rotated bitboards, because:Mincho Georgiev wrote: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.
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 (rank_slides[f][(occ->all >> (r * 8)) & 0xFF] << (r * 8))
| (file_slides[r][(occ->all_sym >> (f * 8)) & 0xFF] << f);
}
U64 bishop_attack(const occ_t *occ, int sq)
{
assert(square_ok(sq));
int r = rank(sq), f = file(sq),
diagno_a1h8 = r + f,
diagno_a8h1 = 7-r + f;
U64 occ_a1h8 = (occ->all_a1h8 >> diag_shift[diagno_a1h8]) & diag_mask[diagno_a1h8],
occ_a8h1 = (occ->all_a8h1 >> diag_shift[diagno_a8h1]) & diag_mask[diagno_a8h1];
return diag_a1h8_slides[sq][occ_a1h8] | diag_a8h1_slides[sq][occ_a8h1];
}
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
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: magic bitboards
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.
-
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: magic bitboards
Hello Pierre,Pierre Bokma wrote: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
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
-
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: magic bitboards
full implementation you can find here at page 2 ...Desperado wrote:Hello Pierre,Pierre Bokma wrote: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
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 OD
and the introduction...
introduction OD
cheers