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

[Edmund]

Edmund

I don't see any errors in my code. I have now checked and double checked again, and it works.
B2 is square 49 for me, so maybe B7 for you. Could you check again?

I have also found more 9-bit magic numbers for rooks so it would be nice to get this verified.

Grant

sorry, I was using a different metric indeed I was talking about square 9.

Do you have any 9-bit magic for this square?

[grant]

Edmund

I'll have a look at B7 for you now.

Grant

[Edmund]

Edmund

I'll have a look at B7 for you now.

Grant

great - any success so far?

[grant]

For B7 the results are not good. Best I can get is 527 index numbers used with 176 good collisions, though if I don't see any progress after about 5 minutes I get bored and try something else.

You will have better success at the other end of the board. I have 9-bit magics for B2, C2 & D2, and goods results for G2 with 992 index numbers and 558 collisions. H2 10-bit is really close also.

Grant

[Edmund]

For B7 the results are not good. Best I can get is 527 index numbers used with 176 good collisions, though if I don't see any progress after about 5 minutes I get bored and try something else.

You will have better success at the other end of the board. I have 9-bit magics for B2, C2 & D2, and goods results for G2 with 992 index numbers and 558 collisions. H2 10-bit is really close also.

Grant

thats unfortunate, but I thought so. Thanks anyway for your efforts.

[Chas]

I'm starting to be a believer in the "don't just use random numbers" to find optimal magics strategy.

I've had a program running for two days using random numbers with very few bits set looking for an 11-bit magic for square 0 (a1). It has tried 20,000,000,000 numbers. None of them has worked.

I think I'd better start look at setting groups of bits to see how they affect the relative success of a magic.

Of course, the rest of you knew that already.

Regards!

[Edmund]

I'm starting to be a believer in the "don't just use random numbers" to find optimal magics strategy.

I've had a program running for two days using random numbers with very few bits set looking for an 11-bit magic for square 0 (a1). It has tried 20,000,000,000 numbers. None of them has worked.

I think I'd better start look at setting groups of bits to see how they affect the relative success of a magic.

Of course, the rest of you knew that already.

Regards!

I am not quite sure, whether there are any optimizations for this square, probably Grant is right saying that the other end of the board is easier.

[grant]

I'm starting to be a believer in the "don't just use random numbers" to find optimal magics strategy.

I've had a program running for two days using random numbers with very few bits set looking for an 11-bit magic for square 0 (a1). It has tried 20,000,000,000 numbers. None of them has worked.

I think I'd better start look at setting groups of bits to see how they affect the relative success of a magic.

Of course, the rest of you knew that already.

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

[grant]

Edmund

I may have mis-understood your terminology.
I measure the potential of finding a magic number by counting the first n number of occupancies that I can fit into half this number.
So for B7 I get the first 527 of 1024 to fit into 512
for G2 I get 992 of 1024 into 512
for A1 I get 3500+ of 4096 into 2048

Based on my results so far, G2 and H2 are very good candidates for searching.

Grant

[Edmund]

Edmund

I may have mis-understood your terminology.
I measure the potential of finding a magic number by counting the first n number of occupancies that I can fit into half this number.
So for B7 I get the first 527 of 1024 to fit into 512
for G2 I get 992 of 1024 into 512
for A1 I get 3500+ of 4096 into 2048

Based on my results so far, G2 and H2 are very good candidates for searching.

Grant

I did it row by row:
for example sq#9:

First I start where the file has no pieces and try to fit the 6 possible occupancies from the row into as little index numbers as possible (the occupancies are all subsets of 0x7c00). For this I found that the lowest possible index number usage was 14 and the bit-pattern that all the magic numbers had in common was: xxxxxxxx xxxxx011 11111111 1xxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx.b

Then I continued with the subsets of the occupancy 0x2000000007c00. I was using the bit-pattern gained from the previous step. The lowest number of indexes used here was 34. Here again I got a pattern I used for the next steps.

For the occupancy 0x2020000007c00 I got the minimum of 68 indexes, for 0x2020200007c00 136 indexes and for 0x2020202007c00 280. For the last step (0x2020202027c00) I didn't find anymore magics, probably due to the fact that the number of indexes used > 2^9

I now concluded that it was close, because I saw a development of the indexes used about at the rate of 17*2^[nr of file-occupancy bits]
Edit: and 17*2^5=544 is close to 2^9

Another idea: in the case we weren't able to find a bit-reduction for a certain square, we should still try to find a magic number that reduces the highest index number used, as this would still be a good improvement.

Edmund