Winboard Forum

by **Grant Osborne** » 23 Mar 2012, 15:17

My engine generates only legal moves and to do so I initially create a bitboard of pinned pieces and their pinners using magics. (As a by-product I get other information including whether or not I am in check). Being unable to find 14 bit rooks for all squares I was forced to use less bits.
I can't remember which squares failed but I shall take another look. If you use a constant to re-locate the bits you will probably have to use a different constant for each square and you may not need to AND it with its compliment as the occupancy has already been masked.

Grant

by **crystalclear** » 25 Mar 2012, 22:31

I can't remember which squares failed but I shall take another look. If you use a constant to re-locate the bits you will probably have to use a different constant for each square and you may not need to AND it with its compliment as the occupancy has already been masked.

I failed to find most 14 bit rook magics. I found about a dozen of them. Repeated attempts to find magics would give me the same ones, and so I got a feeling that there was a mathematical difficulty or even impossibility for some of the remaining magics. That's why I decided to use bit relocation. With relocation I now have a complete set. I do have a bit relocation constant for each square. Some of the constants are the same, e.g. I used a constant of zero for the 14 bit magics that already worked, but essentially I have 64 constants for bit-relocation. The fact that some are the same is neither here nor there.

I did wonder if I could get away with not performing the AND operation with the complement of the constant, but at the moment I just want some working software and I'm not after any sort of optimization.

The magic numbers tend to permute the occupancy bits at the same time as they are collated. But it is (I think) also possible that indexes are muddled. Here's what I mean ...

Example of collated bits getting permuted.
-0-0 -> 00
-0-1 -> 10
-1-0 -> 01
-1-1 -> 11

Example of index getting muddled.
-0-0 -> 00
-0-1 -> 11
-1-0 -> 01
-1-1 -> 10

So I am now wondering if it is possible to generate magic numbers for permutation only, without muddling.
I have not checked, but I suspect that some of the permutations for different magics are identical permutations.
Maybe magics can be chosen so that many of the permutations coincide. That might not be useful in many cases,
but could be useful to me.

For some of my magics I tried a bit-relocation number that I thought might work, and I found the magic number by trial-and-error software.

For the final few shifts and magics, I did a little hand calculation of the relocation and magic pairs.

by **crystalclear** » 25 Mar 2012, 22:58

Finding bit relocation and magic multiplier to collate the bits for this 64 bit number...

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000

Mark out the 14 bits where the collated bits will be.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000 ##############

Shift the bit a to the top. That puts bits b to h into the top 14 bits, so they are collated, though maybe not where we would ideally like them.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000

Shift bit i into one of the free bits, and relocated bit j next to it in another of the bit positions that are still free, of the original 14 top bits.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000 j

Shift bit k into gap and relocate bit m into another free bit.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000 m

Shift bits n and p into the two final free bits.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000 n

So here is where each of the 14 bits to be collated finally land in the 14 index bits at the top of the computer word.

Code: Select all: ############## aijnbcdekfghpm

Now look at each of the shifts, and add them together to get the magic multiplier.
I've just copy-pasted the overhanging bits from above in front of a one, so ignore the letters.

Code: Select all: 10000 10000a000bcde0fgh000 10000a000bcde0fgh0000i0000000 10000a000bcde0fgh0000i0000000j0000000k0000000m000 0000000000000001000000000000000000010000000010000000000000010000

Break it up into 4 bits at a time to write the magic down in hexadecimal.

Code: Select all: 0000 0000 0000 0001 0000 0000 0000 0000 0001 0000 0000 1000 0000 0000 0001 0000 0x0001000010080010 magic

Work out what the constant is that relocates bits j,m and n to their required locations.

Code: Select all: 0000a000bcde0fgh0000i0000000j0000000k0000000m0000000n0000000p000 j m n 0000000000000000000000111111100000000000001110000000100000000000

Turn that to hex.

Code: Select all: 0000 0000 0000 0000 0000 0011 1111 1000 0000 0000 0011 1000 0000 1000 0000 0000 000003f800380800

So that's the calculation for my two numbers (relocation and multiplier) for one of my rook squares.

by **Grant Osborne** » 26 Mar 2012, 16:07

Yes, I follow.
Would you let me know which 14 squares you found magic numbers for? They maybe different to mine.

Grant

by **crystalclear** » 26 Mar 2012, 21:25

Sorry, I don't remember saying I found 14 squares - I haven't counted, I think I found about a dozen.
I didn't particularly save them as there weren't enough for me to be confident I could find the rest, and the program that generated them morphed into the program that generates the new ones, so I haven't got a perfect answer to your question. Also, my bit board layout is unusual, so I guess the magics might work for other people too, but for different squares.

The other observation I have is that the program just searched for working magics, whereas some people seem to search for minimal magics: no unnecessary bits in the number.

Here is a junk file that I found from when I worked on it.
You can see from the printing of zeros and the hello world still left in the program from the IDE that was not a great program that generated them.
But what matters is whether they work or not. I rather hope that bit of the program was bug free.

Code: Select all: hello world ***Failed*** magic for 0 is 0000000000000000 ***Failed*** magic for 1 is 0000000000000000 magic for 2 is 0100020C08102001 magic for 3 is 0100008208100401 magic for 4 is 0100004820860405 magic for 5 is 0100004820860405 magic for 6 is 0300090000804022 magic for 7 is 0100028010200C41 ***Failed*** magic for 8 is 0000000000000000 ***Failed*** magic for 9 is 0000000000000000 ***Failed*** magic for 10 is 0000000000000000 ***Failed*** magic for 11 is 0000000000000000 ***Failed*** magic for 12 is 0000000000000000 ***Failed*** magic for 13 is 0000000000000000 ***Failed*** magic for 14 is 0000000000000000 ***Failed*** magic for 15 is 0000000000000000 ***Failed*** magic for 16 is 0000000000000000 ***Failed*** magic for 17 is 0000000000000000 ***Failed*** magic for 18 is 0000000000000000 ***Failed*** magic for 19 is 0000000000000000 ***Failed*** magic for 20 is 0000000000000000 ***Failed*** magic for 21 is 0000000000000000 ***Failed*** magic for 22 is 0000000000000000 ***Failed*** magic for 23 is 0000000000000000 ***Failed*** magic for 24 is 0000000000000000 ***Failed*** magic for 25 is 0000000000000000 ***Failed*** magic for 26 is 0000000000000000 ***Failed*** magic for 27 is 0000000000000000 ***Failed*** magic for 28 is 0000000000000000 ***Failed*** magic for 29 is 0000000000000000 ***Failed*** magic for 30 is 0000000000000000 ***Failed*** magic for 31 is 0000000000000000 ***Failed*** magic for 32 is 0000000000000000 ***Failed*** magic for 33 is 0000000000000000 ***Failed*** magic for 34 is 0000000000000000 ***Failed*** magic for 35 is 0000000000000000 magic for 36 is 3200010402001008 magic for 37 is 0100040003001082 ***Failed*** magic for 38 is 0000000000000000 ***Failed*** magic for 39 is 0000000000000000 ***Failed*** magic for 40 is 0000000000000000 ***Failed*** magic for 41 is 0000000000000000 ***Failed*** magic for 42 is 0000000000000000 ***Failed*** magic for 43 is 0000000000000000 ***Failed*** magic for 44 is 0000000000000000 ***Failed*** magic for 45 is 0000000000000000 ***Failed*** magic for 46 is 0000000000000000 ***Failed*** magic for 47 is 0000000000000000 ***Failed*** magic for 48 is 0000000000000000 ***Failed*** magic for 49 is 0000000000000000 ***Failed*** magic for 50 is 0000000000000000 ***Failed*** magic for 51 is 0000000000000000 ***Failed*** magic for 52 is 0000000000000000 ***Failed*** magic for 53 is 0000000000000000 ***Failed*** magic for 54 is 0000000000000000 ***Failed*** magic for 55 is 0000000000000000 ***Failed*** magic for 56 is 0000000000000000 ***Failed*** magic for 57 is 0000000000000000 magic for 58 is 0100020C08102001 magic for 59 is 0100008208100401 magic for 60 is 0100004820860405 magic for 61 is 0100004820860405 magic for 62 is 1100098250420021 magic for 63 is 0100028010200C41

Hmm, you seem to be right about there being 14. I thought you were mixed up with me having chatted about 14-bit rook magics.

by **Grant Osborne** » 27 Mar 2012, 12:24

On a quick run through I managed to find 18.
C8, D8, E8, F8, G8, H8, E4, E5, A2, B2, A1, B1, C1, D1, E1, F1, G1, H1.
If you want the magics for these just let me know.

Grant

by **crystalclear** » 29 Mar 2012, 18:01

I said earlier, that I got the impression that a complete set of 14 bit rook magics might be elusive, as often there are 1s that are eight bits apart and also a string of 8 consecutive bits, making magics difficult to find, if not impossible in some cases.

So at the moment I am going to stick with my scheme of magic multiplier plus bit relocation.

The magics I gave above were just lying around in an old file, but your comment prompted me to undo my bit relocation software and do a quick re-search for 14 bit rook magics. I think I found 19. I am sure my bitboard layout is rotated relative to yours, so it might be better to stick to arithmetical numbers rather than chess squares. eg "I have a magic multiplier for occupancy pattern 0x020202fd02020202."

Assuming that we have in general found magics for the same squares, I can guess your bitboard layout.
And if I have that correct ....

If you have 18 and I have 19, that breaks down as follows.
16 squares in common.
2 you have that I don't.
3 I have that you don't.

I think I am missing a couple of your magics,
B1 and E5

In contrast I have these that you might be missing.

Magic multiplier // applicable bit-board occupancy pattern
0x2000040810400240ULL, // Rook 33 (14) 0x020202fd02020202 b4 for you?
0x0100040003001082ULL, // Rook 37 (14) 0x202020df20202020 f4?
0x0100008041000822ULL, // Rook 38 (14) 0x404040bf40404040 g4?

There is no guarantee that my software is correct, but you can try the numbers and see if they work.

I think the numbers are useless without a complete set.
For speed, it might be quicker to add zero than to add a large number, or it might be quicker to multiply with less bits set than with many bits set, so I can see that trimming unnecessary bits in the multipliers or finding the pure magic multipliers like these might be of interest to someone, but without a complete set they are of little use to me. If I find a new 14 bit rook pure magic multiplier I can set my bit relocation constant to zero and use the new multiplier, and then later drop the bit relocation idea if I ever get a complete set of pure magics. I might do that. But I don't have much hope for a complete collection.

Incidentally, do you know which of the multipliers are permuting the index bits and which are muddling them up completely?
And whether there is a fast numerical method of performing a particular bit permutation, other than a look-up table?
I suspect that many of the permutations generated by these magic numbers are identical and can be undone using the same inverse permutation.

by **Grant Osborne** » 30 Mar 2012, 20:10

Sorry, not E5, should be F4. You won't get a complete set. I am convinced that 'at least' one square is impossible.
Here's what I have :-

0x8100022004181021ULL // Rook 2
0x0100008408102205ULL // Rook 3
0x8900020408008241ULL // Rook 4
0x0B0000CA040180A1ULL // Rook 5
0x0700012042008831ULL // Rook 6
0x0500012041700881ULL // Rook 7
0xA0001C1008400240ULL // Rook 33
0x0200010402001008ULL // Rook 36
0x7100040001001082ULL // Rook 37
0x4300008141000822ULL // Rook 38
0x8081046008401180ULL // Rook 48
0x2000060C48904040ULL // Rook 49
0x018060401100180DULL // Rook 56
0x0900401012202C09ULL // Rook 57
0x010022145020084BULL // Rook 58
0x1D00100450820801ULL // Rook 59
0x0900080204008241ULL // Rook 60
0x0700012042040081ULL // Rook 61
0x4300014200208831ULL // Rook 62
0x30D6108060400902ULL // Rook 63

I am now taking a look at bit re-location. Of the few squares I have examined, just re-locating one bit is enough to let me find a magic.

Incidentally, do you know which of the multipliers are permuting the index bits and which are muddling them up completely?
And whether there is a fast numerical method of performing a particular bit permutation, other than a look-up table?
I suspect that many of the permutations generated by these magic numbers are identical and can be undone using the same inverse permutation.

Not sure what this means.

Grant

by **crystalclear** » 01 Apr 2012, 02:37

Collating 4 bits from dispersed patterns like this ...
000000a0000000b000000c00000d0000000
000000000a000000b000c00000d00000000

----> abcd perfect hashing

----> adcb a bit permutation of the desired index

Or the bits could be messed up completely and come out in an order something like this

abcd final result
---- ------------
0000 0000
0001 0100
0010 1110
0011 0001
0100 1111
0101 1100
0110 0110
0111 0011
1000 0111
1001 0001
1010 1101
1011 0010
1100 0101
1101 1000
1110 1001
1111 1010

I find the permutations more aesthetic than a complete muddling of the bits.

I think many of my magics are just permuting the bits, as they just shift each of the 14 desired bits into one of the 14 slots in the top of the "answer".

So mentally I think of the magics as ...
perfect magics 0000a0000b0000c0000d000 -> abcd,
permutation magics 0000a0000b0000c0000d000 -> adcb for example,
or muddling magics.

As far as I can tell, the way people seem to use magic multipliers is to assume or know that there is muddling of indexes, and to get speed by having large tables that contain the attack data in the muddled order, thereby unmuddling the index and addressing the data in one go.
So my questions earlier were about
1) whether there might be a set of magics that are just permuting the index bits.
2) whether there is an easy fast generic way (other than tables) to permute the bits (eg adcb...) back into order (abcd....).

====================

Code: Select all: 0x0100040810204081ULL, // Rook 56 (14) 0xfe01010101010101 +0x0000000000000000 0x0900401012202409ULL, // Rook 57 (14) 0xfd02020202020202 +0x0000000000000000 0x0100020c08102001ULL, // Rook 58 (14) 0xfb04040404040404 +0x0000000000000000

I knocked a bit out of your magic and it still works. Maybe more bits could be removed. I simply wanted to have my own number, though in a sense I still copied it.
I don't think there will be a complete set, but I can slowly start setting the bit relocation numbers to zero when I find new magics.

Code: Select all: magic occupancy bit relocation 0x0220006408012080ULL, // Rook 0 (14) 0x01010101010101fe +0x007f007f007f0000 0x0010010800000440ULL, // Rook 1 (14) 0x02020202020202fd +0x00ff00ff00020000

I see we have the same square numbers for the magics. eg the square you had a magic for and that I was missing a magic, was square number 57 for you in your number and square number 57 for me in my numbering.
I had assumed that wouldn't be the case but I suppose it is logical.
It might be for different squares on the board but the problems numbers are for the same bit patterns for us. That is a confirmation to me that some sort of fast workaround is useful to get me going if I want to stay with 14bit indexes for rooks.

==

With bit relocation, I have a complete set of 14 bit rook magics.

by **Grant Osborne** » 01 Apr 2012, 13:46

Sorry I don't know the answer to your questions. I expect the only way to know what is happening to the bits when they are multiplied is to pick a square and set the occupancy one bit at a time and see where it ends up in the index. To be honest, we are looking at 14 bit magics - that's 16384 elements - that takes an awfully long time compared to 10 bit to find the magic by trial and error software. And I have already established that square 40 is impossible.

You only need to re-locate 1 bit for almost all of the remaining squares and a nice pattern emerges e.g.

Code: Select all: Square bit re-location magic Rook 8 0x007F000000000000 0x84102000A0180680 Rook 9 0x007E000000000000 0x4086200048242040 Rook 10 0x007C000000000000 0x08001000101D0220 Rook 11 0x0078000000000000 0x4541000202880421 Rook 12 0x00F0000000000000 0x0800800304440208 Rook 13 0x0060000000000000 0x404300008141220D Rook 14 0x0040000000000000 0x00070000E0804031 Rook 15 0x3F80000000000000 0x04208002C0A11209

With bit re-location I have all squares except square 54 (just can't get it). Would you help me out on this one?

Grant

by **Grant Osborne** » 03 Apr 2012, 13:23

Still can't find a 14-bit magic for square 54.
Also, I took a look at bishops, all seems OK except for 13-bit magic for square 35.
Do you have magics for these squares?

Grant

by **crystalclear** » 03 Apr 2012, 13:45

Code: Select all: //54 0x40bf404040404040 0100 0000 1011 1111 0100 0000 0100 0000 0100 0000 0100 0000 0100 0000 0100 0000 0100000010111111010000000100000001000000010000000100000001000000 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 ############## 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 k 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 n 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 ############## ajkmnphbicdefg 10 10a000000b 10a000000b0cdefgh0i000000 10a000000b0cdefgh0i0000000j0000000k0000 10a000000b0cdefgh0i0000000j0000000k0000000m0000000n00 0000000000010000000000000100000000000001000000000000001000000010 0000 0000 0001 0000 0000 0000 0100 0000 0000 0001 0000 0000 0000 0010 0000 0010 0x0010004001000202 magic 0a000000b0cdefgh0i0000000j0000000k0000000m0000000n0000000p000000 0000000000000000000000000001111111000000000111111100000000000000 0000 0000 0000 0000 0000 0000 0001 1111 1100 0000 0001 1111 1100 0000 0000 0000 0x0000001fc01fc000 relocate

by **Grant Osborne** » 03 Apr 2012, 14:14

Yep, works for me, thanks very much.
Just square 35 for bishops and I'm done.

Grant

by **crystalclear** » 03 Apr 2012, 14:44

It seems I had trouble with that and did a hand calculation which I have pasted above.

Now let me see if that is the actual value my program found.
My program first tries magics that have been useful in the past, and then tries random numbers if none of the known magics work.
So when I hand calculate a number and stick it in the list, it will only end up being used once my magic selector has verified it as fit for purpose.

Code: Select all: uint64_t RookMagic[64] = { ..... 0x018002c200040018ULL, // Rook 52 (14) 0x10ef101010101010 +0x000003f800380000 0x0000200080020004ULL, // Rook 53 (14) 0x20df202020202020 +0x00000fe00fe003e0 0x0010004001000202ULL, // Rook 54 (14) 0x40bf404040404040 +0x0000001fc01fc000 0x0000400080000201ULL, // Rook 55 (14) 0x807f808080808080 +0x00401f801f801f80 0x0100040810204081ULL, // Rook 56 (14) 0xfe01010101010101 +0x0000000000000000 ..... };

Yep. That's it.
Let me know if you think the values work, as there could be errors in the calculations and bugs in my software.

Some of the magics for large square numbers (i.e. close to square 63) are difficult to find because they have a bit near the top of the word and there is little scope to shift that bit anywhere else. (A rook close to square 63 can usually move to square 63, and any left shift of that number loses the bit.) Inability to shift the top bits where we would like them can leave bits overhanging the top 14 bits that we want to use as an index. We can try to collate the other bits of interest by shifting them up into the top 14, but some bits simultaneously land in the 15th and 16th bits from the top end, we can end up producing carries that mess up the 14 bits we want, and it all goes haywire.

I think I had to hand calculate a few magics for squares in the high 50s.
[Edit: I probably meant low 50s. If a rook is in any of the last eight squares, its possible path takes it to the others and the possible occupancy bits are densely packed in the top eight bits. It is if the rook is in one of the next 8 squares that the occupancy bits overhang the top 14 bits of a 64 bit computer word, and if they also contain bit 62 or 63 then there is little scope to shift these bits without losing the top bit in the process. The overhanging bits need to be shifted into gaps to ensure that they form part of the index. At the same time, if something is shifted into an overhanging 15th bit, then it will start generating a carry into the 14th of the top bits and messing it up.]

I like your relocation of single bits. My bit relocation is much more messy.
It was hard work to my magics and now that I have them I am at a loss for knowing how to usefully do something with them in my chess program.

by **crystalclear** » 03 Apr 2012, 14:54

Code: Select all: Bitboard BishopMagic[64] = // motion of piece up to obstacles { ... 0X04001010006A0082ULL, // Partial Bishop 33 (9) 0X6014200800010024ULL, // Partial Bishop 34 (11) 0X3210002020080009ULL, // Partial Bishop 35 (13) 0X6100080200010009ULL, // Partial Bishop 36 (13) 0X408010C040060030ULL, // Partial Bishop 37 (11) ... };

I haven't used this in anger yet and I get mixed up between software generating numbers and software using them etc, so bear with me if there is some rubbish here.
Now I am wondering why I put the word "PARTIAL" in the comments here.
I found bishop magics for all squares with no bit relocation required.

Hopefully the copy-paste above is from the right file!

by **Grant Osborne** » 03 Apr 2012, 16:14

Superb, thank you very much. Now I have a complete set of bishops and rooks. Your numbers work fine. For the rook squares 56 to 63 I found them in about 10 seconds per square, they were no problem at all.
As for a use for these magics, I mentioned above that I use magics to generate only legal moves. To do this I need to find pinned pieces. I have this already working in my program but, as I said, I had to use less bits.
First find the occupancy of any rooks/queens on the same file/rank as the king, then use this new occupancy to establish whether the king is in check and/or any pieces are pinned. Repeat for bishops/queens.

I am translating this from my code which is in asm so apologies for any errors.

Code: Select all: if (tempBitboard = (RooksQueens(them) & rookMask[kingSq])) { index = (int)((tempBitboard * rookMagic[kingSq]) >> rookShift[kingSq]); tempBitboard = *(rookIndecies[kingSq] + index) & AllOccupied; index = (int)((tempBitboard * rookPinMagic[kingSq]) >> 50); CheckOrPinned = *(rookPinIndieces[kingSq] + index); }

Stored in the variable CheckOrPinned is whether or not I am in check (CheckOrPinned & 3) and if so whether it is a contact check or a slider check or double check, plus pinned pieces and their pinners.

Grant

by **crystalclear** » 06 Apr 2012, 16:42

Now I am wondering why I put the word "PARTIAL" in the comments here.

Okay, I had a look at my magics again.
When I started chess programming I just did things my own way and had no idea if I should store a rook bit patterns that looked like a PLUS sign - a union of a rank and file bit-boards, or if the pattern should be like an exclusive OR of the bit-boards, ie have a hole in the "middle". In hindsight, it might be obvious that the exclusive OR of the rank and file is the sensible choice, but the whole experience has probably left me with a paranoia about whether the main "central" square is included in a bit board or not. (It's not middle of the board - its middle of the rook motion cross hairs.)

If we think of a rook attack bit board being calculated with magic numbers, we could do a calculation with the 14 occupancy bits of the cross hairs but excluding the central 15th square, the one actually occupied by the rook. Or, we could do a magic calculation that collated the 15 bits that included the square that the rook sits on. However, that is terribly wasteful, as one more bit in an index doubles the size of an array - fine if the bit contributes to the usefulness of the index and serves a purpose, but wasteful if it doesn't.

Now when a magic multiplier collates bits, we arrange for the bits to be collected from the top of the computer word. They can be collated somewhere in the middle of a computer word, but getting them from the top end of the word is a requirement at times, e.g. when the occupancy bits include bit 63. From the top of the word, we can collect the index with a single shift - a right shift, whereas collecting bits from the middle of a word is more complicated. So the standard practice for collecting an index from a magic multiplication is to use a single right shift. Basically it is faster to do it that way, so everyone does.

Now suppose we try to find a magic number that collates the 15 bits for a rook occupancy pattern that includes the central square of the cross hairs, and suppose we collate the bits in a way that 15th bit from the top of the word contains the bit for the square that the rook sits on.
Then we can shift the bits right and have a 15 bit index for rook occupancy including the rook square. But if we had shifted right one bit more, it would give us a 14 bit index that corresponds to the occupancy pattern excluding the rook's squares.

So now, we can do the whole magic calculation as before, to get a 14 bit index, but instead of starting with a 14 bit occupancy pattern where we had to ensure the bit for the rook's square was cleared first, we can start with a 15 bit occupancy pattern that includes the rook's square, and the rook square bit is lost or thrown out somehow in the calculation.

So that was my thinking behind calling some of the magic numbers I found "partial". I had found the magic numbers, based on the assumption that occupancy bit-board used for the magic calculations had the bit for the rook's square clear.

However, I could have looked for magic numbers for rooks that gave me a 14 bit occupancy index based on the 14 squares a rook could move to, even if the input was a 15 bit occupancy pattern - the extra bit being the bit for the rook's square. In the explanation above, the rook's bit was collated as the 15th bit of the index, and thrown away by the shift operation. Equally, it could have just not contributed index.

So that was the thinking behind me labeling some of my magic numbers as PARTIAL.

Code: Select all: 0X0020080200802009ULL, // Full Bishop 0 ( 7/ 8) 0x8040201008040201 0X0002040810204080ULL, // Full Bishop 1 ( 7/ 8) 0x0080402010080502 0X4040404040404040ULL, // Full Bishop 2 ( 7/ 8) 0x0000804020110a04 0X2020202020202020ULL, // Full Bishop 3 ( 7/ 8) 0x0000008041221408 0X1010101010101010ULL, // Full Bishop 4 ( 7/ 8) 0x0000000182442810 0X0808080808080808ULL, // Full Bishop 5 ( 7/ 8) 0x0000010204885020 0X0404040404040404ULL, // Full Bishop 6 ( 7/ 8) 0x000102040810a040 0X0202020202020202ULL, // Full Bishop 7 ( 7/ 8) 0x0102040810204080 0X0100040810204081ULL, // Full Bishop 8 ( 7/ 8) 0x4020100804020102 ....

So here, I have some magic numbers for bishops.
If we take the first one, it is for a bishop at square zero, a corner of the board.
You can multiply an occupancy pattern for some of the EIGHT squares on the diagonal, i.e some of the eight squares 0x8040201008040201, by 0X0020080200802009ULL, and shift the result right to recover 7 bits. The value of the corner bit is effectively junked.
I regard the FULL magics as sort of superior to the PARTIAL magics.
The full magics will do everything for me that the partial magics do. If I find a full magic, I can rip out the partial magic in my software and put the full magic in its place. And with a complete set of full magics, the bit for the piece's square becomes a "don't care" bit when doing calculations, instead of needing to be ensured to be clear.

Currently, I have full bishop magics for all squares except 27, 34, 35 and 44, where I have partial magics.

I have thought of an example that might make my full and partial magic idea easy to understand. Suppose a bishop pins a piece against a king and we have the occupancy pattern bit-board for that diagonal. To do magic calculations from the point of view of the piece, king or bishop with full magics, the same occupancy bit-board could be used each time. With partial magics, the bit for the king would need to be cleared before using magic calculations on the occupancy bit-board to verify if the king is in check, and the bit for the bishop would need to be cleared before using the bits to see if the bishop delivers check.

by **Grant Osborne** » 09 Apr 2012, 11:33

I'm afraid I don't see any advantage in including any extra bit for the square that the piece sits on.
Instead of adding an extra bit, try removing one. For example I have found seven 6-bit magics for the bishops.

For me, I want to compare the speed difference from using less bits (smaller tables) but more code against larger tables and less code, hence the desire to get a full set of 14 bit rooks.

Grant

by **crystalclear** » 10 Apr 2012, 19:14

I'm afraid I don't see any advantage in including any extra bit for the square that the piece sits on.
Instead of adding an extra bit, try removing one. For example I have found seven 6-bit magics for the bishops.

I think we are talking a little at cross-purposes.

I did wonder if processors do multiplication by a sort of repeated shift and addition and so take longer to multiply by a magic number with more bits in it.
Let's assume that is the case, and that it is advantageous to find magic numbers with as few bits as possible. I have not done that yet, but it sounds sensible.
But what I have been trying recently is magic numbers that not only produce an index into an array depending on some occupancy bits, but that - at the same time - manage to ignore some other bits in an occupancy pattern.

Let's take for example a bishop attack data for square a1.
Some people will find magic numbers that operate on the state of bits {b2, c3, d4, e5, f6, g7} and find where a bishop can go from a1. They may find that the bits all zero and a look-up tells them that you can reach h8 from a1 with nothing of interest in the way. If we are looking for potential pinning pieces for a friendly king on a1, we might use a bit-board of enemy bishops and queens and find from the magic operation and look-up that there MIGHT be something of interest on h8.
If h8 formed part of the index, then the magic operation and look-up could tell us that there IS something of interest on h8. To do that we need a magic number that operates on the occupancy bits {b2, c3, d4, e5, f6, g7, h8}.

I can imagine your example of using attack data to say where the potentially pinning pieces are, e.g. the first enemy bishop or queen along a diagonal from the friendly king. With h8 in the occupancy data the tables can at times tell us there is a potential pinning piece at h8. Without h8 in the occupancy information, the tables can only tell us to examine h8.

That sort of information about the edge of the board is the logic for me having considered magic numbers and tables that include the remote edge bits.

But in either of these cases, the square a1 is on the diagonal a1-h8, and a question I ask myself is how the whole magic operation - multiplication, shift and look-up - will handle the input if I give occupancy information for {a1, b2, c3, d4, ...}. Does the bit for a1 in the occupancy data get gracefully ignored by the magic operations, or would it foul up the result?

And now let's take the case of someone having a look-up table for square a1 indexed by the 6 bits {b2, c3, d4, e5, f6, g7}. Their table is (let's say) to determine how far a bishop on a1 would be able to move up to and including the first obstacle. So their table for the square a1 is likely have 64 elements:
bishop_attack_data_for_a1[64];

Now here, h8 forms no part of their required indexing and I ask myself a similar question.
Does the bit for h8 in the occupancy data get gracefully ignored by the magic operations, or would it foul up the result?

So that is what has been on my mind a little recently.

For a bishop on b3, it can move to {a2, a4, c2, c4, d1, d5, e6, f7, g8}.
Typically, people will produce attack tables based on what is in the 5 bits {c2, c4, d5, e6, f7}.
bishop_attack_data_for_b3[32];

Now here is how indexing works in a table of mine:-
Multiply by 0x0000040104010800ULL and shift right 59.

This constant has the properties that not only does it index based on what it in 5 bits {c2, c4, d5, e6, f7}, but bits {a2, a4, b3, d1, g8} are ignored.
The multiplication doesn't shift any of those bits into the top 5, nor does it create a carry when several of those bits are set that overflows into and thereby corrupts the the index. From a programming perspective, it is a safer magic to use. Also, it might have some advantages over other magics. Instead of dealing with bits for a bishop's motion {a2, a4, c2, c4, d1, d5, e6, f7, g8} and magic table indexing {c2, c4, d5, e6, f7} separately, the same occupancy pattern can maybe be used for two purposes.

I now have a set of magic numbers and attack tables for bishops, with what I call SHORT indexing.
(To understand what I mean by SHORT indexes, I mean 10 bits for a central rook, rather than 14 bits - i.e. remote edge bits are not included in the index created.)
But my bishop magics can be fed a bit pattern for the whole of the two diagonals. The bit value for the central square is ignored. The bits for the board edges are ignored.

Summary - e.g. for b3 ...
{c2, c4, d5, e6, f7} indexed.
{a2, a4, b3, d1, g8} ignored.
{the rest} should be zero.

Looking for bishop magics like this, 3 squares provides a few problems, e.g. square 21, where I can find a magic that ignores the edge bits, or that ignores the bit for square 21 itself, but not both at once. For rooks, the search was futile - I didn't find enough to make the search worthwhile.

When searching for magics I now try to think of these separately ...
The bits in the occupancy pattern
The relevant bits to make the index - a subset of the occupancy pattern
The number of index bits - probably the same as the number of relevant bits, but not necessarily - could be more, could be less.

by **Grant Osborne** » 11 Apr 2012, 13:05

Crystalclear

I understand what you are doing, and the fact that you can feed your bishop magics two bit patterns depending on whether you include the edge of the board or not (this I am interested in). However, as in my last post, I don't see the point of including an extra bit for the square the bishop sits on in the bit pattern, if it's just going to be shifted away from the index anyway - other than for your own curiosity.
My suggestion was to remove a bit but still to look to the edge of the board, for example square A8, I have a 6-bit magic and the index will still tell me if there is anything of interest on H1. I get the same information from 6-bits as I do from 7-bits and I gain by making the table smaller. My program also tells me if there are any holes in the table but so far I've found none (see viewtopic.php?f=4&t=51162 ).

Grant

Winboard Forum

Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Re: Low memory usage attack bitboard generation

Who is online