Author: James Swafford
Date: 16:52:55 10/26/99
Go up one level in this thread
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
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.