Looking for dense magics

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
lucasart
Posts: 3110
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Looking for dense magics

Post by lucasart » Tue Jul 11, 2017 2:21 pm

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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

jeffreyan11
Posts: 46
Joined: Sat Sep 12, 2015 3:23 am
Location: United States

Re: Looking for dense magics

Post by jeffreyan11 » Tue Jul 11, 2017 2:36 pm

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
Posts: 173
Joined: Mon Sep 03, 2007 7:15 am

Re: Looking for dense magics

Post by Volker Annuss » Tue Jul 11, 2017 7:55 pm

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
Posts: 860
Joined: Thu Mar 09, 2006 10:21 pm
Location: Nederland
Contact:

Re: Looking for dense magics

Post by F. Bluemers » Tue Jul 11, 2017 8:05 pm

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]

Post Reply