32-bit Magic experiments

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

32-bit Magic experiments

Postby Andrew Fan » 03 Dec 2009, 14:21

I'm going to bore you with my own magic stuff. If you're not comfortable with bits, rotates and shifts, then move on :P

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

Flattening it out to two 32-bit parts:

Code: Select all

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
......6......5......4..........7   rol 8

...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
   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.
User avatar
Andrew Fan
Posts: 7
Joined: 24 May 2008, 07:40

Re: 32-bit Magic experiments

Postby Zach Wegner » 04 Dec 2009, 20:43

Hmm, this looks very similar to a method I came up with around the same time (posted here on August 22, 2006):


It's formulated a bit differently, but it uses the same type of constant. Mine is just for files though. For ranks and diagonals, you can just OR the upper and lower dwords, smear them up and shift one to the left by multiplying by 0x02020202, then shifting right by 26.
User avatar
Zach Wegner
Posts: 182
Joined: 26 Sep 2004, 22:02
Location: Austin, Texas, USA

Re: 32-bit Magic experiments

Postby smithdwsn » 28 May 2010, 17:02

Amazing work!.
Posts: 4
Joined: 27 May 2010, 20:15

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 4 guests