How to reduce the "bits" used in a magic number ca

[grant]

Magic number found!

H2 square 55 in my orientation 10-bit = 0x510FFFF5F63C96A0

Even after finding good patterns to OR into the randoms, it still took over 6 hours to find.
Whew.

Grant

[Aleks Peshkov]

Magic number found!

H2 square 55 in my orientation 10-bit = 0x510FFFF5F63C96A0

Does your magic numbers are public domain? If it is so it will be great to publish and update current best (perfect and super perfect) numbers for all squares in chess wiki.

[grant]

The rook set as requested.

0 A8 12 94800280A0400072 4096
1 B8 11 0440003000A00040 2048
2 C8 11 6900082000304100 2048
3 D8 11 8080080150001481 2048
4 E8 11 1D00070008001004 2048
5 F8 11 02000804100E000D 2048
6 G8 11 0200042801428200 2048
7 H8 12 0100010008802746 4096
8 A7 11 088080008030C001 2048
9 B7 10 4028802002400182 1024
10 C7 10 50FF002000350140 1024
11 D7 10 0101800803100080 1024
12 E7 10 A019000800104500 1024
13 F7 10 0008801400810200 1024
14 G7 10 10D2000B02003864 1024
15 H7 11 0262000148940201 2048
16 A6 11 0100868004304002 2048
17 B6 10 0820018020400282 1024
18 C6 10 00C2260011420480 1024
19 D6 10 0001010060689000 1024
20 E6 10 0891050011000801 1024
21 F6 10 41610100028C0058 1024
22 G6 10 185A44000D081210 1024
23 H6 11 449012000400C181 2048
24 A5 11 2F01A08080004002 2048
25 B5 10 101008C24004A002 1024
26 C5 10 2424F04500200104 1024
27 D5 10 004030010008A100 1024
28 E5 10 8291002D00109800 1024
29 F5 10 52120080800C0002 1024
30 G5 10 0008702400414208 1024
31 H5 11 4F010C2A00088B41 2048
32 A4 11 8040087040800080 2048
33 B4 10 21B0082001400040 1024
34 C4 10 0060002101004012 1024
35 D4 10 00B9891001002100 1024
36 E4 10 0891050011000801 1024
37 F4 10 4003044048011020 1024
38 G4 10 0D08300B14005882 1024
39 H4 11 08000E4102000484 2048
40 A3 11 00C580F040018000 2048
41 B3 10 0010024020004000 1024
42 C3 10 2221412009010010 1024
43 D3 10 8151043000090020 1024
44 E3 10 0121001008010004 1024
45 F3 10 8401000400790002 1024
46 G3 10 A0000502100C0008 1024
47 H3 11 9A8182448C020007 2048
48 A2 10 48FFFE99FECFAA00 1024
49 B2 9 48FFFE99FECFAA00 512
50 C2 9 497FFFADFF9C2E00 512
51 D2 9 613FFFDDFFCE9200 512
52 E2 10 A019000800104500 1024
53 F2 10 1020807401020080 1024
54 G2 10 00F2080A10110400 1024
55 H2 10 510FFFF5F63C96A0 1024
56 A1 11 EBFFFFB9FF9FC526 2048
57 B1 10 61FFFEDDFEEDAEAE 1024
58 C1 10 53BFFFEDFFDEB1A2 1024
59 D1 10 127FFFB9FFDFB5F6 1024
60 E1 10 411FFFDDFFDBF4D6 1024
61 F1 11 C012001004086942 2048
62 G1 11 4023080092104104 2048
63 H1 11 7645FFFECBFEA79E 2048

Grant

[Chas]

I remember trying this square about a year ago and I ended up being convinced that an 11-bit magic did not exist. I did get very close though, using 3500+ index numbers.
I would be interested to know close you got to finding this truely magic number.

Grant

I'm still looking for an 11-bit magic for rooks on square 0 (a1). I'm still just trying random numbers.

Results so far:
-- The program has tried 3,000,000,000 numbers.
-- The closest guess was at guess number 1,445,265,204.
-- The magic number guess was 0xAC00408201001C00.
-- Using this magic number guess:
........ The hashing function generated all numbers from 0 to 2047.
........ There were 2000 "good" collisions and 48 "bad" collisions.

My thought is that the guess with the fewest number of "bad" collisions is the best guess.

The program is still running.

Charlie

[grant]

Here are some bishop 4-bit magic numbers that you may not have.
In my engine A8=0 H8=7... H1=63.

A6 20403749D4C9EFDB
B6 02A0443A151B1FF7
A3 250FD6AA751E400C
B3 B6B7F549A5E1E023
H3 005FDB2561A00200

Grant

[jwes]

Might it make sense to split the rook magic into two pieces, as the rank can be done with a shift, an and, and a 64 by 8 byte lookup?

[grant]

Might it make sense to split the rook magic into two pieces, as the rank can be done with a shift, an and, and a 64 by 8 byte lookup?

I just tried masking off everything but the file for the difficult square 0 (A8 in my engine) and came up with a 5-bit magic number 0x22554D918DFF8058.


So would this work?

Code: Select all

occ = Occupied & &#40;0x0001010101010100 << &#40;square & 7&#41;);
	fileAddress = &#40;int&#41;(&#40;occ * MagicNr&#41; >> &#40;64 - rookShift&#91;square&#93;));
	rankAddress = &#40;char&#41;(&#40;Occupied >> &#40;square & 56&#41;) & rankMask&#91;square & 7&#93;);
	return (*rIndecies&#91;square&#93; + fileAddress&#41; | &#40;rankLookUp&#91;rankAddress&#93; << &#40;square & 56&#41;);

Grant

[Pradu]

Might it make sense to split the rook magic into two pieces, as the rank can be done with a shift, an and, and a 64 by 8 byte lookup?

Isn't this Gerd's "kindergarden" bitboards method (which actually predated the both-directions at once method Lasse)?

[Pradu]

Might it make sense to split the rook magic into two pieces, as the rank can be done with a shift, an and, and a 64 by 8 byte lookup?

I just tried masking off everything but the file for the difficult square 0 (A8 in my engine) and came up with a 5-bit magic number 0x22554D918DFF8058.


So would this work?

Code: Select all

occ = Occupied & &#40;0x0001010101010100 << &#40;square & 7&#41;);
	fileAddress = &#40;int&#41;(&#40;occ * MagicNr&#41; >> &#40;64 - rookShift&#91;square&#93;));
	rankAddress = &#40;char&#41;(&#40;Occupied >> &#40;square & 56&#41;) & rankMask&#91;square & 7&#93;);
	return (*rIndecies&#91;square&#93; + fileAddress&#41; | &#40;rankLookUp&#91;rankAddress&#93; << &#40;square & 56&#41;);

Grant

Well done. Using a better magic for multi-directional attacks is a good idea.

[grant]

Persuing this a little further, I can generate 5-bit rook magics for all squares except square 7 (H8 in my engine) which stubbornly is 6-bit, producing a rook table of 16K (actually a little less 15.2K + 0.5K for the ranks).

But, surely if I use Lasse Hansen's genius postmask, the rook table comes down to 2.25K + 0.5K

Code: Select all

occ = Occupied & &#40;0x0001010101010100 << &#40;square & 7&#41;); 
   fileAddress = &#40;int&#41;(&#40;occ * MagicNr&#41; >> &#40;64 - rookShift&#91;square&#93;)); 
   rankAddress = &#40;char&#41;((&#40;Occupied >> &#40;square & 56&#41;) >> 1&#41; & 0x3F&#41;; 
   return ((*rIndecies&#91;square&#93; + fileAddress&#41; & &#40;0x0101010101010101 << &#40;square & 7&#41;)) | (&#40;rankLookUp&#91;square&#93; + rankAddress&#41; << &#40;square & 56&#41;));

If I found the 5-bit magic for H8 I could replace 64 - rookShift[square] with 59.
Hope my assumptions are correct.

Grant