## question about magic keys generation time

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Contact:

### question about magic keys generation time

Hi,

I am trying to build my own magic number move generator. I am now in the proccess of generating my own keys for rook. I have written the code and trying testing, but I dont know yet if I have any bug. I am trying running and now are impatient. how much time does it take to generate magic for a squeare, aprox in a modern PC?

thanks.
Fermin Serrano
Author of 'Rodin' engine

brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

### Re: question about magic keys generation time

This is a very good book about magic bitboards http://www.pradu.us/old/Nov27_2008/Buzz ... boards.pdf

For me it takes about 0.5-1s to generate all magics (rooks and bishops). You need

1) A good hash function. I used

Code: Select all

``````	mul &#58;= magic * uint64&#40;bb&#41;
return uint&#40;uint32&#40;mul>>32^mul&#41; >> shift&#41;
``````
2) Good potential magics. Not my idea and I don't remember the origin
, but I used

Code: Select all

``````   r &#58;= uint64&#40;wiz.Rand.Int63&#40;))
r &= uint64&#40;wiz.Rand.Int63&#40;))
r &= uint64&#40;wiz.Rand.Int63&#40;))
return r<<6 + 1
``````
Also when searching for a shift, make sure you start high (13 for rook, 10 for bishop) and go down from there. Not all squares were created equal.

jordanbray
Posts: 52
Joined: Mon Aug 11, 2014 1:01 am

### Re: question about magic keys generation time

Code: Select all

``````   r &#58;= uint64&#40;wiz.Rand.Int63&#40;))
r &= uint64&#40;wiz.Rand.Int63&#40;))
r &= uint64&#40;wiz.Rand.Int63&#40;))
return r<<6 + 1
``````
Yea, something like this is very important. I do something similar, with (simplified):

Code: Select all

``````   return random_bitboard&#40;) & random_bitboard&#40;) & random_bitboard&#40;) & random_bitboard&#40;);
``````
where I have a custom (KISS) random number generator. I also don't know where this idea comes from, but the and operations are important to reduce the number of bits in the generated random number. This allows more of the bits in the resulting multiplication to shift, rather than just become garbage.

Choosing a good random number generator was the most significant speedup that I got.

I do not start at a particular square when generating, but thats a good idea. Mine takes around 5 seconds, but I also generate more than just the piece tables. I also have not taken the time to optimize it at all, other than to make it take a reasonable amount of time.

Gerd Isenberg
Posts: 2200
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

### Re: question about magic keys generation time

Kempelen wrote:Hi,

I am trying to build my own magic number move generator. I am now in the proccess of generating my own keys for rook. I have written the code and trying testing, but I dont know yet if I have any bug. I am trying running and now are impatient. how much time does it take to generate magic for a squeare, aprox in a modern PC?

thanks.
for square table sizes == 2 ** number of relevant occupied bits (5..9 for bishops, 10..12 for rooks) less than a second for all squares. See Tord's reply and cpw
http://www.talkchess.com/forum/viewtopi ... 34&t=19699
https://chessprogramming.wikispaces.com ... for+Magics

Trying to half table size for many squares may take much longer
Instead of sparse populated randoms, you may also try snoob, that is enumerate all sets with 4 or 5 bits ...
https://chessprogramming.wikispaces.com ... ardinality

Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Contact:

### Re: question about magic keys generation time

Thanks!

I get it! aprox 2 seconds for all squares.
Fermin Serrano
Author of 'Rodin' engine

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

### Re: question about magic keys generation time

Thanks for opening this thread: I have found some energy to look again at magic generation in SF, and after profiling I realized there was a very costly memset() in the code...I have rewritten the logic dropping the memset and managed to double magic generation speed!

Now it takes less than 100 msecs for all squares (bishop + rooks).

For the interested people, here is the code:

https://github.com/mcostalba/Stockfish/ ... d.cpp#L245