Fenner and Levene use masked lines (not necessarily excluding the sliding piece), that is bitboards with N=8 active bits with k={7,8,9} bits apart, starting with bit zero

they deduced two general perfect hashing functions. The case N <= k with

and the case N <= k + 1

This results in modulo 514 for diagonals, modulo 257 for anti-diagonals, and modulo 258 for files, to calculate the occupied index. Tables could made denser by storing indices, but that would require a second indirection. While Fenner and Levene used a Matlab 32-bit implementation to conclude their approach might be competitive, this is how it may be implemented in C by looking up pre-calculated attack-bitboards:

For ranks, diagonals or anti-diagonals, where the occupancy mask excludes the sliding piece, and the rank-or byte-wise sum of disjoint bits is therefor less than 255, Casting out 256-1 works as well, without any shifts required, and with more space saving options for the lookup table, i. e. similar to Kindergarten Bitboards with shared multiples of first rank attacks and an trailing post-mask with the same line ^{[3]}.

The 64-bit modulo by a constant can be done most efficiently by reciprocal fixed point multiplication, this is how MicrosoftVisual C++ 2005 compiler implements the mod constant for x86-64 processors. One 64*64=128 bit multiplication, one shift, one further 32-bit multiplication , one subtraction. Of course using 64-bit division to get the remainder burns even more cycles.

Quote from their paper pp 11 3.5. Comparison with other Methods

As reported in Hyatt (2007), the rotated and magic bitboard methods are of comparable performance, and Tannous (2007) claims just a small improvement of the direct lookup method over rotated bitboards. It is easy to see that, in terms of the number of computer operations, the efficiency of our method will be similar to that of direct lookup. Thus we are justified in claiming that the computational efficiency of our method is comparable to the others.

Their conclusion was based on following statement of Robert Hyatt^{[4]}...

I had reported this earlier. Magic was no faster than rotated. I switched because of two things...

1. Magic is simpler, and simpler is better as I get older.

2. Magic gives you the opportunity to update the occupied_squares and then generate moves easily.

To do this with rotated bitboards first requires that all rotated bitboards be updated in addition to the normal occupied_squares bitboard. This is faster, if you use the feature (I don't yet, but well might at times).

The results shown indicate that directly looking up the attacking moves for sliding pieces in hash tables improves the move generation speeds from 10% to 15% depending on computer architecture. Further efficiencies can be expected in a full implementation where the overhead of maintaining rotated bitboards is eliminated. The implementation and test code is made available in an Open-Source, interactive, chess programming module called “Shatranj” (Tannous, 2006).

## Table of Contents

Home * Board Representation * Bitboards * Sliding Piece Attacks * Congruent Modulo BitboardsCongruent Modulo Bitboardswas introduced by Trevor Fenner and Mark Levene in the ICGA Journal, Vol. 31, No. 1 in 2008^{[1]}. While their Perfect Hashing approach provides great mathematical insights in Congruent Modulo arithmetic, their final conclusion in comparison with Hashing Dictionaries, Rotated Bitboards and Magic Bitboards was criticized by the obvious comparison with Kindergarten Bitboards^{[2]}.## Modulo vs. Multiplication

BitScan broaches the issue of Perfect Hashing with Modulo versus Multiplication as well:So does the SWAR-Popcount, when it is about to finally add byte-wise populations:

## Modulo

## Congruence relation

Fenner and Levene use masked lines (not necessarily excluding the sliding piece), that is bitboards with N=8 active bits with k={7,8,9} bits apart, starting with bit zeroBased on Congruence relation

or equivalently

they deduced two general perfect hashing functions. The case N <= k with

and the case N <= k + 1

This results in modulo 514 for diagonals, modulo 257 for anti-diagonals, and modulo 258 for files, to calculate the occupied index. Tables could made denser by storing indices, but that would require a second indirection. While Fenner and Levene used a Matlab 32-bit implementation to conclude their approach might be competitive, this is how it may be implemented in C by looking up pre-calculated attack-bitboards:

## Casting out 255

For ranks, diagonals or anti-diagonals, where the occupancy mask excludes the sliding piece, and the rank-or byte-wise sum of disjoint bits is therefor less than 255, Casting out 256-1 works as well, without any shifts required, and with more space saving options for the lookup table, i. e. similar to Kindergarten Bitboards with shared multiples of first rank attacks and an trailing post-mask with the same line^{[3]}.## Reciprocal Multiplication

The 64-bit modulo by a constant can be done most efficiently by reciprocal fixed point multiplication, this is how Microsoft Visual C++ 2005 compiler implements the mod constant for x86-64 processors. One 64*64=128 bit multiplication, one shift, one further 32-bit multiplication , one subtraction. Of course using 64-bit division to get the remainder burns even more cycles.## Multiplication

A Kindergarten like approach might look like this (not considering inner six bits):and uses one 64*64=64-bit multiplication, with this x86-64 assembly for calculating an eight-bit occupied index:

Even Kindergarten File-Attacks are cheaper and faster, not to mention Magic Bitboards, which covers two lines of a rook or bishop in one run.

## Fenner's and Levene's conclusion

Quote from their paper pp 113.5. Comparison with other MethodsAs reported in Hyatt (2007), the rotated and magic bitboard methods are of comparable performance, and Tannous (2007) claims just a small improvement of the direct lookup method over rotated bitboards. It is easy to see that, in terms of the number of computer operations, the efficiency of our method will be similar to that of direct lookup. Thus we are justified in claiming that the computational efficiency of our method is comparable to the others.Their conclusion was based on following statement of Robert Hyatt

^{[4]}...I had reported this earlier. Magic was no faster than rotated. I switched because of two things...1. Magic is simpler, and simpler is better as I get older.2. Magic gives you the opportunity to update the occupied_squares and then generate moves easily.To do this with rotated bitboards first requires that all rotated bitboards be updated in addition to the normal occupied_squares bitboard. This is faster, if you use the feature (I don't yet, but well might at times)....and this claim of Sam Tannous^{[5]}:The results shown indicate that directly looking up the attacking moves for sliding pieces in hash tables improves the move generation speeds from 10% to 15% depending on computer architecture. Further efficiencies can be expected in a full implementation where the overhead of maintaining rotated bitboards is eliminated. The implementation and test code is made available in an Open-Source, interactive, chess programming module called “Shatranj” (Tannous, 2006).## Publications

1997).Perfect Hashing. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-1432008).Move Generation with Perfect Hashing Functions.ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf## Forum Posts

## External Links

## References

2008).Move Generation with Perfect Hashing Functions.ICGA Journal, Vol. 31, No. 1, pp. 3-12. pdf2007).Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pp. 85-91, pdf## What links here?

Up one Level