How do I model a chessboard when programming a computer to play chess?

Question

What data structures would you use to represent a chessboard for a computer chess program?

Answer 1

The simple approach is to use an 8x8 integer array. Use 0 for empty squares and assign values for the pieces:

1 white pawns
2 white knights
3 white bishops
4 white rooks
5 white queens
6 white king

Black pieces use negative values
-1 black pawn
-2 black knight
etc

8| -4 -2 -3 -5 -6 -3 -2 -4
7| -1 -1 -1 -1 -1 -1 -1 -1
6|  0  0  0  0  0  0  0  0
5|  0  0  0  0  0  0  0  0
4|  0  0  0  0  0  0  0  0
3|  0  0  0  0  0  0  0  0
2|  1  1  1  1  1  1  1  1 
1|  4  2  3  5  6  3  2  4
  -------------------------
   1  2  3  4  5  6  7  8

Piece moves can be calculated by using the array indexes. For example the white pawns move by increasing the row index by 1, or by 2 if it's the pawn's first move. So the white pawn on [2][1] could move to [3][1] or [4][1].

However this simple 8x8 array representation of has chessboard has several problems. Most notably when you're moving 'sliding' pieces like rooks, bishops and queens you need to constantly be checking the indexes to see if the piece has moved off the board.

Most chessprograms today, especially those that run on a 64 bit CPU, use a bitmapped approach to represent a chessboard and generate moves. x88 is an alternate board model for machines without 64 bit CPUs.

Answer 2

An array would probably be fine. If you wanted more convenient means of "traversing" the board, you could easily build methods to abstract away the details of the data structure implementation.

Answer 3

int[8][8]

0=no piece
1=king
2=queen
3=rook
4=knight
5=bishop
6=pawn

use positive ints for white and negative ints for black

Answer 4

Initially, use an 8 * 8 integer array to represent the chess board.

You can start programing using this notation. Give point values for the pieces. For example:

**White**
9 = white queen
5 = white rook
3 = bishop
3 = knight
1 = pawn

**black**
-9 = white queen
-5 = white rook
-3 = bishop
-3 = knight
-1 = pawn

White King: very large positive number
Black King: very large negative number

etc. (Note that the points given above are approximations of trading power of each chess piece)

After you develop the basic backbones of your application and clearly understand the working of the algorithms used, try to improve the performance by using bit boards.

In bit boards, you use eight 8 -bit words to represent the boards. This representation needs a board for each chess piece. In one bit board you will be storing the position of the rook while in another you will be storing the position of the knight... etc

Bit boards can improve the performance of your application very much because manipulating the pieces with bit boards are very easy and fast.

As you pointed out,

Most chessprograms today, especially those that run on a 64 bit CPU, use a bitmapped approach to represent a chessboard and generate moves. x88 is an alternate board model for machines without 64 bit CPUs.

Answer 5

I would use a multidimensional array so that each element in an array is a grid reference to a square on the board.

Thus

board = arrary(A = array (1,2,3,4,5,5,6,7,8),
               B = array (12,3,.... etc...
               etc...          
               )

Then board[A][1] is then the board square A1.

In reality you would use numbers not letters to help keep your maths logic for where pieces are allowed to move to simple.

Answer 6

There are of course a number of different ways to represent a chessboard, and the best way will depend on what is most important to you.

Your two main choices are between speed and code clarity.

If speed is your priority then you must use a 64 bit data type for each set of pieces on the board (e.g. white pawns, black queens, en passant pawns). You can then take advantage of native bitwise operations when generating moves and testing move legality.

If clarity of code is priority then forget bit shuffling and go for nicely abstracted data types like others have already suggested. Just remember that if you go this way you will probably hit a performance ceiling.

To start you off, look at the code for Crafty (C) and SharpChess (C#).

Answer 7

Well, not sure if this helps, but Deep Blue used a single 6-bit number to represent a specific position on the board. This helped it save footprint on-chip in comparison to it's competitor, which used a 64-bit bitboard.

This might not be relevant, since chances are, you might have 64 bit registers on your target hardware, already.

Answer 8

Using a bitboard would be an efficient way to represent the state of a chess board. The basic idea is that you use 64bit bitsets to represent each of the squares on the board, where first bit usually represents A1 (the lower left square), and the 64th bit represents H8 (the diagonally opposite square). Each type of piece (pawn, king, etc.) of each player (black, white) gets its own bit board and all 12 of these boards makes up the game state. For more information check out this Wikipedia article.

Answer 9

I actually wouldn't model the chess board, I'd just model the position of the pieces. You can have bounds for the chess board then.

Piece.x= x position of piece
Piece.y= y position of piece

Answer 10

When creating my chess engine I originally went with the [8][8] approach, however recently I changed my code to represent the chess board using a 64 item array. I found that this implementation was about 1/3 more efficient, at least in my case.

One of the things you want to consider when doing the [8][8] approach is describing positions. For example if you wish to describe a valid move for a chess piece, you will need 2 bytes to do so. While with the [64] item array you can do it with one byte.

To convert from a position on the [64] item board to a [8][8] board you can simply use the following calculations:

Row= (byte)(index / 8)

Col = (byte)(index % 8)

Although I found that you never have to do that during the recursive move searching which is performance sensitive.

For more information on building a chess engine, feel free to visit my blog that describes the process from scratch: www.chessbin.com

Adam Berent

Answer 11

Array of 120 bytes.

This is a chessboard of 8x8 surrounded by sentinel squares (e.g. a 255 to indicate that a piece can't move to this square). The sentinels have a depth of two so that a knight can't jump over.

To move right add 1. To move left add -1. Up 10, down -10, up and right diagonal 11 etc. Square A1 is index 21. H1 is index 29. H8 is index 99.

All designed for simplicity. But it's never going to be as fast as bitboards.