Page 1 of 1
Magic BitBoards Magic numbers
Posted: Sat Oct 14, 2017 6:37 pm
by tomitank
Hi all!
I would like magic bitboard with 32 bits integers.
I always get an overflow loop.
Blockers array and AttacksFromDebug is 100% good.
What do I do wrong?
Thanks: Tamas
Code: Select all
for (var from = 0; from < 120; from++)
{
MagicRAttacks[from] = new Array();
MagicBAttacks[from] = new Array();
for (pce = BISHOP; pce <= ROOK; pce++)
{
if (pce == ROOK) {
MagicRShifts[from] = 32 - PopCount(BlockerBBMask[AttackBBidx(ROOK, from, LOW)]) - PopCount(BlockerBBMask[AttackBBidx(ROOK, from, HIGH)]);
var MagicShift = MagicRShifts[from];
} else {
MagicBShifts[from] = 32 - PopCount(BlockerBBMask[AttackBBidx(BISHOP, from, LOW)]) - PopCount(BlockerBBMask[AttackBBidx(BISHOP, from, HIGH)]);
var MagicShift = MagicBShifts[from];
}
while (true)
{
var index = 0;
var collision = false;
var b = { Low : 0, High : 0 };
var MagicLow = Math.random() * 0xFFFFFFFF | 0;
var MagicHigh = Math.random() * 0xFFFFFFFF | 0;
loop_1: do {
b.High = 0; // Hack
b.Low = (b.Low - BlockerBBMask[AttackBBidx(pce, from, LOW)]) & BlockerBBMask[AttackBBidx(pce, from, LOW)]; // Blockers Low
loop_2: do {
b.High = (b.High - BlockerBBMask[AttackBBidx(pce, from, HIGH)]) & BlockerBBMask[AttackBBidx(pce, from, HIGH)]; // Blockers High
var attacks = AttacksFromDebug(pce, from, b);
index = ((b.Low * MagicLow) ^ (b.High * MagicHigh)) >>> MagicShift;
if (pce == ROOK) {
if (MagicRAttacks[from][index] == null || (MagicRAttacks[from][index].Low == attacks.Low && MagicRAttacks[from][index].High == attacks.High)) {
MagicRMagics[from << 1 | LOW] = MagicLow;
MagicRMagics[from << 1 | HIGH] = MagicHigh
MagicRAttacks[from][index] = { Low : attacks.Low, High : attacks.High };
} else {
MagicRAttacks[from][index] = null;
collision = true; break loop_1;
}
} else {
if (MagicBAttacks[from][index] == null || (MagicBAttacks[from][index].Low == attacks.Low && MagicBAttacks[from][index].High == attacks.High)) {
MagicBMagics[from << 1 | LOW] = MagicLow;
MagicBMagics[from << 1 | HIGH] = MagicHigh;
MagicBAttacks[from][index] = { Low : attacks.Low, High : attacks.High };
} else {
MagicBAttacks[from][index] = null;
collision = true; break loop_1;
}
}
} while (b.High);
} while (b.Low);
if (!collision) {
break;
}
}
}
}
Re: Magic BitBoards Magic numbers
Posted: Sat Oct 14, 2017 11:13 pm
by Sven
from < 120? not 64?
Also label "loop_2" is unused, by intent?
Re: Magic BitBoards Magic numbers
Posted: Sat Oct 14, 2017 11:19 pm
by Henk
Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 12:11 am
by tomitank
from < 120? not 64?
That was a problem.
Here is the good code:
Code: Select all
for (var from = SQUARES.A8; from <= SQUARES.H1; from++)
{
if (from & 0x88) continue;
for (pce = BISHOP; pce <= ROOK; pce++)
{
if (pce == ROOK) {
MagicRShifts[from] = 32 - PopCount(BlockerBBMask[AttackBBidx(ROOK, from, LOW)]) - PopCount(BlockerBBMask[AttackBBidx(ROOK, from, HIGH)]);
var MagicShift = MagicRShifts[from];
} else {
MagicBShifts[from] = 32 - PopCount(BlockerBBMask[AttackBBidx(BISHOP, from, LOW)]) - PopCount(BlockerBBMask[AttackBBidx(BISHOP, from, HIGH)]);
var MagicShift = MagicBShifts[from];
}
while (true)
{
do {
var MagicLow = RAND_32() & RAND_32() & RAND_32();
var MagicHigh = RAND_32() & RAND_32() & RAND_32();
} while ((PopCount(BlockerBBMask[AttackBBidx(pce, from, LOW)] * MagicLow)
+ PopCount(BlockerBBMask[AttackBBidx(pce, from, HIGH)] * MagicHigh)) < 6);
var collision = false;
var b = { Low : 0, High : 0 };
if (pce == ROOK) MagicRAttacks[from] = new Array(4096);
if (pce == BISHOP) MagicBAttacks[from] = new Array(4096);
do {
b.High = 0; // Hack
do {
var attacks = AttacksFromDebug(pce, from, b);
var index = ((b.Low * MagicLow) ^ (b.High * MagicHigh)) >>> MagicShift;
if (pce == ROOK) {
if (MagicRAttacks[from][index] == null) {
MagicRMagics[from << 1 | LOW] = MagicLow;
MagicRMagics[from << 1 | HIGH] = MagicHigh
MagicRAttacks[from][index] = { Low : attacks.Low, High : attacks.High };
} else if (MagicRAttacks[from][index].Low != attacks.Low || MagicRAttacks[from][index].High != attacks.High) {
collision = true;
continue;
}
} else {
if (MagicBAttacks[from][index] == null) {
MagicBMagics[from << 1 | LOW] = MagicLow;
MagicBMagics[from << 1 | HIGH] = MagicHigh;
MagicBAttacks[from][index] = { Low : attacks.Low, High : attacks.High };
} else if (MagicBAttacks[from][index].Low != attacks.Low || MagicBAttacks[from][index].High != attacks.High) {
collision = true;
continue;
}
}
b.High = (b.High - BlockerBBMask[AttackBBidx(pce, from, HIGH)]) & BlockerBBMask[AttackBBidx(pce, from, HIGH)];
} while (b.High && !collision);
b.Low = (b.Low - BlockerBBMask[AttackBBidx(pce, from, LOW)]) & BlockerBBMask[AttackBBidx(pce, from, LOW)];
} while (b.Low && !collision);
if (!collision) {
break;
}
}
}
}
}
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 12:14 am
by tomitank
Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..
This is not a definitive version yet.
I hope I can optimize it...
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 12:34 am
by Henk
tomitank wrote:Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..
This is not a definitive version yet.
I hope I can optimize it...
No what I understood is that magic bitboards is only an index. That has nothing to do with your implementation..
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 5:23 pm
by Sven
tomitank wrote:from < 120? not 64?
That was a problem.
Here is the good code:
So your original problem is solved?
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 5:28 pm
by Sven
tomitank wrote:Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..
This is not a definitive version yet.
I hope I can optimize it...
The code you have shown is used to fill the table. It does not need to be optimized a lot unless you plan to recalculate the table many times.
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 10:17 pm
by tomitank
Sven wrote:
So your original problem is solved?
Yes
Sven wrote:
The code you have shown is used to fill the table. It does not need to be optimized a lot unless you plan to recalculate the table many times.
After receiving the magic numbers, I saved them.
Unfortunately bitboard in JavaScript is very slow...
With one dimension array MagicBAttacks[(from << 12) | magic_index] slightly better, but mailbox is even better.
Interestingly, however, the Senpai 1.0 bitboard is almost the same speed as the magic bitboard with much less memory requirement.
I hope that I can compensate with a better evaluation.
Re: Magic BitBoards Magic numbers
Posted: Sun Oct 15, 2017 11:10 pm
by hgm
If you want to be fast with only 32-bit data types, the recommended method is mailbox plus view-distance table. Incrementally updating the view-distances is quite cheap. And it allows you not only to generate captures very efficiently (no more ray scans, just look at the target immediately), but also makes staged generation by victim reasonably efficient.
The latter would be even more efficient if you also kept an incrementally updated attack map, which flags slider attacks by direction (8 bits), and leaper attacks per piece (11 bits). The leaper attacks then only require update if the corresponding leaper appears/disappears. And since all slider in Chess are unlimited range, any former slider attack on an evacuated square can be automatically displaced to the down-stream obstacle (the view-distance table immediately telling you where that is located). While on a square that gets blocked you just have to displace the slider attacks on the down-stream neighbors from your direction to you. You can then just extract the attackers for a given victim as bits from the attack-map entry for the square it is on.