Moderator: Andres Valverde
Gerd Isenberg wrote:Hi Lasse,
great news - despite 8MByte is quite huge
Did you use a brute force approach to find the magics? Enumerating all possible 64-bit De Bruijn numbers until you found a hit - unambiguous result for all relevant enumareted occupied sets on the two rays?
Good luck and fun with your approach!
Cheers,
Gerd
Correct my if I'm wrong, but as I can see, a rook does max have 12 different attack patterns for a rank or file, giving 144 max totally for both for each square. So I believe I have mapped those 144 pattern around 8192 entries. I therefore believe this can be optimised pretty much.
bob wrote:can you either stick this on an ftp machine somewhere or zip it up and email it? cutting/pasting introduces a number of errors...
//--------------------------------------------------------------------------
// Find keys to get rook mobility
//--------------------------------------------------------------------------
fprintf(HashCodeFile, "#Hash codes for rook mobility 256 elements\n");
for (sqr=H8; sqr<=A1; sqr++) {
Print(3,"Searching hash code for rook mobility sqr %c%c\n",'H'-(sqr>>3),'8'-(sqr&7));
N=0;
Best=0;
do {
for (i=0;i<256;i++) RookMobility[sqr][i]=0;
MagicNr=Random64();
success=true;
n=0;
for (i=0;i<64*64;i++) {
Pattern=AttacksFile[sqr][i&63] | AttacksRank[sqr][i>>6];
Address=(MagicNr*Pattern)>>(64-8);
if (RookMobility[sqr][Address]) {
if (RookMobility[sqr][Address]!=PopCount(Pattern)){
success=false;
if (n>Best) {
Best=n;
Print(3,"Best=%3d N=%d\n",Best,N);
}
break;
}
} else {
n++;
RookMobility[sqr][Address] = PopCount(Pattern);
}
N++;
if (!(N&((1<<24)-1))) Print(3,".");
}
} while (!success);
Print(3,"n=%d Magic number found: 0x%x%x \t:", n,HIDWORD(MagicNr),LODWORD(MagicNr));
Print(3,"Iterations = %x%x\n",HIDWORD(N),LODWORD(N));
HashKeyRookMobility[sqr]=MagicNr;
xtos64(htxt,HashKeyRookMobility[sqr]);
fprintf(HashCodeFile, "%c%c = %s\n",'H'-(sqr>>3),'8'-(sqr&7),htxt);
fflush(HashCodeFile);
}
One possible improvement might be to get rid of the redundant outer square occupied state while calculating your occupied pattern. Simply mask out the outer squares of each rank/file or diagonal/antidiagonal in your precalculated RookMask or BishopMask arrays. With this reduced cardinality of "Pattern" it might be possible to find magics for more dense lookup arrays, may be 1024 for bishops and/or 2048 for rooks per square.
I suggest no longer to post that huge source code here. Some routines, to get the idea is fine - imho, for instance the attack getters. But a whole program with a complete bitboard infrastructure is somehow problematic - even if it is perft only.
There are possible clone issues. Do you intend to make open source under some public license?
Pcs=WQueens; // WQueens
while (Pcs) {
From=FirstOne(Pcs);
Pattern = (AllWPieces | AllBPieces) & MaskRook[From];
Address = (Pattern*HashKeyRook[From])>>(64-RAT_BITS);
A = RookAttacks[From][Address];
Pattern = (AllWPieces | AllBPieces) & MaskBishop[From];
Address = (Pattern*HashKeyBishop[From])>>(64-BAT_BITS);
A |= BishopAttacks[From][Address];
A ^= A & (AllWPieces | AllBPieces);
// Mobility
Pattern = A & MaskFreeRook[From];
Address = (Pattern*HashKeyRookMobility[From])>>(64-RMT_BITS);
N2+=RookMobility[From][Address];
Pattern = A & MaskFreeBishop[From];
Address = (Pattern*HashKeyBishopMobility[From])>>(64-BMT_BITS);
N2+=BishopMobility[From][Address];
while (A) {
To=FirstOne(A);
*M++=From+(To<<6)+(WQueen<<12);
A &= ClrBit(To);
}
Pcs &= ClrBit(From);
}
For now I use two tables RookMobility[64][2048] and BishopMobility[64][2048] (256k). The good thing is that it has byte size, and it can be compressed to half-byte, if wanted.
Return to Programming and Technical Discussions
Users browsing this forum: Exabot [Bot] and 5 guests