question about magic keys generation time

[Kempelen]

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.

[brtzsnr]

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]

Code: Select all

   r := uint64(wiz.Rand.Int63())
   r &= uint64(wiz.Rand.Int63())
   r &= uint64(wiz.Rand.Int63())
   return r<<6 + 1 

Yea, something like this is very important. I do something similar, with (simplified):

Code: Select all

   return random_bitboard() & random_bitboard() & random_bitboard() & random_bitboard();

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]

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]

Thanks!

I get it! aprox 2 seconds for all squares.

[mcostalba]

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