Below describes a "simple" method of generating attack/mobility rays for sliding pieces using 32-bit constant magic multiplications in a computer chess program that uses the bitboard method to represent the chess board.
The method is no intended as a replacement for the 64-bit magic mulplication method by Pradu et al (boring paper :P) but as an alternative to that method, especially for 32-bit CPUs.
To start with, let's look at a single diagonal of a bishop in a bitboard:
- Code: Select all
.......7
......6.
.....5..
....4...
...3....
..2.....
.1......
0.......
Flattening it out to two 32-bit parts:
- Code: Select all
10987654321098765432109876543210
.......7......6......5......4...
...3......2......1......0.......
The idea is to use a magic multiplier (shift and add) to collect the bits together, forming an 8-bit index.
An earlier attempt for this diagonal using shifts had a problem of requiring 9-bits to hold the unique indices. Upon further investingation, a rotation is used to overcome this problem and an 8-bit index can be generated:
- Code: Select all
10987654321098765432109876543210
......6......5......4..........7 rol 8
...3......2......1......0.......
...3..6...2..5...1..4...0......7 Upper and lower 32-bits OR'ed after rotation of upper bits
6...2..5...1..4...0......7 Shift and add/or (no overflow) a few times to collect the bits
.5...1..4...0......7
..0......7
010000000001000001000001 Magic multiplier in binary
03216547 >> 22 Shift to move the index back to bits 7-0
0x00401041 Magic multiplier in hex
The complete operation is:
Index = (((rol(Upper32,8) | Lower32) * 0x401041) >> 22) & 0xff
The index can now be used to look up a pre-generated attack map for a given square on that diagonal. The last masking is there to gurantee the index range is correct. It may be superficial but safer to have it included.
By applying this method to all the same diagonals, it is found that a constant magic value can be used! No need to search for a magic value for each square for weeks!
The downside of this is the resulting index's bit number mapping is no longer in the normal order, this problem can be overcome with some bit remapping code when generating the attack map.
This is only one diagonal. For a full set of attack maps, we need to do the same operations to get another index to look up, then combine the results. Hence this will take 2 32-bit multiplications as oppose to one 64-bit multiplication as with the more popular method but a lot simplicity to find the magic values.
If an 8-bit index sounds too much then it may be possible to reduce it to 6-bits by not including the edge bits to begin with. I have not verified this with the diagonals but have done so for the rank and file indices.
This 32-bit magic implementation has been active in my own engine for a few years now (2006 earliest recorded file time) and I have no plan to move onto the "proper" 64-bit version.
The rest I leave as an exercise, and discover things for yourselves. It should take you a few hours by hand so you now have a perfect excuse to not sit in front of the computer. Ok, I'll let you use your Gigaflops machine to emulate pen and paper
Have fun.
