Java & Magic Bitboards

[Laurens Winkelhagen]

Dear All,

First, let me introduce myself. I'm Laurens Winkelhagen (30) from the Netherlands. Author of Jan Willem, a C++ chess program which I stopped developing a couple of years ago.

Currently, my interest in developing a chess engine has been revived, and I've decided to give it a new go. I'm in a semi-preliminary phase, currently working on move generation. Interestingly I've decided not do return to C(++) but to try my best to build an engine that can beat me (not much of a feat, I admit) in Java.

Java?
Yes, Java. Admittedly, I mostly want to do it in java, just to see if I can and as practice for my java skills.
There are of course several drawbacks to using java (just naming 2):

* The absence of unsigned (64bit) types / unclear (for me) complications for bitboard architectures.

Of course, I've decided to try and use magic bitboards. Thus far, I have working tables for bishops using the magics I've found in a post here on the forum, with surprisingly little java-specific code (basically only once '>>>=' instead of '>>=')

Code: Select all

   private static int result(long occ, long magic, int shift){
       occ      *= magic;
       occ     >>>= shift;
      return (int)(occ);
   }

On the flipside, my attempt to use the Kogge-Stone algorithm failed dramatically, for completely obscure reasons. At the bottom of this post there will be a question to the readers of this post about this;-)

* The scarcity of existing (open source) java programs.

Though, honestly, I found quite a few, but as yet, I'm trying to stay away from their source code. I would like my engine to be my own creation. I realize though that sometimes certain ideas that are implemented in an engine should have their origins mentioned. About this, also, I have some questions.

Questions
I suppose you can consider the rest of this post just the introduction for the questions below.
(About Java)
1. What further complications can I expect when writing my program in Java? (as opposed to other OO languages like C++) (I expect EGTB's will give problems..).
2. Does anyone have pointers to articles about bitboard operations in Java? (so far I've found an O'Reilly article, and a bunch of pages describing efficient bitboarding for C/C++).
3. Anyone familiar with problems with the Kogge Stone algorithm in Java / perhaps with solutions? ^^

(About giving credit)
4. Some ideas are complicated in the theory, but do not really allow for independent discovery of implementations (I would name Magic Bitboards as an example). Besides giving credit to the Idea / inventor, how does one proceed with crediting the actual code? I will elaborate a little bit: In my concrete case, I've copied from this forum a list of magics, a list of shifts and a list of arraysizes, and from the chessprogramming wiki I've 'copied' the idea, including some code very similar to the code example above (http://chessprogramming.wikispaces.com/Magic+Bitboards). There is a big list of people from whom I've copied 'code' - in all probability the list of magics alone has 5+ authors .. How does one deal with that properly / Am I even allowed to copy that list?

Cheers! --Laurens.

[Olivier Deville]

Hi Laurens

Don't expect me to respond on the technical matters

I just want to welcome you back. Good luck with your Java project !

I hope you will pay us a visit at the OpenWar chat (port 16044), since I remember you were here quite often when you were active.

Olivier

[Gerd Isenberg]

Hi Laurens,
I think Kogge-Stone requires a 64-bit JVM - in 32-bit it is too expensive. Also a complete different bitboard infrastructure, that is looping over directions rather than pieces and to propagate multiple sliders.

All code and magics found in cpw are public domain. If you go open source or even GPL, I suggest to mention the main inventors of magic bitboards, Lasse Hansen and Pradu Kannan inside your source. For "standard" magics, n relevant occupied bits to n-bit index, it is quite simple to find your own magics. See Tord's code in Looking for Magics.

Guess you are aware of Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond by Glen Pepicelli.

Cheers,
Gerd

[Laurens Winkelhagen]

Thanks for the welcome-back, Oliver!

And thanks, Gerd, for the clarification. The article you mentioned was indeed the exact O'Reilly article I refered to:-)

[Laurens Winkelhagen]

Dear all,

It took a while, but finally I (think I) completed a first working skeleton of my new engine, and I plan to put it on the internet sometime tonight. The engine is called Frank-Walter, which seems a definite step up from Jan Willem;-) playwise it's of course a major step down, but I'm happy I seem to have produced my first java chess engine, however primitive it might be.

version 1.0 features:

Code: Select all

+ bitboards:
  * magic bitboard move generation for diagonals
  * kindergarten bitboard move generation for verticals
    (idea's and example code obviously coming from the cpw, I did manage to generate the magics myself though;-)
+ castling, ep, minor promotions.
+ winboard protocol version 2 support (only) (needs the 'time' command though)
+ some primitive time management
+ iterative deepening
+ alpha beta search with (admittedly sparse) quiescence.
+ pcsq board evaluation.
- almost no move ordering (except for the first ply)!!
+ mate, stalemate and 50moves detection
- no 3fold repetition detection
- no transposition tables, no pondering, no PVS, no nullmove, no killer moves

As you can see there is a lot of room for improvement^^ I think I'll have fun improving the program, and hope it will be able to beat my old C++ program some day.

Cheers, Laurens

[Volker Pittlik]

...The engine is called Frank-Walter...

Believe it or not but there already a lot of logos for it!

SCNR

Volker

[Laurens Winkelhagen]

hehe yes,

He and his apparently desired namechange to the more 'down to earth' or short Frank was the inspiration for the name of my engine:-)

[Laurens Winkelhagen]

Frank-Walter is now available for download from http://chess.winkelhagen.com/
The engine should be stable, though I've only tested it on my own machine. Currently, you need Java (1.5) to run it.

[Steffan Westcott]

Anyone familiar with problems with the Kogge Stone algorithm in Java / perhaps with solutions? ^^

Sadly I haven't had time to work on chess programming in the past couple of years, but I am a professional Java programmer and happen to be the person who first suggested applying Kogge-Stone networks to chess, so perhaps I can help

People often complain about Java's lack of unsigned integer types, but I fail to see how this adversely affects bitboard techniques. In fact, there is only one thing to be aware of when reading or porting bitboard algorithms from C/C++ to Java : Arithmetic right shifts.

In C/C++ there is just one right shift operator, >>. Consider the expression x = a >> b.

In the case where a is a signed integer type (any size) the b leftmost bits of x will be copies of the leftmost bit ('sign bit') of a. This is a case of an 'arithmetic shift right'.

In the case where 'a' is an unsigned integer type, the 'b' leftmost bits of x will be zeroes. This is a case of a 'logical shift right'. It is precisely because of this shifting in of zeroes that it is vital to declare bitboards as unsigned values in a typical C/C++ bitboard chess program.

In Java there are two right shift operators. >> is an arithmetic shift right, >>> is a logical shift right. So usually you require >>> when shifting bitboard values, not >>.

Apart from that, there is little else to say about implementing the Kogge-Stone algorithms in Java. What was the nature of your obscure problem?

Cheers,
Steffan

[Laurens Winkelhagen]

Thanks for your answer Steffan!


Since writing this post I've done some experimenting and practising with java-bitboard operations, and indeed i've noticed the (now also for me;-) obvious: you've got to be carefull with arithmic (v/s logical) operations on bitboards! When I first started with the experimenting, I didn't even know of the existance of the '>>>' operator:-(

about the floodfill: This was one of my experiments, but as things started to work out with some other bitboard techniques (magic & kindergarten), I've stopped putting effort in it: even my failed experiment is no longer in my bitboard testing class.. Maybe I will pick up the idea again later, when writing perhaps mobility or evaluation code, but for now I have bigger problems, unrelated to java^^ it's some search instability I've found after introducing the transposition table:-(

Cheers for taking the time to reply to my question, and I hope you will find time again for this hobby:-)

[NaltaP312]

Hi,

I have started to do a chess engine too with java langage, here my nuts
I have used KoggeStone by his simplicity to implement.
I have used these forums :
http://www.stmintz.com/ccc/index.php?id=252289 and http://chessprogramming.wikispaces.com/ ... +Algorithm

//KoggeStone algorithm
public static long ShiftRight (long b) { return (b<<1) & 0xfefefefefefefefeL; }
public static long ShiftLeft (long b) { return (b>>1) & 0x7f7f7f7f7f7f7f7fL; }
public static long ShiftUp (long b) { return b<<8; }
public static long ShiftDown (long b) { return b>>8; }
public static long ShiftUpRight (long b) { return (b<<9) & 0xfefefefefefefefeL; }
public static long ShiftUpLeft (long b) { return (b<<7) & 0x7f7f7f7f7f7f7f7fL; }
public static long ShiftDownRight(long b) { return (b>>7) & 0xfefefefefefefefeL; }
public static long ShiftDownLeft (long b) { return (b>>9) & 0x7f7f7f7f7f7f7f7fL; }

/** The routine FillUpOccluded() smears the set bits of bitboard g upwards, but only along set bits of p;
* a reset bit in p is enough to halt a smear. In the above, g = moving piece(s); p = empty squares.*/
public static long FillRightOccluded(long g, long p) {
p &= 0xfefefefefefefefeL;
g |= p & (g << 1);
p &= (p << 1);
g |= p & (g << 2);
p &= (p << 2);
return g |= p & (g << 4);
}

public static long FillLeftOccluded(long g, long p) {
p &= 0x7f7f7f7f7f7f7f7fL;
g |= p & (g >> 1);
p &= (p >> 1);
g |= p & (g >> 2);
p &= (p >> 2);
return g |= p & (g >> 4);
}

public static long FillUpOccluded(long g, long p) {
g |= p & (g << 8);
p &= (p << 8);
g |= p & (g << 16);
p &= (p << 16);
return g |= p & (g << 32);
}

public static long FillDownOccluded(long g, long p) {
g |= p & (g >> 8);
p &= (p >> 8);
g |= p & (g >> 16);
p &= (p >> 16);
return g |= p & (g >> 32);
}

public static long FillUpRightOccluded(long g, long p) {
p &= 0xfefefefefefefefeL;
g |= p & (g << 9);
p &= (p << 9);
g |= p & (g << 18);
p &= (p << 18);
return g |= p & (g << 36);
}

public static long FillUpLeftOccluded(long g, long p) {
p &= 0x7f7f7f7f7f7f7f7fL;
g |= p & (g << 7);
p &= (p << 7);
g |= p & (g << 14);
p &= (p << 14);
return g |= p & (g << 28);
}

public static long FillDownRightOccluded(long g, long p) {
p &= 0xfefefefefefefefeL;
g |= p & (g >> 7);
p &= (p >> 7);
g |= p & (g >> 14);
p &= (p >> 14);
return g |= p & (g >> 28);
}

public static long FillDownLeftOccluded(long g, long p) {
p &= 0x7f7f7f7f7f7f7f7fL;
g |= p & (g >> 9);
p &= (p >> 9);
g |= p & (g >> 18);
p &= (p >> 18);
return g |= p & (g >> 36);
}

public static long soutOne(long bitboard) {
return bitboard>>8;
}

public static long nortOne(long bitboard) {
return bitboard<<8;
}

public static long whitePawnCaptureEast(long whitePawns, long empty) {
return ((whitePawns & 9187201950435737471L) << 9) & empty;
}

public static long whitePawnCaptureWest(long whitePawns, long empty) {
return ((whitePawns & -72340172838076674L) << 7) & empty;
}

public static long whiteSinglePushTargets(long whitePawns, long empty) {
return (nortOne(whitePawns)&empty);
}

public static long whitePawnLegalDoublePush(long whitePawns, long empty) {
long rank4 = 0x00000000FF000000L;
long singlePush = whiteSinglePushTargets(whitePawns, empty);
return (nortOne(singlePush) & empty & rank4);
}

/*** Return a bitboard with all positions set to 1 that can be reach from the square for queen and rook.*/
public static long orthogonalMove( int square , long whitePieces, long blackPieces) {
long seed = ONE_BIT[square];
long free = ~(whitePieces | blackPieces);
return ShiftRight( FillRightOccluded( seed, free ) )
| ShiftLeft( FillLeftOccluded( seed, free ) )
| ShiftUp( FillUpOccluded( seed, free ) )
| ShiftDown( FillDownOccluded( seed, free ) );
}

/*** Return a bitboard with all positions set to 1 that can be reach from the square for queen and bishop.*/
public static long diagonalMove( int square , long whitePieces, long blackPieces) {
long seed = ONE_BIT[square];
long free = ~(whitePieces | blackPieces);
return ShiftUpRight( FillUpRightOccluded( seed, free ) )
| ShiftUpLeft( FillUpLeftOccluded( seed, free ) )
| ShiftDownLeft( FillDownLeftOccluded( seed, free ) )
| ShiftDownRight( FillDownRightOccluded( seed, free ) );
}

If this can help you
I will be happy to have a feedback how to implement a generate move with Magic bitboard and java langage
Regards
NaltaP312