Discussion of chess software programming and technical issues.
Moderators: hgm , Rebel , chrisw
tomitank
Posts: 276Joined: Sat Mar 04, 2017 12:24 pmLocation: Hungary
Post by tomitank Sat Oct 14, 2017 6:37 pm
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;
}
}
}
}
Sven
Posts: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Sat Oct 14, 2017 11:13 pm
from < 120? not 64?
Henk
Posts: 7216Joined: Mon May 27, 2013 10:31 am
Post by Henk Sat Oct 14, 2017 11:19 pm
Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..
tomitank
Posts: 276Joined: Sat Mar 04, 2017 12:24 pmLocation: Hungary
Post by tomitank Sun Oct 15, 2017 12:11 am
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;
}
}
}
}
}
tomitank
Posts: 276Joined: Sat Mar 04, 2017 12:24 pmLocation: Hungary
Post by tomitank Sun Oct 15, 2017 12:14 am
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...
Henk
Posts: 7216Joined: Mon May 27, 2013 10:31 am
Post by Henk Sun Oct 15, 2017 12:34 am
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..
Sven
Posts: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Sun Oct 15, 2017 5:23 pm
tomitank wrote: from < 120? not 64?
That was a problem.
Here is the good code:
So your original problem is solved?
Sven
Posts: 4052Joined: Thu May 15, 2008 9:57 pmLocation: Berlin, GermanyFull name: Sven Schüle
Post by Sven Sun Oct 15, 2017 5:28 pm
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.
tomitank
Posts: 276Joined: Sat Mar 04, 2017 12:24 pmLocation: Hungary
Post by tomitank Sun Oct 15, 2017 10:17 pm
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.
hgm
Posts: 27787Joined: Fri Mar 10, 2006 10:06 amLocation: AmsterdamFull name: H G Muller
Post by hgm Sun Oct 15, 2017 11:10 pm
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.
