Magic BitBoards Magic numbers

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Magic BitBoards Magic numbers

Post by tomitank » Sat Oct 14, 2017 4: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 &#40;var from = 0; from < 120; from++)
		&#123;
			MagicRAttacks&#91;from&#93; = new Array&#40;);
			MagicBAttacks&#91;from&#93; = new Array&#40;);
			for &#40;pce = BISHOP; pce <= ROOK; pce++)
			&#123;
				if &#40;pce == ROOK&#41; &#123;
					MagicRShifts&#91;from&#93; = 32 - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;ROOK, from, LOW&#41;&#93;) - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;ROOK, from, HIGH&#41;&#93;);
					var MagicShift = MagicRShifts&#91;from&#93;;
				&#125; else &#123;
					MagicBShifts&#91;from&#93; = 32 - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;BISHOP, from, LOW&#41;&#93;) - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;BISHOP, from, HIGH&#41;&#93;);
					var MagicShift = MagicBShifts&#91;from&#93;;
				&#125;

				while &#40;true&#41;
				&#123;
					var index = 0;
					var collision = false;
					var b = &#123; Low &#58; 0, High &#58; 0 &#125;;
					var MagicLow = Math.random&#40;) * 0xFFFFFFFF | 0;
					var MagicHigh = Math.random&#40;) * 0xFFFFFFFF | 0;

					loop_1&#58; do &#123;

						b.High = 0; // Hack

						b.Low = &#40;b.Low - BlockerBBMask&#91;AttackBBidx&#40;pce, from, LOW&#41;&#93;) & BlockerBBMask&#91;AttackBBidx&#40;pce, from, LOW&#41;&#93;; // Blockers Low

						loop_2&#58; do &#123;

							b.High = &#40;b.High - BlockerBBMask&#91;AttackBBidx&#40;pce, from, HIGH&#41;&#93;) & BlockerBBMask&#91;AttackBBidx&#40;pce, from, HIGH&#41;&#93;; // Blockers High

							var attacks = AttacksFromDebug&#40;pce, from, b&#41;;

							index = (&#40;b.Low * MagicLow&#41; ^ &#40;b.High * MagicHigh&#41;) >>> MagicShift;

							if &#40;pce == ROOK&#41; &#123;
								if &#40;MagicRAttacks&#91;from&#93;&#91;index&#93; == null || &#40;MagicRAttacks&#91;from&#93;&#91;index&#93;.Low == attacks.Low && MagicRAttacks&#91;from&#93;&#91;index&#93;.High == attacks.High&#41;) &#123;
									MagicRMagics&#91;from << 1 | LOW&#93; = MagicLow;
									MagicRMagics&#91;from << 1 | HIGH&#93; = MagicHigh
									MagicRAttacks&#91;from&#93;&#91;index&#93; = &#123; Low &#58; attacks.Low, High &#58; attacks.High &#125;;
								&#125; else &#123;
									MagicRAttacks&#91;from&#93;&#91;index&#93; = null;
									collision = true; break loop_1;
								&#125;
							&#125; else &#123;
								if &#40;MagicBAttacks&#91;from&#93;&#91;index&#93; == null || &#40;MagicBAttacks&#91;from&#93;&#91;index&#93;.Low == attacks.Low && MagicBAttacks&#91;from&#93;&#91;index&#93;.High == attacks.High&#41;) &#123;
									MagicBMagics&#91;from << 1 | LOW&#93; = MagicLow;
									MagicBMagics&#91;from << 1 | HIGH&#93; = MagicHigh;
									MagicBAttacks&#91;from&#93;&#91;index&#93; = &#123; Low &#58; attacks.Low, High &#58; attacks.High &#125;;
								&#125; else &#123;
									MagicBAttacks&#91;from&#93;&#91;index&#93; = null;
									collision = true; break loop_1;
								&#125;
							&#125;

						&#125; while &#40;b.High&#41;;

					&#125; while &#40;b.Low&#41;;

					if (!collision&#41; &#123;
						break;
					&#125;
				&#125;
			&#125;
		&#125;

Sven
Posts: 3948
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Magic BitBoards Magic numbers

Post by Sven » Sat Oct 14, 2017 9:13 pm

from < 120? not 64?
Also label "loop_2" is unused, by intent?

Henk
Posts: 6764
Joined: Mon May 27, 2013 8:31 am

Re: Magic BitBoards Magic numbers

Post by Henk » Sat Oct 14, 2017 9:19 pm

Nothing magic about magic bitboards. It is nothing more than using an index costing much internal memory..

tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Magic BitBoards Magic numbers

Post by tomitank » Sat Oct 14, 2017 10:11 pm

from < 120? not 64?
That was a problem.

Here is the good code:

Code: Select all

		for &#40;var from = SQUARES.A8; from <= SQUARES.H1; from++)
		&#123;
			if &#40;from & 0x88&#41; continue;

			for &#40;pce = BISHOP; pce <= ROOK; pce++)
			&#123;
				if &#40;pce == ROOK&#41; &#123;
					MagicRShifts&#91;from&#93; = 32 - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;ROOK, from, LOW&#41;&#93;) - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;ROOK, from, HIGH&#41;&#93;);
					var MagicShift = MagicRShifts&#91;from&#93;;
				&#125; else &#123;
					MagicBShifts&#91;from&#93; = 32 - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;BISHOP, from, LOW&#41;&#93;) - PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;BISHOP, from, HIGH&#41;&#93;);
					var MagicShift = MagicBShifts&#91;from&#93;;
				&#125;

				while &#40;true&#41;
				&#123;
					do &#123;
						var MagicLow = RAND_32&#40;) & RAND_32&#40;) & RAND_32&#40;);
						var MagicHigh = RAND_32&#40;) & RAND_32&#40;) & RAND_32&#40;);
					&#125; while (&#40;PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;pce, from, LOW&#41;&#93; * MagicLow&#41;
							+ PopCount&#40;BlockerBBMask&#91;AttackBBidx&#40;pce, from, HIGH&#41;&#93; * MagicHigh&#41;) < 6&#41;;

					var collision = false;
					var b = &#123; Low &#58; 0, High &#58; 0 &#125;;
					if &#40;pce == ROOK&#41; MagicRAttacks&#91;from&#93; = new Array&#40;4096&#41;;
					if &#40;pce == BISHOP&#41; MagicBAttacks&#91;from&#93; = new Array&#40;4096&#41;;

					do &#123;

						b.High = 0; // Hack

						do &#123;
							var attacks = AttacksFromDebug&#40;pce, from, b&#41;;

							var index = (&#40;b.Low * MagicLow&#41; ^ &#40;b.High * MagicHigh&#41;) >>> MagicShift;

							if &#40;pce == ROOK&#41; &#123;
								if &#40;MagicRAttacks&#91;from&#93;&#91;index&#93; == null&#41; &#123;
									MagicRMagics&#91;from << 1 | LOW&#93; = MagicLow;
									MagicRMagics&#91;from << 1 | HIGH&#93; = MagicHigh
									MagicRAttacks&#91;from&#93;&#91;index&#93; = &#123; Low &#58; attacks.Low, High &#58; attacks.High &#125;;
								&#125; else if &#40;MagicRAttacks&#91;from&#93;&#91;index&#93;.Low != attacks.Low || MagicRAttacks&#91;from&#93;&#91;index&#93;.High != attacks.High&#41; &#123;
									collision = true;
									continue;
								&#125;
							&#125; else &#123;
								if &#40;MagicBAttacks&#91;from&#93;&#91;index&#93; == null&#41; &#123;
									MagicBMagics&#91;from << 1 | LOW&#93; = MagicLow;
									MagicBMagics&#91;from << 1 | HIGH&#93; = MagicHigh;
									MagicBAttacks&#91;from&#93;&#91;index&#93; = &#123; Low &#58; attacks.Low, High &#58; attacks.High &#125;;
								&#125; else if &#40;MagicBAttacks&#91;from&#93;&#91;index&#93;.Low != attacks.Low || MagicBAttacks&#91;from&#93;&#91;index&#93;.High != attacks.High&#41; &#123;
									collision = true;
									continue;
								&#125;
							&#125;

							b.High = &#40;b.High - BlockerBBMask&#91;AttackBBidx&#40;pce, from, HIGH&#41;&#93;) & BlockerBBMask&#91;AttackBBidx&#40;pce, from, HIGH&#41;&#93;;

						&#125; while &#40;b.High && !collision&#41;;

						b.Low = &#40;b.Low - BlockerBBMask&#91;AttackBBidx&#40;pce, from, LOW&#41;&#93;) & BlockerBBMask&#91;AttackBBidx&#40;pce, from, LOW&#41;&#93;;

					&#125; while &#40;b.Low && !collision&#41;;

					if (!collision&#41; &#123;
						break;
					&#125;
				&#125;
			&#125;
		&#125;
	&#125;

tomitank
Posts: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Magic BitBoards Magic numbers

Post by tomitank » Sat Oct 14, 2017 10:14 pm

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: 6764
Joined: Mon May 27, 2013 8:31 am

Re: Magic BitBoards Magic numbers

Post by Henk » Sat Oct 14, 2017 10:34 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...
No what I understood is that magic bitboards is only an index. That has nothing to do with your implementation..

Sven
Posts: 3948
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Magic BitBoards Magic numbers

Post by Sven » Sun Oct 15, 2017 3: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: 3948
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Magic BitBoards Magic numbers

Post by Sven » Sun Oct 15, 2017 3: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: 258
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Magic BitBoards Magic numbers

Post by tomitank » Sun Oct 15, 2017 8:17 pm

Sven wrote: So your original problem is solved?
Yes :wink:
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.

User avatar
hgm
Posts: 25825
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Magic BitBoards Magic numbers

Post by hgm » Sun Oct 15, 2017 9: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.

Post Reply