Moderators: hgm, Rebel, chrisw
Isn't that what most engines do, that use magic bitboards?Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
I think some engines use a pre-computed list of magics, but then generate the actual tables from them at startup time.The_Algebraist wrote:Thanks for your detailed explanations, Gerd! And also to you Sven!
This really helps me a lot! I'm looking forward to reimplementing the slider attacks with the magics
I just fed my move generation with the 218-move-position and the engine found them all
Isn't that what most engines do, that use magic bitboards?Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
I use them statically, but I intentionally left my code in the branch, even not connected to the cmd line interface, so I can show how the numbers have been generated. I will strongly recommend you read Kannan's papers first, so you can clear everything out for yourself. Also Reul's thesis would be great for you.The_Algebraist wrote:Thanks for your detailed explanations, Gerd! And also to you Sven!
This really helps me a lot! I'm looking forward to reimplementing the slider attacks with the magics
I just fed my move generation with the 218-move-position and the engine found them all
Isn't that what most engines do, that use magic bitboards?Gerd Isenberg wrote: And yes, you can compute the magics on the fly while startup ...
Code: Select all
const unsigned int b_bits[64] =
{ 6, 5, 5, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 9, 9, 7, 5, 5,
5, 5, 7, 7, 7, 7, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
6, 5, 5, 5, 5, 5, 5, 6
};
const unsigned int r_bits[64] =
{ 12, 11, 11, 11, 11, 11, 11, 12,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
11, 10, 10, 10, 10, 10, 10, 11,
12, 11, 11, 11, 11, 11, 11, 12
};
//magic multipliers generation
#define MAX_TRIALS 10000
void print_magics(uint64 *m)
{
int i,j;
FILE *f;
f = fopen("magics.txt", "a");
j = 1;
for(i = 0; i < 64; i++)
{ fprintf(f, "\t%#.16llx%s, ", m[i],"ULL");
if(++j > 4)
{ j = 1;
fprintf(f, "%s", "\n");
}
}
fprintf(f, "%s", "\n\n");
fclose(f);
}
uint64 rand64_1bits(int bitcount)
{
int i;
uint64 pos, rnum = 0ULL;
for(i = 0; i < bitcount; i++)
{ for(;;)
{ pos = 1ULL << (rand() % 63);
if(!(pos & rnum))
{ rnum |= pos;
break;
}
}
}
return (rnum);
}
uint64 gen_multiplier(int sq, bitboard_t mask, int bits, int *mbits, int *ibits, int rook)
{
int fail,b;
int trials;
int bit_trials;
uint64 magic;
uint64 index;
bitboard_t x, blockers[4096], solution[4096], used[4096];
for(x = 0ULL; x < (1ULL << bits); x++)
{ blockers[x] = get_blockers(x, mask);
solution[x] = (rook) ? (get_rook_atk(sq,blockers[x])) :
(get_bishop_atk(sq, blockers[x]));
}
trials = 0; bit_trials = 1;
for(;;)
{ ibits[sq] = 0;
magic = rand64_1bits(bit_trials);
for(x = 0ULL; x < (1ULL << bits); x++) used[x] = 0;
fail = 0;
for(x = 0ULL; x < (1ULL << bits); x++)
{ index = (blockers[x] * magic) >> (64 - bits);
if(used[index] == 0)
{ used[index] = solution[x];
b = popcnt(blockers[x] * magic);
if(ibits[sq] < b) ibits[sq] = b;
}
else if(used[index] != solution[x])
{ fail = 1;
break;
}
}
if(!fail)
{ mbits[sq] = bit_trials;
return magic;
}
trials++;
if((trials > MAX_TRIALS) && (bit_trials < bits))
{ bit_trials++;
trials = 0;
}
}
}
void generate_magics()
{
int i,j,h,m,s;
uint64 magics[64];
int magic_bits[64];
int index_bits[64];
time_t t1,t2;
srand((uint32)time(0));
time(&t1);
printf("generating magic numbers\n\nprogress:\n");
for(i = 0; i < 64; i++)
{ magics[i] = gen_multiplier(i, b_mask[i], b_bits[i], magic_bits, index_bits, 0);
printf(".");
}
print_magics(magics);
printf("\n\nused bits in bishop magic numbers by %d trials:\n\n",MAX_TRIALS);
for(i = 0,j = 1; i < 64; i++,j++)
{ printf("%d, ",magic_bits[i]);
if(j >= 8)
{ printf("\n");
j = 0;
}
}
printf("\n\nmax. multiplication bits for bishop by %d trials:\n\n",MAX_TRIALS);
for(i = 0,j = 1; i < 64; i++,j++)
{ printf("%d, ",index_bits[i]);
if(j >= 8)
{ printf("\n");
j = 0;
}
}
printf("\n\nprogress:\n");
for(i = 0; i < 64; i++)
{ magics[i] = gen_multiplier(i, r_mask[i], r_bits[i], magic_bits, index_bits, 1);
printf(".");
}
print_magics(magics);
printf("\n\nused bits in rook magic numbers by %d trials:\n\n",MAX_TRIALS);
for(i = 0,j = 1; i < 64; i++,j++)
{ printf("%d, ",magic_bits[i]);
if(j >= 8)
{ printf("\n");
j = 0;
}
}
printf("\n\nmax. multiplication bits for rook by %d trials:\n\n",MAX_TRIALS);
for(i = 0,j = 1; i < 64; i++,j++)
{ printf("%d, ",index_bits[i]);
if(j >= 8)
{ printf("\n");
j = 0;
}
}
printf("\n\n");
time(&t2);
s = (int)(t2-t1);
h = (s / 3600); m = (s / 60) % 60; s %= 60;
printf("time: %dh:%dm:%ds\n\n", h, m, s);
}
well the fact that there was a delete missing indicates you're engaged in one cardinal sin: dynamic memory allocation. You should be able to get a fair bit of speed by reusing preallocated objects or creating objects on the stack (local variables) instead of new and delete.The_Algebraist wrote:I found it! 1 missing delete... That got out of hand really fast though.
But now it runs smoothly, yet not very fast.
I only get 7M nodes per sec. Is this only due to the classical approach approach I used instead of the magic bitboards, or must there be some sloppy technique somewhere?
There aren't too many new and delete in the code, but maybe I can try to eliminate them. I will have a look at that tomorrow! Thanks for your suggestion Kevin!kbhearn wrote:well the fact that there was a delete missing indicates you're engaged in one cardinal sin: dynamic memory allocation. You should be able to get a fair bit of speed by reusing preallocated objects or creating objects on the stack (local variables) instead of new and delete.
It is indeed 7M make and unmake.kbhearn wrote:That said, if 7M nodes per second is 7M makes and unmakes you're doing pretty good. If you're bulk counting at the leaves (rather than make and unmake the final ply just tallying the number of legal moves) it's a bit slow, but the algorithm shouldn't be the problem.