Author: Robert Hyatt
Date: 09:04:36 10/27/99
Go up one level in this thread
On October 26, 1999 at 19:52:55, James Swafford wrote:
>On October 25, 1999 at 00:23:56, James Robertson wrote:
>>>>>
>>>>
>>>>But I have very similar bit masks in Gromit (only 16 bit, because Gromit
>>>>does not use bitboards) and I wonder how to write a bitboard-base program
>>>>without such bit masks. Is there anything special about the order of masks
>>>>in Crafty that is unlikely to be invented independently by others?
>>>
>>>there are 64 of the masks that are just 1 bit shifted right slowly but surely.
>>>I can't imagine why you would have such masks (notice that they are each 64
>>>bits long) if you aren't doing bitmaps. I have another set that has one bit
>>>set in each 64 bit value, but the bit isn't in the 'sliding' pattern, as it is
>>>used to update the rotated-left-90-degree board. Another set of 64 for each
>>>of the two 45-degree-rotated boards. Those are pretty unique to my style of
>>>rotating... There are many other masks as well, including the compact-attacks
>>>array of values that _nobody_ would likely have without using the crafty engine
>>>(this was the code done by Mark Bromley).
>>>
>>>
>>>
>>>>
>>>>Do other bit board based programs use such masks? How do they look in
>>>>Inmichess? Insomniac (if it uses bit boards)?
>
>I use a8=0; h1=63, so I guess mine are a bit different.
>The problem I've run into is having to "flip" when probing
>Nalimov's tablebases. :-(
>
>
>// rank and file masks
>bitmap rank_mask[8]=
> {{(b<<0)|(b<<1)|(b<<2)|(b<<3)|(b<<4)|(b<<5)|(b<<6)|(b<<7)},
> {(b<<8)|(b<<9)|(b<<10)|(b<<11)|(b<<12)|(b<<13)|(b<<14)|(b<<15)},
> {(b<<16)|(b<<17)|(b<<18)|(b<<19)|(b<<20)|(b<<21)|(b<<22)|(b<<23)},
> {(b<<24)|(b<<25)|(b<<26)|(b<<27)|(b<<28)|(b<<29)|(b<<30)|(b<<31)},
> {(b<<32)|(b<<33)|(b<<34)|(b<<35)|(b<<36)|(b<<37)|(b<<38)|(b<<39)},
> {(b<<40)|(b<<41)|(b<<42)|(b<<43)|(b<<44)|(b<<45)|(b<<46)|(b<<47)},
> {(b<<48)|(b<<49)|(b<<50)|(b<<51)|(b<<52)|(b<<53)|(b<<54)|(b<<55)},
> {(b<<56)|(b<<57)|(b<<58)|(b<<59)|(b<<60)|(b<<61)|(b<<62)|(b<<63)}};
>
>
>bitmap file_mask[8]=
> {{(b<<0)|(b<<8)|(b<<16)|(b<<24)|(b<<32)|(b<<40)|(b<<48)|(b<<56)},
> {(b<<1)|(b<<9)|(b<<17)|(b<<25)|(b<<33)|(b<<41)|(b<<49)|(b<<57)},
> {(b<<2)|(b<<10)|(b<<18)|(b<<26)|(b<<34)|(b<<42)|(b<<50)|(b<<58)},
> {(b<<3)|(b<<11)|(b<<19)|(b<<27)|(b<<35)|(b<<43)|(b<<51)|(b<<59)},
> {(b<<4)|(b<<12)|(b<<20)|(b<<28)|(b<<36)|(b<<44)|(b<<52)|(b<<60)},
> {(b<<5)|(b<<13)|(b<<21)|(b<<29)|(b<<37)|(b<<45)|(b<<53)|(b<<61)},
> {(b<<6)|(b<<14)|(b<<22)|(b<<30)|(b<<38)|(b<<46)|(b<<54)|(b<<62)},
> {(b<<7)|(b<<15)|(b<<23)|(b<<31)|(b<<39)|(b<<47)|(b<<55)|(b<<63)}};
>
>
>// rotation maps for rotated bitmaps
>int r90l_square[64] =
> { 7,15,23,31,39,47,55,63,
> 6,14,22,30,38,46,54,62,
> 5,13,21,29,37,45,53,61,
> 4,12,20,28,36,44,52,60,
> 3,11,19,27,35,43,51,59,
> 2,10,18,26,34,42,50,58,
> 1, 9,17,25,33,41,49,57,
> 0, 8,16,24,32,40,48,56 };
>
>int r45l_square[64] =
> { 28,21,15,10, 6, 3, 1, 0,
> 36,29,22,16,11, 7, 4, 2,
> 43,37,30,23,17,12, 8, 5,
> 49,44,38,31,24,18,13, 9,
> 54,50,45,39,32,25,19,14,
> 58,55,51,46,40,33,26,20,
> 61,59,56,52,47,41,34,27,
> 63,62,60,57,53,48,42,35 };
>
>int r45r_square[64] =
> { 0, 1, 3, 6,10,15,21,28,
> 2, 4, 7,11,16,22,29,36,
> 5, 8,12,17,23,30,37,43,
> 9,13,18,24,31,38,44,49,
> 14,19,25,32,39,45,50,54,
> 20,26,33,40,46,51,55,58,
> 27,34,41,47,52,56,59,61,
> 35,42,48,53,57,60,62,63 };
>
>
>// mapping scheme for Nalimov's tablebases
>int tb_map[64] =
> { 56,57,58,59,60,61,62,63,
> 48,49,50,51,52,53,54,55,
> 40,41,42,43,44,45,46,47,
> 32,33,34,35,36,37,38,39,
> 24,25,26,27,28,29,30,31,
> 16,17,18,19,20,21,22,23,
> 8, 9,10,11,12,13,14,15,
> 0, 1, 2, 3, 4, 5, 6, 7 };
>
>
>//
>// unfortunately, no one can be told what the matrix is.
>// you have to see it for yourself.
>//
>
>int matrix[120] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1, 0, 1, 2, 3, 4, 5, 6, 7, -1,
> -1, 8, 9, 10, 11, 12, 13, 14, 15, -1,
> -1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
> -1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
> -1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
> -1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
> -1, 48, 49, 50, 51, 52, 53, 54, 55, -1,
> -1, 56, 57, 58, 59, 60, 61, 62, 63, -1,
> -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };
>
>int matrix_index[64] = { 21,22,23,24,25,26,27,28,
> 31,32,33,34,35,36,37,38,
> 41,42,43,44,45,46,47,48,
> 51,52,53,54,55,56,57,58,
> 61,62,63,64,65,66,67,68,
> 71,72,73,74,75,76,77,78,
> 81,82,83,84,85,86,87,88,
> 91,92,93,94,95,96,97,98 };
>
>
>
>>>
>>>any bitboard program probably has the 64 masks with the sliding 1, but the
>>>other 3 sets are very unlikely, and the compact-attack stuff is probably
>>>impossible to reproduce exactly without copying, as there are so many
>>>different ways to do the same thing.
>>>
>>
>>I think it is not _that_ unlikely. My rotated bitboard code was written with a
>>lot of English (and a little code) advice from Tim Diamond (thanks Tim!). He
>>basically explained in _great_ detail how rotated bitboards work, and I
>>implemented them with original code. I didn't use the Crafty source at all for
>>the early part of my program (I do peek at it sometimes now, and have gotten a
>>lot of ideas from it. Thanks Bob! :).
>>
>>I have the masks with 1 bit shifted, and they should look identical to Crafty's,
>>Arasan's, GLChess's, and Galahad's. I have two arrays that simply have set bits
>>for any square a knight or king attacks from a certain square. I'll bet all the
>>programs I mentioned have these exact arrays (it seems the easiest way to
>>generate knight and king moves to me). If they use 0 for A1, the arrays should?
>>look identical in memory. As for your rotated masks, they were an integral part
>>of Tim's method (which I presume he learned from you....?), so I have them too.
>>:) I was poking around in Arasan many months back and thought I saw similar
>>masks in Jon's program. Don't know if mine would line up in memory with yours,
>>but they serve the same or a similar purpose.
>>
>>Beyond this, I believe you are right. I would be _shocked_ if any programmer
>>invented the same mobility, evaluation, etc. etc. etc. arrays invented by any
>>other programmer.
>>
>>James
>>
>>
>>>
>>>
>>>
>>>>
>>>>I agree that it is something different if LaPetite uses the same scoring arrays.
>>>>Everyone uses them, but finding lots of identical scores would be surprising.
>>>>
>>>>
>>>>I'd really like to see a statement here, where G. Mueller gives her point
>>>>of view.
>>>>
>>>>
>>>>Frank
>>>
>>>
>>>So would I. Because it is so blatant. But G. Mueller didn't discuss voyager
>>>a year ago when she burst upon the scene with a program stronger than almost
>>>any new amateur, complete with parallel search... I doubt we will hear anything
>>>now...
>
>
>
>Here is how I initialize some of my mask:
>
> // precompute horizontal rook/queen moves
> for (c=0;c<64;c++) {
> for (k=0;k<256;k++) {
> /* compute occupied squares by rank state k */
> occupied[7] = (k & 128);
> occupied[6] = (k & 64);
> occupied[5] = (k & 32);
> occupied[4] = (k & 16);
> occupied[3] = (k & 8);
> occupied[2] = (k & 4);
> occupied[1] = (k & 2);
> occupied[0] = (k & 1);
> /* compute moves from square c for rank state k */
> attack_board = 0;
> /* look to the left */
> for (t=1;t<8;t++) {
> if ((c-t)<0) break;
> if (((c-t)&7)==7) break;
> /*
> we're in bounds.
> add square (c-t) to the bitboard.
> if (c-t) is occupied in the rank
> state (k), kick out of the loop.
> */
> attack_board |= mask[c-t];
> if (occupied[(c-t)&7]) break;
> }
> /* look to the right */
> for (t=1;t<8;t++) {
> if ((c+t)>63) break;
> if (((c+t)&7)==0) break;
> attack_board |= mask[c+t];
> if (occupied[(c+t)&7]) break;
> }
> rank_mvs[c][k] = attack_board;
> rank_mob[c][k] = PopCnt(attack_board);
> }
> }
>
>
>
>Not the prettiest, but it works. I can't see how anybody's
>would be significantly different.
>
>--
>James
Look at the "COMPACT_ATTACKS" stuff in crafty. It is _far_ different.
almost to the point of being impossible to understand. In any case, your 64
bit attack bitmaps aren't 64 bits in crafty... they are much shorter. They take
more instructions to generate moves, but much less memory bandwidth, which is
more important on the PC.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.