Page 1 of 1
question about magic keys generation time
Posted: Thu Mar 19, 2015 8:32 pm
by 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.
Re: question about magic keys generation time
Posted: Thu Mar 19, 2015 9:19 pm
by 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.
Re: question about magic keys generation time
Posted: Thu Mar 19, 2015 11:05 pm
by 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.
Re: question about magic keys generation time
Posted: Fri Mar 20, 2015 8:45 pm
by Gerd Isenberg
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
Re: question about magic keys generation time
Posted: Sat Mar 21, 2015 4:05 pm
by Kempelen
Thanks!
I get it! aprox 2 seconds for all squares.
Re: question about magic keys generation time
Posted: Sun Mar 22, 2015 12:15 pm
by 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