Magic bitboards, Java

[Sargon]

Hi

I'm thinking about rewriting my chess engine again. Some months ago, I remember reading something about magic bitboards as an alternative to rotated bitboards. I couldn't find any detailed information about it either in this forum nor via Google though. Is there any public info available somewhere? (if yes, where? :)

I'm also interested in hearing about first hand experience with bitboards and Java. Who is using bitboards in a Java engine? (as primary board representation - not just pawns or something like that) What classes/methods did you find most useful (with respect to speed) for bitboard representation and basic operations set/clear/test?

I've not yet decided whether my next rewrite will be in C++ (again) or Java. I really like Javas portability, but I fear I will miss things like templates. (not to speak of typedef and the const modifier) The current version makes heavy use of templates in the following way:

Code: Select all

class Board
{
	[...]

	bitboard_t whitePieces;
	bitboard_t blackPieces;

	[...]

	template <colour_t> struct Trait;
&#125;;


template <> struct Board&#58;&#58;Trait<White>
&#123;
	static inline pieces&#40;const Board& b&#41; &#123; return b.whitePieces; &#125;;
	&#91;...&#93;
&#125;;

&#91;and analog for black&#93;

This helps me in many ways to write code once, as opposed to:

Code: Select all

if(sideToMove == White) { do_this; }
else                    { do_that; }

Are there any features in Java that would help me here? (v1.6 is OK)

Thanks in advance. :)

Sargon

[Alessandro Damiani]

About the Java part:
In Java Generics are like templates in C++. See http://java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf. I don't know C++'s templates, but I wonder why templates/Generics should be used in your case. If I guessed your intention right from looking at the C++ code I would write it this way in Java:

Code: Select all

class Board {

    static interface Trait {
    
        Bitboard pieces();
    
    }

    class TraitWhite implements Trait {
        
        Bitboard pieces() {
            return whitePieces;
        }
    
    }

    class TraitBlack implements Trait {
        
        Bitboard pieces() {
            return blackPieces;
        }
    
    }

    Bitboard whitePieces;
    Bitboard blackPieces;

    Trait traitWhite = new TraitWhite();
    Trait traitBlack = new TraitBlack();

}

With this code just pass Board.Trait to other methods:

Code: Select all

void foo(Board.Trait trait) {
    Bitboard pieces = trait.pieces();
    while (!pieces.isEmpty()) {
        ...
    }
}

[Pradu]

Not complete and will probably not be until I can get around to proving all the optimal magics... but here are all the facts:
http://www.prism.gatech.edu/~gtg365v/Bu ... boards.pdf

If you are not interested in proving optimal magics, you can skip reading the "generating optimal magics" part and you can generate magic keys by trying out random numbers.

Also take a look at threads on the Winboard Forum for various enhancements like Grant Osbrone's 32-bit optimized versions and Gerd's separated-direction version.

[Guetti]

Hallo Daniel,

Es gibt viel Info auf dem Winboard forum ueber magic bitboards. Ich habe schnell ein paar links rausgesucht (sicher nicht vollstaendig):

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

Ich benutze im Moment nicht Pradus magic, sondern Gerd Isenbergs Methode auch "Kindergarten" Methode genannt. Der Vorteil sind die einfache Implementation, cache friendliness und wenig initialisationen.
Die Methode ist fast so effektiv wie Pradu's magic. Hier der 1.5 KB und der 9.5 KB approach:

http://wbforum.vpittlik.org/viewtopic.p ... 400&t=4523

http://wbforum.vpittlik.org/viewtopic.p ... 902&t=4523

http://wbforum.vpittlik.org/viewtopic.p ... 755&t=4523

[Guetti]

Here a explanation of Gerds Kindergarten Magics:

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

[Sargon]

Hi Pradu

Thanks for the link! Exactly what I was looking for. I'm not just interested in the algorithm but would also like to understand how it works. :)

Sargon

[Sargon]

Hi Guetti :)

Thanks for the links. I'll check the Winboard forum too. :) But... "kindergarten"? When it comes to Gerd, it usually involves Assembler code! Didn't know kids these days do that in kindergarten already. :)

Sargon

[Sargon]

Hi Allessandro

I'm aware that Java supports templates in version 5 and later. Unfortunately they're way less flexible than the C++ templates. For example, in Java the template parameter is always a class type. In C++ you can also make us of partial specialization, like I did.

While your version works for normal methods, it doesn't work for static methods, since you don't have polymorphism there. Anyway, thanks for the idea! :)

Sargon

[Guetti]

Hi Guetti

Thanks for the links. I'll check the Winboard forum too. But... "kindergarten"? When it comes to Gerd, it usually involves Assembler code! Didn't know kids these days do that in kindergarten already.

Sargon

"Kindergarten" in the sense of easyness to implement. It takes some time to understand, but Pradu's magic, well
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:

Code: Select all

		extern unsigned char first_rank_attacks[64][8];		// bitsets on first rank for square x and file y
		extern Bitboard a_file_attacks[64][8];				// bitsets on a-file for square x and rank y
		extern Bitboard fillup_attacks[64][8];				// 0x0101010101010101ULL * first_rank_attacks
		extern Bitboard diaga1h8_mask[64];					// bits on diagonal of square x
		extern Bitboard diagh1a8_mask[64];					// bits on antidiagonal of square x

and the attack functions described in the winboard threads:

Code: Select all

			/*
			// Gerd's 1.5 kb approach
			inline Bitboard rankAttacks(Bitboard occ, int sq)
			{
				int f = sq & 7;
				int r = sq & ~7;  // rank * 8
				int o = (int) (occ >> (r + 1)) & 63;
				Bitboard g = first_rank_attacks[o][f];
				return &#40;g << r&#41;;
			&#125;

			inline Bitboard fileAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;
				occ = 0x0101010101010101ULL & &#40;occ >> f&#41;;	// a-file
				occ = &#40;0x0080402010080400ULL * occ&#41; >> 58;
				occ = &#40;0x8040201008040201ULL * first_rank_attacks&#91;occ&#93;&#91;&#40;sq^56&#41;>>3&#93;);
				return (&#40;0x8080808080808080ULL & occ&#41; >> &#40;f^7&#41;);
			&#125;

			inline Bitboard diagonalAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;
				occ = &#40;diaga1h8_mask&#91;sq&#93; & occ&#41;;
				occ = &#40;0x0202020202020202ULL * occ&#41; >> 58;
				occ = &#40;0x0101010101010101ULL * first_rank_attacks&#91;occ&#93;&#91;f&#93;);
				return &#40;diaga1h8_mask&#91;sq&#93; & occ&#41;;
			&#125;

			inline Bitboard antidiagonalAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;
				occ = &#40;diagh1a8_mask&#91;sq&#93; & occ&#41;;
				occ = &#40;0x0202020202020202ULL * occ&#41; >> 58;
				occ = &#40;0x0101010101010101ULL * first_rank_attacks&#91;occ&#93;&#91;f&#93;);
				return &#40;diagh1a8_mask&#91;sq&#93; & occ&#41;;
			&#125;
			*/

			// Gerds 9.5kb approach
			inline Bitboard rankAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;		// file
				int r = sq & ~7;	// rank*8
				int o = &#40;int&#41; &#40;occ >> &#40;r+1&#41;) & 63;
				return &#40;Bitboard&#41; first_rank_attacks&#91;o&#93;&#91;f&#93; << r;
			&#125;

			inline Bitboard fileAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;		// file
				occ = 0x0101010101010101ULL & &#40;occ >> f&#41;;	// a-file
				int o = &#40;0x0080402010080400ULL * occ&#41; >> 58;
				return &#40;a_file_attacks&#91;o&#93;&#91;sq>>3&#93;) << f;
			&#125;

			inline Bitboard diagonalAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;		// file
				occ = &#40;diaga1h8_mask&#91;sq&#93; & occ&#41;;
				int o = &#40;0x0202020202020202ULL * occ&#41; >> 58;
				return &#40;diaga1h8_mask&#91;sq&#93; & fillup_attacks&#91;o&#93;&#91;f&#93;);
			&#125;

			inline Bitboard antidiagonalAttacks&#40;Bitboard occ, int sq&#41;
			&#123;
				int f = sq & 7;		// file
				occ = &#40;diagh1a8_mask&#91;sq&#93; & occ&#41;;
				int o = &#40;0x0202020202020202ULL * occ&#41; >> 58;
				return &#40;diagh1a8_mask&#91;sq&#93; & fillup_attacks&#91;o&#93;&#91;f&#93;);
			&#125;

and you're set.
This method uses one (or 2) 64-bit multiplication(s) per attack getter, which is fine on 64-bit systems but takes a speed hit on 32-bit. (I think Gerd posted a more 32-bit friendly method in the same thread).

[fluxroot]

Hi Allessandro

I'm aware that Java supports templates in version 5 and later. Unfortunately they're way less flexible than the C++ templates. For example, in Java the template parameter is always a class type. In C++ you can also make us of partial specialization, like I did.

While your version works for normal methods, it doesn't work for static methods, since you don't have polymorphism there. Anyway, thanks for the idea!

Sargon

I'm just porting my engine the other way around, from Java to C++. Though both languages are OO, there's a lot of difference in designing your classes. Don't try to map them one-to-one. This was my big mistake...