Chess bitboard implementation in Java

Question

I'm looking to create a basic chess (or failing that, checkers/draughts) engine. After researching the topic I'm fairly confident that I want to use a series of bitboards. I understand the concept at a basic level but I'm having trouble representing them in Java.

I've attempted to represent the white pieces of a chessboard as 1 and everything else as 0 using a long:

long whitePieces = 0000000000000000000000000000000000000000000000001111111111111111L;

But when I print it out I get the following 46 bits:

System.out.println(Long.toBinaryString(whitePieces));
1001001001001001001001001001001001001001001001

What is causing this result? I'm sure there's something I'm fundamentally misunderstanding here; If anyone could point me in the right direction I'd be very grateful.

Peristalsis

With chess there are more than one kind of piece, so a bit isn't enough? And leading zeroes won't work. You need an array or a list. Which number is 05?, Answer: 5. Make a 2d array of booleans instead. Or a coded integer of some kind instead of multiple such arrays. – Karyoplasm

I'm planning on using a series of bitboards, I'll edit my post to make that more clear, thanks. – Peristalsis

long doesn't store 0s only the 1. Why not use array to store pieces? boolean[][] white = new boolean[num][num]; – Endomorph

Why would you want to do something like that ? a simple counter will do the same job just fine, won't it ? – Nannettenanni

If you're looking for the binary representation of the integer number 1111111111111111, it will not be 1111111111111111... 1111111111111111 is the binary representation of the binary number 1111111111111111, which is the integer 65535. – Psoas

Answer 1

Add 0b in front of your long to say that it's a binary number.

long whitePieces = 0b0000000000000000000000000000000000000000000000001111111111111111L;
                   ^^

(0b prefix was introduced in Java 7. If you're on an older version you could do Long.parseLong("000...111", 2))

---

A different approach: How about creating an enum:

enum ChessPiece { Pawn, Knight, ... };

and store the board in a ChessPiece[8][8]. This should provide you with a much cleaner interface to read and modify the state than a bunch of longs would give you.

If you're concerned about performance, just keep the actual representation properly encapsulated in a Board class (make the actual data structure private). If you, at a later point, find that ChessPiece[8][8] turns out to be a bottleneck, you can play around and change it to a long without much effort.

Billiards

That fixed it, thanks very much. In your opinion is this an effective bitboard representation? – Peristalsis

A few longs might be the way to go, depending on the algorithms you implement. Should be fast to clone a board state for instance. But before you choose a long, ask yourself if you have a clear picture of what the performance bottleneck will be in your algorithms, and if it's worth diving into bit-twiddling right away. – Billiards

The issue is that I'm a pretty amatuer programmer; I've programmed games before but chess AI is far harder than anything I've done before. I'm finding chess move generation and AI to be a confusing topic and bitwise operations on longs is the only way I'm understanding the topic at the moment. I definitely need to experiment and gain a better understanding before I can decide on a concrete implementation – Peristalsis

Also regarding a long, how would I deal with the disregarded leading zeros? Many thanks – Peristalsis

Please STRONGLY consider a better abstraction than a long. The enum and a two dimension array is a much better abstraction and will make writing your code much clearer. In general, I advise writing clean code FIRST and then OPTIMIZING for speed or memory. Consider Ahmdla's Law please: en.wikipedia.org/wiki/Ahmdal%27s_Law – Kush

The problem is the abstraction; I'm very concerned that it's going to confuse me. I can understand basic move generation using bitwise operations on longs eg pawn position >> 8 & pawn position >> 16 would give you the possible starting moves for a pawn. If I moved away from this I'm totally unsure of how I would create a representation I still understood. – Peristalsis

To move a piece from a2 ([0][1]) to a3 ([0][2]) you would do board[0][2] = board[0][1]; board[0][1] = null. – Billiards

(also @Peristalsis :) The hint to use an array of reference types like ChessPiece[8][8] is certainly appropriate from the "high-level", object oriented point of view. However, for an efficient chess engine, you sometimes have to do squeeze out each and every bit of performance, and do things that make the average Java programmer shed quite a few tears... More info can be found at chessprogramming.wikispaces.com/Board+Representation – Doykos

Answer 2

You're not storing a binary number, but a decimal one. To create a number using binary notation, you need to prefix it with 0b. See Oracle docs on binary literals.

Also, a single tile or piece of the chessboard can't be represented by a single bit at all, so you might want to rethink your solution in general.

Eurythmics

Thanks! Could you explain why a single tile cannot be represented by a single bit? Why would a series of these longs by insufficient for each aspect of a chessboard (white pawns, white rooks, black pawns etc)? – Peristalsis

One long fpr each kind of chessman is enough for storing the current position. But you'll also have to store state of a chessman, at least for kings, rooks, and pawns. – Reliquary

Could you clarify what you mean by state? – Peristalsis

@BeepBeep, a series of longs would work, yes. I thought you were planning to have all pieces in one, which is impossible. – Eurythmics

@BeepBeep, I believe laune means rules such as castling and en passant that can't be inferred from position of pieces alone. – Eurythmics

Castling and en passant are definitely difficult, but I've read that they can be solved using this implementation. There's a sizable amount of material on the web regarding this; hopefully I'll get there! – Peristalsis

@BeepBeep, of course they can, but that's exactly what we're saying. You have to remember to store them. – Eurythmics