Looking for dense magics

[lucasart]

Been looking at magic bitboards lately. My understanding is that, using the so called "fancy" approach (mainstream), it's easy to find magics that require a "natural" number of bits (eg. 12 bits for Ra1, 10 bits for Rb2, etc.). This is done by brute force, using sparsely populated random bitboards (as done in Stockfish fpr example).

But a lot harder to find "dense" magics, requiring fewer bits. Some have been found:
https://chessprogramming.wikispaces.com ... ics+so+far

How do you go about finding dense magics ? Are there "tricks" ? Or is it the same brute force approach, but using more patience ?

PS: I understand there is little interest for this nowadays, other than theoretical. Indeed the size of non dense magics is still small wrt typical hash table. Plus there are now PEXT bitboards (and even PEXT/PDEP), if you have recent hardware.

[jeffreyan11]

I tried this a while back. I used the same brute force approach, but wrote my own PRNG that biased towards integers I thought would be likely to work as magics. That took a lot of trial and error.

I found magics for the squares listed on there very quickly (average 1-2 sec per magic), but never found any others. I convinced myself that they don't exist and gave up.

[Volker Annuss]

Basically it is just more patience.

Some tricks may help:

- Look for magics with few bits set, with most bits set or with regions where only few bits are set and other regions with most bits set.

- When you have found two similar magics, also try all magics between them, for example with 11000010 and 11010000 also try 110000000 and 11010010.

- When you have found a magic number change a single bit.

[F. Bluemers]

Lately I have been looking for these keys too,especially the rook squares 48..63.
I've found them except 2,just or-ing masks with the key to test e.g.

Code: Select all

	//hints for some squares:
	//return (ranval()&0xffffffffffffff00ULL)|0x0000ff00FF000000ULL; 48,49,50,51,52,53
	//return (ranval()&0xffffffffffff0000ULL)|0x0000ff00FF000600ULL; 53
	//return ranval() & 0xffffFf63c96a0ULL; //for 55,slow??
	//return ranval()&(0xFFFF000000000000)|0xfff5f63c96a0ULL;//55 is finicky
	//return ranval()|0x00ffff00ff000000ULL;//for 56
	//return ranval()|0x000fff0000000000ULL;//for 57
	//return ranval()|0x00ffff00ff000000ULL; //58fast. 59,60
	//return ranval()|0x00fff00000ff0000ULL; //61slow
	//return ranval()|0x0001fff000000FF0ULL; //63

As an experiment I am playing with generating the 'hintmask' by shifting 0xff by multiples in three variables and 'or' these into the key.

Code: Select all

found magic (rook):  0xdfffff45ff3c6200 (41)bits square 48 shift 10 found 1 seconds used 33.669998
found magic (rook):  0xe8ffff5dff3a5e00 (42)bits square 49 shift 9 found 1 seconds used 177.856003
found magic (rook):  0x53ffff55ff65da00 (41)bits square 50 shift 9 found 1 seconds used 192.302994

[/quote]