6

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.

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
BeepBeep
  • 151
  • 3
  • 9
  • 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. – keyser Aug 15 '14 at 07:11
  • I'm planning on using a series of bitboards, I'll edit my post to make that more clear, thanks. – BeepBeep Aug 15 '14 at 07:12
  • long doesn't store 0s only the 1. Why not use array to store pieces? boolean[][] white = new boolean[num][num]; – KriszDev Aug 15 '14 at 07:12
  • Why would you want to do something like that ? a simple counter will do the same job just fine, won't it ? – Nir Alfasi Aug 15 '14 at 07:13
  • 2
    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`. – rid Aug 15 '14 at 07:13

2 Answers2

11

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.

aioobe
  • 413,195
  • 112
  • 811
  • 826
  • That fixed it, thanks very much. In your opinion is this an effective bitboard representation? – BeepBeep Aug 15 '14 at 07:21
  • 1
    A few `long`s 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. – aioobe Aug 15 '14 at 07:30
  • 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 – BeepBeep Aug 15 '14 at 07:36
  • Also regarding a long, how would I deal with the disregarded leading zeros? Many thanks – BeepBeep Aug 15 '14 at 07:47
  • 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: http://en.wikipedia.org/wiki/Ahmdal%27s_Law – Nick Palmer Aug 15 '14 at 08:02
  • 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. – BeepBeep Aug 15 '14 at 08:09
  • 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`. – aioobe Aug 15 '14 at 08:16
  • (also @BeepBeep :) 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 http://chessprogramming.wikispaces.com/Board+Representation – Marco13 Aug 15 '14 at 09:47
0

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.

kviiri
  • 3,282
  • 1
  • 21
  • 30
  • 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)? – BeepBeep Aug 15 '14 at 07:19
  • 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. – laune Aug 15 '14 at 07:22
  • Could you clarify what you mean by state? – BeepBeep Aug 15 '14 at 07:24
  • @BeepBeep, a *series* of longs would work, yes. I thought you were planning to have all pieces in one, which is impossible. – kviiri Aug 15 '14 at 07:27
  • @BeepBeep, I believe laune means rules such as castling and *en passant* that can't be inferred from position of pieces alone. – kviiri Aug 15 '14 at 07:36
  • 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! – BeepBeep Aug 15 '14 at 07:41
  • @BeepBeep, of course they can, but that's exactly what we're saying. You have to remember to store them. – kviiri Aug 15 '14 at 07:41