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.
Post Reply
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

question about magic keys generation time

Post by Kempelen » Thu Mar 19, 2015 7:32 pm

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
http://sites.google.com/site/clonfsp/

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

Re: question about magic keys generation time

Post by brtzsnr » Thu Mar 19, 2015 8:19 pm

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 := magic * uint64(bb)
	return uint(uint32(mul>>32^mul) >> shift)
2) Good potential magics. Not my idea and I don't remember the origin
, but I used

Code: Select all

   r := uint64(wiz.Rand.Int63())
	r &= uint64(wiz.Rand.Int63())
	r &= uint64(wiz.Rand.Int63())
	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

Post by jordanbray » Thu Mar 19, 2015 10:05 pm

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

Post by Gerd Isenberg » Fri Mar 20, 2015 7:45 pm

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

User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Re: question about magic keys generation time

Post by Kempelen » Sat Mar 21, 2015 3:05 pm

Thanks!

I get it! aprox 2 seconds for all squares.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

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

Re: question about magic keys generation time

Post by mcostalba » Sun Mar 22, 2015 11:15 am

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

Post Reply