Magic bitboards, Java

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

grant
Posts: 67
Joined: Mon Aug 06, 2007 4:42 pm
Location: London, England

Re: Magic bitboards, Java

Post by grant »

Hi

Try this

http://wbforum.vpittlik.org/viewtopic.php?t=5997

Grant
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Magic bitboards, Java

Post by Gerd Isenberg »

Guetti wrote: "Kindergarten" in the sense of easyness to implement. It takes some time to understand, but Pradu's magic, well :shock:
If you already have a normal bitboard move generator (not rotated), you probably only have to add and correctly initialize these four arrays for the "Kindergarten" method:
"Kindergarten" was more intended to the easyness of the carryless multiplication - which is simply copy/topcut of "vertical file-strings" to each distinct "one" per file - which I suppose is even understandable by 3 year old kids with some colored paper stripes ;-)

Code: Select all

h . . . . . . .   1 . . . . . . .   a b c d e f g h
g . . . . . . .   . 1 . . . . . .   . a b c d e f g
f . . . . . . .   . . 1 . . . . .   . . a b c d e f
e . . . . . . .   . . . 1 . . . .   . . . a b c d e
d . . . . . . . * . . . . 1 . . . = . . . . a b c d
c . . . . . . .   . . . . . 1 . .   . . . . . a b c
b . . . . . . .   . . . . . . 1 .   . . . . . . a b
a . . . . . . .   . . . . . . . 1   . . . . . . . a

1 . . . . . . .   a . . . . . . .   a b c d e f g h
1 . . . . . . .   . b . . . . . .   . b c d e f g h
1 . . . . . . .   . . c . . . . .   . . c d e f g h
1 . . . . . . .   . . . d . . . .   . . . d e f g h
1 . . . . . . . * . . . . e . . . = . . . . e f g h
1 . . . . . . .   . . . . . f . .   . . . . . f g h
1 . . . . . . .   . . . . . . g .   . . . . . . g h
1 . . . . . . .   . . . . . . . h   . . . . . . . h
But ease to implement is fine as well. By the way - it was quite hard to optimize kindergarten rook-attacks with optimal parallel scheduling of both directions with vc2005 in 64-bit mode.

Multiplying masked rank/diagonal by A-(B)file (2*)0x0101..01 - or
multiplying masked file by main-diagonal (0x8040201008040201) seems somehow more intuitional, than trying to multiply by some "random" magic numbers found by brute force until all occupied recombinations leave unique indices. But the way to recognize the simple "nature" of the Kindergarten-multiplication was full of meanders and traps for me. De Bruijn- and random-numbers where my and Tony Werten's first trials even for directionwise attack-getters with quite small tables. Lasse Hanssen had the idea to map the occupancy of both rook/bishop directions to one index-range - while Pradu Kannan improved Lasse's idea with Java-like arrays for a much denser lookup-range over all squares - the real magic bitboards.


To Sargon:

In Java - what about a pure fill based approach using Steffan Westcott's Kogge-Stone routines and no lookups at all?
Safes the boundscheckings and you may process multiple sliders in one run - real fun to implement.
Here some C-code where you can replace u64 by Java long and >> by >>>:

Code: Select all

const u64 notA = 0xfefefefefefefefe;
const u64 notH = 0x7f7f7f7f7f7f7f7f;

u64 eastOne &#40;u64 b&#41; &#123;return &#40;b<<1&#41; & notA;&#125;
u64 noEaOne &#40;u64 b&#41; &#123;return &#40;b<<9&#41; & notA;&#125;
u64 soEaOne &#40;u64 b&#41; &#123;return &#40;b>>7&#41; & notA;&#125;
u64 westOne &#40;u64 b&#41; &#123;return &#40;b>>1&#41; & notH;&#125;
u64 noWeOne &#40;u64 b&#41; &#123;return &#40;b<<7&#41; & notH;&#125;
u64 soWeOne &#40;u64 b&#41; &#123;return &#40;b>>9&#41; & notH;&#125;
u64 nortOne &#40;u64 b&#41; &#123;return  b<<8;&#125;
u64 soutOne &#40;u64 b&#41; &#123;return  b>>8;&#125;

// Kogge Stones occluded fills
// by Steffan Westcott
u64 eastOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notA;
   gen |= pro & &#40;gen << 1&#41;;
   pro  = pro & &#40;pro << 1&#41;;
   gen |= pro & &#40;gen << 2&#41;;
   pro  = pro & &#40;pro << 2&#41;;
   gen |= pro & &#40;gen << 4&#41;;
   return gen;
&#125;

u64 noEaOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notA;
   gen |= pro & &#40;gen <<  9&#41;;
   pro  = pro & &#40;pro <<  9&#41;;
   gen |= pro & &#40;gen << 18&#41;;
   pro  = pro & &#40;pro << 18&#41;;
   gen |= pro & &#40;gen << 36&#41;;
   return gen;
&#125;

u64 soEaOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notA;
   gen |= pro & &#40;gen >>  7&#41;;
   pro  = pro & &#40;pro >>  7&#41;;
   gen |= pro & &#40;gen >> 14&#41;;
   pro  = pro & &#40;pro >> 14&#41;;
   gen |= pro & &#40;gen >> 28&#41;;
   return gen;
&#125;

u64 westOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notH;
   gen |= pro & &#40;gen >> 1&#41;;
   pro  = pro & &#40;pro >> 1&#41;;
   gen |= pro & &#40;gen >> 2&#41;;
   pro  = pro & &#40;pro >> 2&#41;;
   gen |= pro & &#40;gen >> 4&#41;;
   return gen;
&#125;

u64 noWeOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notH;
   gen |= pro & &#40;gen <<  7&#41;;
   pro  = pro & &#40;pro <<  7&#41;;
   gen |= pro & &#40;gen << 14&#41;;
   pro  = pro & &#40;pro << 14&#41;;
   gen |= pro & &#40;gen << 28&#41;;
   return gen;
&#125;

u64 soWeOccl&#40;u64 gen, u64 pro&#41; &#123;
   pro  = pro &  notH;
   gen |= pro & &#40;gen >>  9&#41;;
   pro  = pro & &#40;pro >>  9&#41;;
   gen |= pro & &#40;gen >> 18&#41;;
   pro  = pro & &#40;pro >> 18&#41;;
   gen |= pro & &#40;gen >> 36&#41;;
   return gen;
&#125;

u64 nortOccl&#40;u64 gen, u64 pro&#41; &#123;
   gen |= pro & &#40;gen <<  8&#41;;
   pro  = pro & &#40;pro <<  8&#41;;
   gen |= pro & &#40;gen << 16&#41;;
   pro  = pro & &#40;pro << 16&#41;;
   gen |= pro & &#40;gen << 32&#41;;
   return gen;
&#125;

u64 soutOccl&#40;u64 gen, u64 pro&#41; &#123;
   gen |= pro & &#40;gen >>  8&#41;;
   pro  = pro & &#40;pro >>  8&#41;;
   gen |= pro & &#40;gen >> 16&#41;;
   pro  = pro & &#40;pro >> 16&#41;;
   gen |= pro & &#40;gen >> 32&#41;;
   return gen;
&#125;

// sliding attacks
u64 eastSld &#40;u64 rooks, u64 empty&#41; &#123;return eastOne&#40;eastOccl&#40;rooks, empty&#41;);&#125;
u64 soutSld &#40;u64 rooks, u64 empty&#41; &#123;return soutOne&#40;soutOccl&#40;rooks, empty&#41;);&#125;
u64 westSld &#40;u64 rooks, u64 empty&#41; &#123;return westOne&#40;westOccl&#40;rooks, empty&#41;);&#125;
u64 nortSld &#40;u64 rooks, u64 empty&#41; &#123;return nortOne&#40;nortOccl&#40;rooks, empty&#41;);&#125;
u64 noEaSld &#40;u64 rooks, u64 empty&#41; &#123;return noEaOne&#40;noEaOccl&#40;rooks, empty&#41;);&#125;
u64 soEaSld &#40;u64 rooks, u64 empty&#41; &#123;return soEaOne&#40;soEaOccl&#40;rooks, empty&#41;);&#125;
u64 soWeSld &#40;u64 rooks, u64 empty&#41; &#123;return soWeOne&#40;soWeOccl&#40;rooks, empty&#41;);&#125;
u64 noWeSld &#40;u64 rooks, u64 empty&#41; &#123;return noWeOne&#40;noWeOccl&#40;rooks, empty&#41;);&#125;
Cheers,
Gerd
Top
Sargon

Re: Magic bitboards, Java

Post by Sargon »

Hi Gerd

I've not yet decided about the programming language, but your fill-based approach looks interesting.

At the moment I'm trying to understand magic bitboards though - really a cool idea! Wrote a program which should calculate all possible magic numbers but that's most likely never gonna finish. :) Are the total numbers known? For input keys with 8, 16 and 32 bits I came up with 4, 32 and 4096 solutions. Can anyone confirm those numbers?

Sargon

PS. And your "kindergarten" algorithm will probably make me feel very stupid if I don't understand it within minutes. ;)
Top
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Magic bitboards, Java

Post by Pradu »

Sargon wrote:Hi Gerd

I've not yet decided about the programming language, but your fill-based approach looks interesting.

At the moment I'm trying to understand magic bitboards though - really a cool idea! Wrote a program which should calculate all possible magic numbers but that's most likely never gonna finish. :) Are the total numbers known? For input keys with 8, 16 and 32 bits I came up with 4, 32 and 4096 solutions. Can anyone confirm those numbers?
Are you talking about bitscan magics? It think your number of magic numbers are double of what they should be. Here are my values:

Here's 8 (2 solutions)
Here's 16 (16 solutions)
Here's 32 (2048 solutions)

Interesting enough, there is power of 2 number of solutions for every power of two bits.
Sargon

PS. And your "kindergarten" algorithm will probably make me feel very stupid if I don't understand it within minutes. ;)
Top
Sargon

Re: Magic bitboards, Java

Post by Sargon »

Pradu wrote:Are you talking about bitscan magics? It think your number of magic numbers are double of what they should be. Here are my values:

Here's 8 (2 solutions)
Here's 16 (16 solutions)
Here's 32 (2048 solutions)
Yes, I meant bitscan magics. Sorry, should have been clearer.

I'm a bit confused though.. my 4 solutions for 8 bit are:

Code: Select all

0x3a &#40;0011'1010&#41;
0x2e &#40;0010'1110&#41;
0x1d &#40;0001'1101&#41;
0x17 &#40;0001'0111&#41;
Did I miss something?

Sargon
Top
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Magic bitboards, Java

Post by Gerd Isenberg »

Sargon wrote: Yes, I meant bitscan magics. Sorry, should have been clearer.

I'm a bit confused though.. my 4 solutions for 8 bit are:

Code: Select all

0x3a &#40;0011'1010&#41;
0x2e &#40;0010'1110&#41;
0x1d &#40;0001'1101&#41;
0x17 &#40;0001'0111&#41;
Did I miss something?

Sargon
Cyclic bit rotation does not really distinguish De Bruijn rings. I consider the odd ones original De Bruijn rings. They have log2(N) ( eg. 3 of 8) number of leading binary zeros - and therefor the property to map at least the first two keys to itself.

Code: Select all

eg. 0x17 = 
00010111&#40;00&#41;
000      ^^ 0->0
 001        1->1
  010       2->2
   101      3->5
    011     4->3
     111    5->7
      110   6->6
       100  7->4
^^      ^^
||______|| wrapped hidden zeros
We need N + log2(N) - 1 bits for a De Bruijn sequence, containing N unique, overlapping log2(N)-bit sequences. The trick to stay with N bits is a ring - using the log2(N)-1 hidden bits right of bit zero as "wrapped" leading zeros.

The even "pseudo" De Bruijns just fulfill that condition and may be used in bitscans as well, implying a cyclic transformation of a bitscan mapping.

Code: Select all

2*0x17 = 0x2E
00101110&#40;00&#41;
001      ^^ 0->1
 010        1->2
  101       2->5
   011      3->3
    111     4->7
     110    5->6
      100   6->4
       000  7->0
^^      ^^
||______|| wrapped hidden zeros
Top
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Magic bitboards, Java

Post by Pradu »

Sargon wrote:
Pradu wrote:Are you talking about bitscan magics? It think your number of magic numbers are double of what they should be. Here are my values:

Here's 8 (2 solutions)
Here's 16 (16 solutions)
Here's 32 (2048 solutions)
Yes, I meant bitscan magics. Sorry, should have been clearer.

I'm a bit confused though.. my 4 solutions for 8 bit are:

Code: Select all

0x3a &#40;0011'1010&#41;
0x2e &#40;0010'1110&#41;
0x1d &#40;0001'1101&#41;
0x17 &#40;0001'0111&#41;
Did I miss something?

Sargon
Indeed I was mistaken. I have a bug in my code. Lousy me! Arrg, I have the same bug in my optimal magic generator too.... I have to do all the proofs over again... Anyways thanks for the verification :)
Top
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Magic bitboards, Java

Post by Pradu »

Here are the corrections:

8 bits
16 bits
32 bits

There are way too many 64-bit magics to print out; however, there should be 2^27 magics for 64-bits:

Code: Select all

#include <stdio.h>

//START - BUILD CONFIGURATION

//#define SHOW_TRACE /*define this to show trace output for this program*/
//Number of bits to hash to &#40;make this the minimal bits&#41;
#define BITS 6
//The type of the number we are trying to bitscan
typedef unsigned int TYPE;

//END - BUILD CONFIGURATION

TYPE indecies&#91;1<<BITS&#93;;
unsigned int count = 0;

#define FAIL 1
#define SUCCESS 0

//START - FUNCTION PROTOTYPES
int main&#40;);
int try0&#40;TYPE depth&#41;;
int try1&#40;TYPE depth&#41;;
int unique&#40;TYPE index, TYPE depth&#41;;

int main&#40;)
&#123;
	TYPE magic;
	TYPE i;
	//generate indecies
	try0&#40;0&#41;;
	try1&#40;0&#41;;
	printf&#40;"%d magics\n", count&#41;;
	system&#40;"Pause");
	return SUCCESS;
&#125;

int compile&#40;)
&#123;

    count++;
    /*#ifdef SHOW_TRACE
    printf&#40;"\nIndecies\n");
	for&#40;i=&#40;1<<BITS&#41;-1;i;i--)
		printf&#40;"%X ",&#40;unsigned long&#41;indecies&#91;i&#93;);
	printf&#40;"%X",&#40;unsigned long&#41;(*indecies&#41;);
	printf&#40;"\n");
	#endif

	magic=0;
	//compile indecies
	for&#40;i=&#40;1<<BITS&#41;-1;i;i--)
	&#123;
		magic|=indecies&#91;i&#93;>>&#40;BITS-1&#41;;
		magic<<=1;
	&#125;
	magic|=(*indecies&#41;>>&#40;BITS-1&#41;;

	printf&#40;"Magic %u&#58; ",count&#41;;
	for&#40;i=2*sizeof&#40;TYPE&#41;;i;i--)
		printf&#40;"%X",&#40;magic>>&#40;4*&#40;i-1&#41;))&0xF&#41;;
	printf&#40;"\n");*/
&#125;

int try0&#40;TYPE depth&#41;
&#123;
	#ifdef SHOW_TRACE
	printf&#40;"%d&#41; Trying 0\n",depth&#41;;
	#endif
	if&#40;!depth&#41; *indecies=0;
	else indecies&#91;depth&#93;=indecies&#91;depth-1&#93;>>1;
	if&#40;unique&#40;indecies&#91;depth&#93;,depth&#41;) return FAIL;
	if&#40;depth==(&#40;1<<BITS&#41;-1&#41;) &#123;compile&#40;); return FAIL;&#125;
	if&#40;try0&#40;depth+1&#41;) return try1&#40;depth+1&#41;;
	return SUCCESS;
&#125;

int try1&#40;TYPE depth&#41;
&#123;
	#ifdef SHOW_TRACE
	printf&#40;"%d&#41; Trying 1\n", depth&#41;;
	#endif
	if&#40;!depth&#41; *indecies=(&#40;TYPE&#41;1&#41;<<&#40;BITS-1&#41;;
	else indecies&#91;depth&#93;=&#40;indecies&#91;depth-1&#93;>>1&#41; | &#40;1<<&#40;BITS-1&#41;);
	if&#40;unique&#40;indecies&#91;depth&#93;,depth&#41;) return FAIL;
	if&#40;depth==(&#40;1<<BITS&#41;-1&#41;) &#123;compile&#40;); return FAIL;&#125;
	if&#40;try0&#40;depth+1&#41;) return try1&#40;depth+1&#41;;
	return SUCCESS;
&#125;

int unique&#40;TYPE index, TYPE depth&#41;
&#123;
	TYPE i;
	for&#40;i=0;i!=depth;i++)
		if&#40;indecies&#91;i&#93;==index&#41;
		&#123;
			#ifdef SHOW_TRACE
			printf&#40;"Fail\n");
			#endif
			return FAIL;
		&#125;
	return SUCCESS;
&#125;
Top
Pradu
Posts: 287
Joined: Sat Mar 11, 2006 3:19 am
Location: Atlanta, GA

Re: Magic bitboards, Java

Post by Pradu »

Code corrections again...

I wish this forum had a much longer time limit for editing posts so that we wouldn't have to double post like this to correct mistakes.

Code: Select all

#include <stdio.h>

//START - BUILD CONFIGURATION

//#define SHOW_TRACE /*define this to show trace output for this program*/
//Number of bits to hash to &#40;make this the minimal bits&#41;
#define BITS 6
//The type of the number we are trying to bitscan
typedef unsigned long long TYPE;

//END - BUILD CONFIGURATION

TYPE indecies&#91;1<<BITS&#93;;
unsigned int count = 0;

#define FAIL 1
#define SUCCESS 0

//START - FUNCTION PROTOTYPES
int main&#40;);
int try0&#40;TYPE depth&#41;;
int try1&#40;TYPE depth&#41;;
int unique&#40;TYPE index, TYPE depth&#41;;

int main&#40;)
&#123;
	TYPE magic;
	TYPE i;
	//generate indecies
	try0&#40;0&#41;;
	try1&#40;0&#41;;
	printf&#40;"%d magics\n", count&#41;;
	system&#40;"Pause");
	return SUCCESS;
&#125;

int compile&#40;)
&#123;

    count++;
    /*#ifdef SHOW_TRACE
    printf&#40;"\nIndecies\n");
	for&#40;i=&#40;1<<BITS&#41;-1;i;i--)
		printf&#40;"%X ",&#40;unsigned long&#41;indecies&#91;i&#93;);
	printf&#40;"%X",&#40;unsigned long&#41;(*indecies&#41;);
	printf&#40;"\n");
	#endif

	magic=0;
	//compile indecies
	for&#40;i=&#40;1<<BITS&#41;-1;i;i--)
	&#123;
		magic|=indecies&#91;i&#93;>>&#40;BITS-1&#41;;
		magic<<=1;
	&#125;
	magic|=(*indecies&#41;>>&#40;BITS-1&#41;;

	printf&#40;"Magic %u&#58; ",count&#41;;
	for&#40;i=2*sizeof&#40;TYPE&#41;;i;i--)
		printf&#40;"%X",&#40;magic>>&#40;4*&#40;i-1&#41;))&0xF&#41;;
	printf&#40;"\n");*/
&#125;

int try0&#40;TYPE depth&#41;
&#123;
	#ifdef SHOW_TRACE
	printf&#40;"%d&#41; Trying 0\n",depth&#41;;
	#endif
	if&#40;!depth&#41; *indecies=0;
	else indecies&#91;depth&#93;=indecies&#91;depth-1&#93;>>1;
	if&#40;unique&#40;indecies&#91;depth&#93;,depth&#41;) return FAIL;
	if&#40;depth==(&#40;1<<BITS&#41;-1&#41;) &#123;compile&#40;); return FAIL;&#125;
	if&#40;try0&#40;depth+1&#41;) return try1&#40;depth+1&#41;;
	return SUCCESS;
&#125;

int try1&#40;TYPE depth&#41;
&#123;
	#ifdef SHOW_TRACE
	printf&#40;"%d&#41; Trying 1\n", depth&#41;;
	#endif
	if&#40;!depth&#41; *indecies=(&#40;TYPE&#41;1&#41;<<&#40;BITS-1&#41;;
	else indecies&#91;depth&#93;=&#40;indecies&#91;depth-1&#93;>>1&#41; | &#40;1<<&#40;BITS-1&#41;);
	if&#40;unique&#40;indecies&#91;depth&#93;,depth&#41;) return FAIL;
	if&#40;depth==(&#40;1<<BITS&#41;-1&#41;) &#123;compile&#40;); return FAIL;&#125;
	if&#40;try0&#40;depth+1&#41;) return try1&#40;depth+1&#41;;
	return SUCCESS;
&#125;

int unique&#40;TYPE index, TYPE depth&#41;
&#123;
	TYPE i;
	for&#40;i=0;i!=depth;i++)
		if&#40;indecies&#91;i&#93;==index&#41;
		&#123;
			#ifdef SHOW_TRACE
			printf&#40;"Fail\n");
			#endif
			return FAIL;
		&#125;
	return SUCCESS;
&#125;
Top
Aleks Peshkov
Posts: 892
Joined: Sun Nov 19, 2006 9:16 pm
Location: Russia

Re: Magic bitboards, Java

Post by Aleks Peshkov »

There are way too many 64-bit magics to print out; however, there should be 2^27 magics for 64-bits
Please, show here the smallest one.
Top

Return to “Computer Chess Club: Programming and Technical Discussions”