Moderator: Andres Valverde
Lasse Hansen wrote:The RookMobility[64][2048] always return a value in the range [0, 14]=15 elements, that tells how many non-capturing moves it is allowed to do. It does not return an attack set. It is just a replacement for PopCount for all possible rook attack sets that are non-captures.
Lasse
bob wrote:I have always had such mobility lookups in Crafty, but I included the endpoints as well when I pre-computed the mobility values.
I'm not sure why one would exclude them since capturing an opponent move is certainly a legal move and ought to count in terms of mobility..
bob wrote:My "attack" arrays are 64x64 int64, my mobility arrays are 64x64 chars. I included the attacks after some testing, as leaving them out seemed a bit worse when your piece is attacking opponent pieces...
Lasse Hansen wrote:Pattern=RookMask[square]&(AllWPieces | AllBPieces);
Address= (Pattern*key[square])>>(64-13);
Attacks = AttacksRook[square][Address];
Lasse Hansen wrote:bob wrote:My "attack" arrays are 64x64 int64, my mobility arrays are 64x64 chars. I included the attacks after some testing, as leaving them out seemed a bit worse when your piece is attacking opponent pieces...
Testing is gold, talk is cheap
I looked a bit at the code in crafty, your mobility lookups seem very efficient. But you dont only count capturing of opponent pieces, you also count capturing your own, am I right?
It should be easy to copy your approach by using hashing of non-rotated bitboards more efficiently than what I have done, but I can already do exactly what you do. I just need to OR the attack bitmap for non-captures with the attack bitmap for all captures, then do the mobility lookup. But I do have the option of leaving out the attacks of both my own pieces and/or the opponents.
I guess I have to make a simplified Eval to see how costly my mobility calculations are. BTW, I made mobility lookup tables for king and knight too, though I dont know if these are needed.
Lasse
What does RookMask[square] contain? Is it a bitboard of rookmoves from that square?
--------
----x---
----x---
----x---
----x---
-xxx-xx-
----x---
--------
For example both of the following positions will produce the same Pattern but the available rookmoves would be different.
2) Also, how did you calculate key[square] and figure out that the multiplication by key and a bitshift will hash the moves correctly?
3) When you profiled perft, approximately what was the ratio between the time spent making moves and the time spent generating them?
#include <stdio.h>
typedef unsigned long long U64;
#define TABLE_BITS 7 // means 128 elements
int FirstOne[1<<TABLE_BITS]; // this is the hash table I want to make
U64 MagicNumber;
int main()
{
U64 Address, Pattern, N=0, SetBit[64], Random64();
int i,success,n,best=0;
SetBit[0]=1; // constructing the set of elements I want to hash
for (i=1;i<64;i++) SetBit[i]=SetBit[i-1]<<1;
do { // searching for a MagicNumber that fits my needs
for (i=0;i<(1<<TABLE_BITS);i++) FirstOne[i]=-1;
MagicNumber=Random64();
success=1;
n=0;
for (i=0;i<64;i++) { // trying all elements
Pattern = SetBit[i];
Address = (Pattern*MagicNumber)>>(64-TABLE_BITS);
if (FirstOne[Address] != -1) {
success=0;
if (n>best) {
best=n;
printf("best=%d\n",best);fflush(stdout);
}
break;
}
else {
FirstOne[Address] = i;
n++;
}
}
N++;
if (!(N&((1<<24)-1))) {
printf("."); fflush(stdout);
}
} while (!success);
printf("MagicNumber found in %u iterations\n",(unsigned int)N);
for (i=0;i<64;i++) { // testing the result
Pattern = SetBit[i];
Address = (Pattern*MagicNumber)>>(64-TABLE_BITS);
printf("i=%d FirstOne[%d]=%d\n",i,(int)Address,FirstOne[Address]);
}
return 0;
}
// The following is taken from crafty
/*
A 32 bit random number generator. An implementation in C of the algorithm
given by Knuth, the art of computer programming, vol. 2, pp. 26-27. We use
e=32, so we have to evaluate y(n) = y(n - 24) + y(n - 55) mod 2^32, which
is implicitly done by unsigned arithmetic.
*/
unsigned int Random32(void)
{
/*
random numbers from Mathematica 2.0.
SeedRandom = 1;
Table[Random[Integer, {0, 2^32 - 1}]
*/
static const unsigned long x[55] = {
1410651636UL, 3012776752UL, 3497475623UL, 2892145026UL, 1571949714UL,
3253082284UL, 3489895018UL, 387949491UL, 2597396737UL, 1981903553UL,
3160251843UL, 129444464UL, 1851443344UL, 4156445905UL, 224604922UL,
1455067070UL, 3953493484UL, 1460937157UL, 2528362617UL, 317430674UL,
3229354360UL, 117491133UL, 832845075UL, 1961600170UL, 1321557429UL,
747750121UL, 545747446UL, 810476036UL, 503334515UL, 4088144633UL,
2824216555UL, 3738252341UL, 3493754131UL, 3672533954UL, 29494241UL,
1180928407UL, 4213624418UL, 33062851UL, 3221315737UL, 1145213552UL,
2957984897UL, 4078668503UL, 2262661702UL, 65478801UL, 2527208841UL,
1960622036UL, 315685891UL, 1196037864UL, 804614524UL, 1421733266UL,
2017105031UL, 3882325900UL, 810735053UL, 384606609UL, 2393861397UL
};
static int init = 1;
static unsigned long y[55];
static int j, k;
unsigned long ul;
if (init) {
int i;
init = 0;
for (i = 0; i < 55; i++)
y[i] = x[i];
j = 24 - 1;
k = 55 - 1;
}
ul = (y[k] += y[j]);
if (--j < 0)
j = 55 - 1;
if (--k < 0)
k = 55 - 1;
return ((unsigned int) ul);
}
U64 Random64(void)
{
U64 result;
unsigned int r1, r2;
r1 = Random32();
r2 = Random32();
result = r1 | (U64) r2 << 32;
return (result);
}
TBitBoard BishopAttacks[64][1<<13]; // 4MByte
TBitBoard MaskBishop[64];
const U64 HashKeyBishop[64]= {...};
Pattern = (AllWPieces | AllBPieces) & MaskBishop[From];
Address = (Pattern*HashKeyBishop[From])>>(64-13);
A = BishopAttacks[From][Address];
TBitBoard BishopAttacks[64][1<<6][1<<6]; // 2MByte
TBitBoard MaskDiagonal[64];
TBitBoard MaskAntiDiagonal[64];
Pattern1 = (AllWPieces | AllBPieces) & MaskDiagonal[From];
Pattern2 = (AllWPieces | AllBPieces) & MaskAntiDiagonal[From];
Address1 = (Pattern1*0x0202020202020202)>>(64-6);
Address2 = (Pattern2*0x0202020202020202)>>(64-6);
A = BishopAttacks[From][Address1][Address2];
A = BishopAttacks[From][Address1][Address2];
A = Dia1Attacks[From][Address1] | Dia2Attacks[From][Address2];
% cumulative self self total
time seconds seconds calls s/call s/call name
34.71 101.25 101.25 197876243 0.00 0.00 MovgenNoncapts
29.27 186.64 85.39 200180423 0.00 0.00 MovgenCapts
15.29 231.26 44.61 12426301514 0.00 0.00 bitScanForward
8.64 256.46 25.21 628189928 0.00 0.00 InCheck
3.50 266.67 10.20 xtos64
3.43 276.67 10.00 200180422 0.00 0.00 MakeMove
2.18 283.03 6.36 1 6.36 278.35 Perft2
1.89 288.55 5.53 200180422 0.00 0.00 UnmakeMove
Have you managed to find any 4096 keys for the rook?
AFile = 0x0101010101010101 & (AllPieces >> (From & 7) );
occ64Rank = 0x000000000000003f & (AllPieces >> ((From & ~7)+1));
occ64File = (0x0004081020408000 * AFile) >> (64-6);
Address = (occ64File << 6) + occ64Rank; // 4096 range
Lasse Hansen wrote:Grant Osborne wrote:Have you managed to find any 4096 keys for the rook?
Yes, for square H8 I found 0x608001d3c001e085 after 2.7 hours and 1+ billion tries . Then I tried H7 and stopped after 18 hours.
Lasse
bob wrote:Or if you have a way to distribute the work across several machines, I can crank up our 128 node dual 64bit xeon cluster...
--------
----*---
----*---
----*---
----1---
-**1-1*-
----1---
--------
Possible rook move bitboards per square
49 42 70 84 84 70 42 49
42 36 60 72 72 61 36 42
70 60 100 120 120 100 60 70
84 72 120 144 144 120 72 84
84 72 120 144 144 120 72 84
70 60 100 120 120 100 60 70
42 36 60 72 72 61 36 42
49 42 70 84 84 70 42 49
Possible bishop move bitboards per square
7 6 10 12 12 10 6 7
6 6 10 12 12 10 6 6
10 10 40 48 48 40 10 10
12 12 48 108 108 48 12 12
12 12 48 108 108 48 12 12
10 10 40 48 48 40 10 10
6 6 10 12 12 10 6 6
7 6 10 12 12 10 6 7
#define Rmoves(pos,square) *(RmovesPointer[square]+RmovesIncrement(pos,square))
#define Bmoves(pos,square) *(BmovesPointer[square]+BmovesIncrement(pos,square))
Gerd Isenberg wrote:I didn't exactly understand how a collision is exactly defined in your brute-force approach. For the rook on e3 with all neighbored squares occupied, there are six don't care bits (additionally to the redundant outer squares), where you can greatly accept collisions with all 2**6 possible combination of the *squares here. So if you have a collision with the same attack pattern - or the same unique number of all enumerated attack pattern per square, you can ignore those "productive" accidently shared collisions - if you don't allready do that.
Pradu wrote:So I was wondering if it was possible to create a cheap hashing function RmovesIncrement in such a way that you can perfectly hash all keys into arrays rookMoves or bishopMoves:
...
Mabe it isn't possible to find the keys needed in RmovesIncrement in reasonable time using a brute force method considering the trouble you had generating keys for a 1 to 1 minimal perfect hash (the 4906 one)...does anyone know of more efficient ways to find these keys or to find out if such keys even exist?
Return to Programming and Technical Discussions
Users browsing this forum: Google [Bot], Yahoo [Bot] and 1 guest