Sign in to follow this  

Chess Boards Using Bits

This topic is 4839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all ; i was asking if i am using some 64-bit ints to represent a chess board ...such that every piece has its bitboard .... HOW can i check the valid moves ..... for every piece ... will i make awful for loops or will i use the features of dealing with bits ....bitwise operations .... sorry this is my first time using bits .... thanks in advance :-)

Share this post


Link to post
Share on other sites
Could you try to describe that a little more in detail? I (and I guess most others) don't really understand what you're trying to ask.

Are you saying you want to represent the whole chessboard in 8 * 8 (=64) bits? Since a bit can either be 1 or 0 the only kind of information you could store is if there is a piece or not. No way of storing if it's a king, pawn, bishop and whatnot. So, no way of telling what kind of moves it can do. (3 bits would be enough, since there are only 6 different pieces, but you'd have to use bitwise operations again, which are completely unnecessary and rather cumbersome here)

I think this would be a rather cumbersome way of storing the information. How about using a 8x8 2D-array of 8 bit-integers? This way you can store if there's a piece or not, and even tell what kind of piece it is.

As for the moves, use some kind of lookup table which tells you all possible moves. Maybe store them as vectors. Like four vectors of infinite(*) length for the rook, 4*2 vectors for the knight.



(*) Infinite lenght being 7 units for horizontal/parallel vectors since a piece can never move further then that in x/y direction. Infinite diagonal vectors are simply 7 units in both x and y direction.

Share this post


Link to post
Share on other sites
I think you can use mask and bitwise operator but you may use a chess board which size is greater than 64 boards.

------------
------------
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
------------
------------

x symbolizes your chess board. Now to know where can go a knight you will have a mask ( o symbolizes the valid move in my next beautifull ascii art)

------------
------------
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
--xxxxxxxx--
-oxoxxxxxx--
o-xxoxxxxx--
--Cxxxxxxx--
o---o-------
-o-o--------

You easily see that there is only two valid move. To check another position of the knight, it's just a shift.

Share this post


Link to post
Share on other sites
We used bitfields for our Arimaa game (remotly simmialr to chess). They were usied only in AI/search part but they actualy performed very well since almost all operations are reduced to logical operations and shifts.

Share this post


Link to post
Share on other sites
What platform are you designing this chess game for? If it was a mobile game or something, I could see the use of such memory saving tactics in an attempt to save space. I've never done any programming in which I really need to worry about conserving memory, but if your're making like a chess game for a cell phone, then this might be an issue.

I don't see any practical way how using only one bit per square would work in chess, because there can be some many different kinds of pieces. You'd have to accout for the king, queen, bishop, knight, rook, and pawn, (6 pieces total) and I'd think you'd also need to keep track of whether the piece is white or black (or whatever 2 colors you'd be using). You'd also need to keep track of empty spaces, so as mentioned above, I think the least amount of space each piece could fit into is 8-bits (6 bits for the type of piece, 1 bit for white or black, 1 bit for empty or not), meaning the board would be 64 bytes, not 64 bits, at a minimun.

Share this post


Link to post
Share on other sites
Google: http://www.google.com/search?q=chess+bitboard&sourceid=firefox&start=0&start=0&ie=utf-8&oe=utf-8

Quote:
Original post by wyrzy
I don't see any practical way how using only one bit per square would work in chess, because there can be some many different kinds of pieces. You'd have to accout for the king, queen, bishop, knight, rook, and pawn, (6 pieces total)


you missed this part of the OP's post: "such that every piece has its bitboard"


Now, assuming you're making this for a cellphone (otherwise I really can't see the logic... and even for a cellphone, I'm hard pressed to see it as your primary set of data...):

You'd probably want to bitwise OR together: all the seperate "friendly" pieces (to form one of many lists of invalid moves), "enemy" pieces (to form which spots might be valid to attack) and then flip the bitwise OR of both to make a list of valid "normal" places to move:

int64 friendly =
friendly_pawns
| friendly_rooks
| friendly_queens //in case someone gets knighted, eh?
| friendly_kings
| friendly_knights
| friendly_bishops;
int64 enemy = //for pieces that can do certain moves only while attacking... aka the pawn
...
int64 empty = ~(friendly | enemy); //for pieces that can do cetain moves only while not attacking... aka the pawn


Then you'd create a set of attempted moves for each piece, and then do bitwise &s to see if the moves were valid. Aka:

if (pawn)
{
if (!( pawn_move_diagonal & enemy )) continue; //invalid move
if (!( pawn_move_forward & enemy )) contine; //invalid move
//if we reach here, the move is legal
}
else
{
if ( piece_move & friendly ) continue; //invalid move
//if we reach here, the move is legal
}
//if the move is legal, we've reached here
//note: this might checkmate self, which is illegal, but i'll let you figure out the extra code needed for that


You could probably OR all the results together instead of treating each one seperately... then you'd get a bitboard for each piece... but that's diving into implementation details for how you want to handle your AI (the only reason you'd want to check the valid moves for every piece, besides checking if a move was going to allow the opponent to capture your king, thus making your move illegal).

edit: also, this belongs in the GAME PROGRAMMING forum.
edit: removed accidental self-quote post, edited original post

[Edited by - MaulingMonkey on September 16, 2004 9:59:01 PM]

Share this post


Link to post
Share on other sites
The 88 scheme and "store position of each piece" data structures were designed for machines with limited memory. The advantages of bitboards are speed and convenience - it is really simple to answer queries like "what are all queens under attack by a bishop at xy". All operations I can think of right now are constant-time; there's no need to scan squares.

Looking at my engine (which is currently collecting dust), I used a bitboard for each non-pawn piece of both sides (2*5), 4 rotated bitboards of all figures, and 2 for each side's figures. Updating them all when a move is made is simple, and they're all convenient to have throughout.

Share this post


Link to post
Share on other sites
Quote:

I think the least amount of space each piece could fit into is 8-bits (6 bits for the type of piece, 1 bit for white or black, 1 bit for empty or not), meaning the board would be 64 bytes, not 64 bits, at a minimun.


3 bits : 6 pieces + 1 empty (23 = 8, need only 7)
+1 bits : black/white
--------------------
=4 bits
*64 [squares]
--------------------
=256 bits (16 byte)

Possible with an 4 * 8 array of 8 bit integers. Each integer is used to store two squares.


Each piece stores it's own position:

3 bits : x
+3 bits : y
+1 bits : black/white
=7 bits {8 bits}
*32 [pieces]
=256 bits (16 byte)


@wyrzy : when's the last time you did some binary? :) 6 bits can store a lot more : 26 = 64.

Share this post


Link to post
Share on other sites
Quote:
Original post by Jan Wassenberg
The 88 scheme and "store position of each piece" data structures were designed for machines with limited memory. The advantages of bitboards are speed and convenience - it is really simple to answer queries like "what are all queens under attack by a bishop at xy". All operations I can think of right now are constant-time; there's no need to scan squares.

Looking at my engine (which is currently collecting dust), I used a bitboard for each non-pawn piece of both sides (2*5), 4 rotated bitboards of all figures, and 2 for each side's figures. Updating them all when a move is made is simple, and they're all convenient to have throughout.

in fact, currently he have small cache memory instead... and speed gap between cpu and ram is quite big, so bit tricks is not less important.

Share this post


Link to post
Share on other sites
I just thought I'd throw this little snip of code in for consideration:


typedef int64 bitboard_t;
//bit layout:
//white side
// 1 2 3 4 5 6 7 8
// 9 10 11 12 13 14 15 16
//17 18 19 20 21 22 23 24
//25 26 27 28 29 30 31 32
//33 34 35 36 37 38 39 40
//41 42 43 44 45 46 47 48
//49 50 51 52 53 54 55 56
//57 58 59 60 61 62 63 64
//black side

//<<8 moves a bitboard down 1, >>8 moves up 1, <<1 moves left one, >>1 moves right one. Note: wraps around, so AND against an edge if necessary.

bitboard_t left_edge = 0x0101010101010101;
bitboard_t right_edge= 0x8080808080808080;
bitboard_t edge = left_edge | right_edige;
bitboard_t non_edge = ~edge;

//... lots of piece bitboard declerations and setups ...

bitboard_t black_pawns;
bitboard_t black_pawns_attack = //all possible places black pawns can attack
(( (black_pawns&(~left_edge)) >> 9) //attack up/left, unless allready on the left edge
| (( (black_pawns&(~right_edge)) >> 7)) //attack up/right, unless allready on the right edge
& white_pieces;

Share this post


Link to post
Share on other sites
Using 64-bit values to represent a chess board (a.k.a. "bitboards") is a good approach (unless you plan on writing a program for a PDA, maybe). On 32-bit PCs, bitboards approximately "break even" in regards to execution speed. On 32-bit hardware, bitboards are slower than strictly array-based approaches for generating legal moves and moving pieces around the board, but they are more expressive for evaluating positions. Think in terms of sets, each 64-bit value is a set of squares with some boolean property. This way you deal with the entire board at once as opposed to scanning one square at a time. It also takes some time to get used to "thinking bitboards". It isn't always obvious how to efficiently accomplish something.

Here you will find some articles on the topic of bitboards and board representation from (basically) the expert on the subject of bitboards, Dr. Robert Hyatt. Read the articles, "Chess board representations", and "Rotated BitMaps". Rotated bitboards are the most common method of generating attacks and legal moves.

The basic themes are that you can do bitwise set operations, and also shift and mask off parts of bitboards (for instance, mask off 8-bits representing a rank), then stick that 8-bit value into a lookup table and output whatever you feel like sticking in the lookup table.

And of course when you move to a 64-bit machine you instantly get a significant speed boost for free.

Share this post


Link to post
Share on other sites
Quote:
I think he was trying to point out that optimizing for memory will also give you faster performance, because it more effectively uses the cache.

hmm, true in general, but I don't think it matters either way here. Both bitboards and "smaller" board schemes reference only a few cache lines, and other memory accesses by the engine (transposition tables, tree) are likely to kick them out.

Share this post


Link to post
Share on other sites

This topic is 4839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this