Hi Gerd,
my magic factor generation is much too experimental to give some code here. Most of the implementation details are just a guess what might work and you might better test your own ideas and come up with something better.
Evaluation function (fitness function)
First you need an evaluation function (or fitness function in terms of genetic algorithms) for a magic number.
(1) In the first place it evaluates the number of bits in the index table. This is what you want to minimize. All other terms just help to guide the search.
I tried various other terms. All these terms seem to have the nasty property that they are helpful for some squares but bad for others.
(2) The number of unused entries at the end of the index table.
(3) The number of good collisions.
(4) The number of bad collisions when using one index bit less.
(5) How close is the popcount of the factor to 5, 6 .. or 10 or 54, 56 ..?
(6) Count how often a bit is different from its neighbour. How close is popcount( factor ^ (factor>>1) ) to 8, 9, ...
(7) Invent your own.
(8) see (7)
Although (5) and (6) only need a very small weight in the evaluation, having one of them is very helpful.
Make children
Take two parents. Every bit the parents have in common is copied to the child. Every bit that is different in the parents is replaced by a random bit.
c = (p1 & p2) | ((p1 ^ p2) & rnd64());
Sometimes flip one (or more) random bit(s) in the child.
Exception 1: When the child becomes equal to one of the parents, flip a random bit.
Exception 2: If both parents are equal, make the child a random number.
This prevents the whole population from beeing filled with the same number, making progress difficult.
Optimization
Fill an initial population with random factors.
Then simply pick two parents with a good evaluation (the better they are, the higher the probatility to pick them), create lots of children and replace some factors with a bad evaluation (the worse they are, the higher the probability to pick them) by the best evaluated children.
Make sure, that even the best factors have a chance to get killed to avoid dead ends.
Repeat this as long as you have CPU time left.
A big hash table that maps magic factors to evaluations is helpful.
A modified optimization algorithm tries to keep some losely connected local populations:
Divide the population in a left and a right half.
Select one parent from the right and one from the left.
Make lots of children and replace one factor from the left and one factor from the right by a good child.
Optimize the right and the left half recursively.
Greetings
Volker
PS: Looking into the Wiki, there are at least some 4 bit bishop magics you could need. So here is my complete list. A 10 bit rook magic for square 55 like the one by Grant Osborne is still undiscovered.
Code: Select all
Rook magics
0: 12 0x0080062081544001 4096
1: 11 0x004004500040600a 2048
2: 11 0xf7dfeff7fbfbf7df 2045
3: 11 0xfdfff6fabfe9ffed 2047
4: 11 0x7efffaffe9e7ffeb 2047
5: 11 0x09000c00028a8b00 2047
6: 11 0x7bfffeac6bfbfc02 2046
7: 12 0x020000d200640051 4095
8: 11 0x0002801082a4c000 2048
9: 10 0x0001400cd0002000 1024
10: 10 0x00ff1fff3e7e80e0 1019
11: 10 0xfffdffe5fdcdedf2 1022
12: 10 0x0002001212020408 1021
13: 10 0xfffdfff2eff9fffb 1023
14: 10 0xfffbfff5ddadae17 1022
15: 11 0x0b260000488e8e7c 2046
16: 11 0xc25082100808200f 2047
17: 10 0x9040404010002000 1024
18: 10 0x0230002000240800 1024
19: 10 0x4002020040102008 1024
20: 10 0x0002020008106004 1024
21: 10 0x0221010002080400 1024
22: 10 0x00000c00028a8b10 1023
23: 11 0x0130220012a0cb04 2048
24: 11 0x0000400180096090 2048
25: 10 0x005050004004a00a 1024
26: 10 0x0490002020040800 1024
27: 10 0x0002401200082200 1024
28: 10 0x0202001200040820 1024
29: 10 0x0086008080040002 1024
30: 10 0x0000100c00028a8b 1023
31: 11 0xc001000100004082 2048
32: 11 0x0000814010800428 2048
33: 10 0x80401008052000a0 1024
34: 10 0x80010010c1002000 1024
35: 10 0x0080100103000820 1024
36: 10 0x0002001412002008 1024
37: 10 0x8800810200800400 1024
38: 10 0x0400802300800200 1024
39: 11 0x002000910a000044 2048
40: 11 0x0001c00420808012 2048
41: 10 0x00202001d0094004 1024
42: 10 0x4090040800202000 1024
43: 10 0xffffd1ffcbd9ffec 1023
44: 10 0xff7feff1edf1fff7 1022
45: 10 0x000a000804020011 1024
46: 10 0xdefbdfe05f7c7ffe 1023
47: 11 0x0000b0b0c79dfffc 2047
48: 10 0xbfffff35ff5e5e00 1024
49: 9 0xdfffff7f868ee600 512
50: 9 0xffbfff9dffaf2e00 512
51: 9 0xffffffd1ffcf9e00 512
52: 9 0xffffffe9ffe7ce00 512
53: 9 0xfffffff5fff3e600 512
54: 10 0x0000c8c950414400 1023
55: 11 0x000000a400c1a200 2047
56: 11 0xf3ffffc1ffbf4f6e 2048
57: 10 0xf1ffff8161014f52 1024
58: 10 0xffffff7fb5ffa7ea 1024
59: 10 0xffffffb9ffdfb3f6 1024
60: 10 0xaffffff5ffdff2e6 1024
61: 11 0xf9fffffdfffe7772 2048
62: 10 0xfb7fffef27eebeac 1024
63: 11 0xffffffff3bff5e5e 2048
---------------------------------
89566
Bishop magics:
0: 5 0x0015090220e3fe00 32
1: 4 0xffeaf6fe3effffff 16
2: 5 0x550885d0e880dba0 30
3: 5 0x000e394092000000 31
4: 5 0x94170db89906a438 31
5: 5 0x0000a253a8000000 29
6: 4 0xffff5979f4ffffff 16
7: 5 0xfffeef16e70dffff 32
8: 4 0xffffd3eefbfe3fff 16
9: 4 0xffffeaf6fe3effff 16
10: 5 0x020208a5c9007000 30
11: 5 0x8f328e3924a08806 31
12: 5 0xaf78a8f2476f92c9 31
13: 5 0x000000a293a80000 29
14: 4 0xfffffbb9ba73ffff 16
15: 4 0xfffffeadde3bffff 16
16: 4 0x0040000a1509cfe0 16
17: 4 0x0020001a850327f0 16
18: 7 0x848f001e21b0e2f0 126
19: 7 0x0020201202014000 128
20: 7 0x0040800401a08000 128
21: 7 0xfff71ff78fddbaff 124
22: 4 0x00040000c549ff00 16
23: 4 0x0002000052a4dfc0 16
24: 5 0x0008d102220a0a01 31
25: 5 0x1090103022854260 31
26: 7 0x13435000980b8234 128
27: 9 0x0007828028020002 512
28: 9 0x0101840000802004 512
29: 7 0xffefff1fff8edd7f 125
30: 5 0x00040100805890e8 31
31: 5 0xfffdfdffff2f5e7f 31
32: 5 0x0002861a00401000 31
33: 5 0xfff9f2f97fe8a5ff 30
34: 7 0x0400805000210400 128
35: 9 0x0040400a00006200 512
36: 9 0x0010088200012200 512
37: 7 0xfffb7ddf0ffe1eff 126
38: 5 0x796cc69a53db8c7e 30
39: 5 0x5861307869b8dbc0 30
40: 4 0xf7bff669b5ffc037 16
41: 4 0x0007f3253a002000 16
42: 7 0x00001828d0000800 127
43: 7 0x0000006128060400 128
44: 7 0xbffffc7dfd1fba3f 127
45: 7 0xffa1f1b8bf0ff878 126
46: 4 0x003f89c540a00400 16
47: 4 0x001fc2c191a00200 16
48: 4 0xfffffe3bedd5ffff 16
49: 4 0xfffffefe376affff 16
50: 5 0xfffffebdbb943fff 30
51: 5 0xb67fbfffed2c3fff 32
52: 5 0xffffffebf71c6fff 30
53: 5 0xffff37858320dffe 29
54: 4 0xfffff7fc7bbd5fff 16
55: 4 0xfffffbfe3ddeafff 16
56: 5 0xffffff8dfdef59ff 32
57: 4 0xfffffffe7d337aff 16
58: 5 0x64014186e5aae4a2 30
59: 5 0x0000000003f410b0 32
60: 5 0x567b4ffeebf71c6f 30
61: 5 0x0000000ac66d60de 28
62: 4 0xfffffff8fbfb7d5f 16
63: 5 0xfffffbbe173b76eb 32
---------------------------------
4745