Discussion of chess software programming and technical issues.
Moderators: hgm , Rebel , chrisw
tomitank
Posts: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: 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: 4052 Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Post
by Sven » Sat Oct 14, 2017 11:13 pm
from < 120? not 64?
Also label "loop_2" is unused, by intent?
Henk
Posts: 7220 Joined: 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: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: 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: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: 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: 7220 Joined: 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: 4052 Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full 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: 4052 Joined: Thu May 15, 2008 9:57 pm
Location: Berlin, Germany
Full 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: 276 Joined: Sat Mar 04, 2017 12:24 pm
Location: 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: 27828 Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full 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.
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.