What is the best data-structure to represent a checkers board when speed is the primary concern?

Question

I am currently implementing something quite similar to checkers. So, I have this table game and there are both white and black pieces. Where there are neither white or black pieces, you dno't have pieces.

I'm currently doing the GetValidMoves() method that'll return all the current moves one can do with the current board.

I am thus wondering what might be the best way to represent the board. The naive approach would be to have a matrix with 0's 1's and 2's (for no piece, white piece and black piece).

Other idea would be to instead of a matrix representation of the board, have 2 lists(or any other data-structure): one for black pieces, other for white.

I am implementing this game to test some AI algorithms, so my main concern is speed. I will basically put 2 AI players playing each other, for each turn each player should have a list of all his valid moves and then he'll choose what move to do, this always happening until the game ends(some player wins or there's a tie).

PS: I am not asking about the AI algorithm, I just want to know what would be the best data-structure to handle the board, so that it makes it easy to

1. Look for all the valid moves for the current player
2. Do a move
3. Verify the game is not over (it is over when one player lost all his pieces or one player reached the other side of the board).

Answer 1

Consider using a bitmap: two 64-bit unsigned ints, one for white and one for black. Then you can represent moves and board positions as a function from (W x B) -> (W x B) where W, B represent the set of possible white and possible black positions respectively.

Then most of the board position stuff can be done with integer arithmetic, which is about as fast as you can get.

Answer 2

I would also use a bitmap for this. The functions to check for 1, 2, and 3 will be a little unintuitive to write, but should be very fast.

You'll, of course, need to be careful of the edge cases and a fast solution will probably involve some integer and modular arithmetic on the indexes.

Answer 3

A common way of doing that is with a long type's binary representation for each player.
(since there are 64 squares on the board).. As Charlie already said..
Here's a very good (but reather general) wiki article.

The usage is simple - for example, if you want to check if all pieces can move say up and right, shift the player's pieces represntation 7 bits to the left, and check if there are opponent pieces there, then shift them 7 bits left again, and check if those squares are clear...
I used it in a Reversi competition once, and can say the implementation wasn't too hard.
HTH.

Answer 4

In terms of lists, I would highly recommend against using a structure that uses linked lists in this situation. You'll likely already know the positions that you want to investigate (x-y coordinates), and so a linked list would require O(n) time to simply grab the value of the checkerboard space. As other answers have mentioned, a bitmap or long approach would be ideal.

In terms of how to organize the data, I would imagine that an implementation where both the black and white are stored in the same structure would be ideal. You'll have some overhead since storing 2 and 3 in binary require the same amount of memory, though if you're writing checkers, you'll likely need to stored "kinged" data anyway. Having the ability to check if a space is open by performing a single lookup should provide a significant performance benefit.

Hope this helps.

Answer 5

First of all, it's worth noting that in checkers, half the squares on the boards can never be used, so you really only need an array of 32 items, not 64. Taking kings into account, you get possibilities from 0 to 4 instead of 0 to 2 (though when I did it, I found it easier to use -3 to +3 instead, so the values for red and black have the same magnitude and opposite signs).

Answer 6

It depends on what your AI algorithms are going to be doing. Most AI algorithms would be doing some kind of search over the possible moves at least several steps ahead. In that case you will be making lots of copies of your board representation and it makes sense to try and keep it small as the time to copy your data structure will dominate the time to get a list of possible moves as well as limiting the depth to which you can search.

However, if you are not searching I would create a class Piece and store the color, location, and whether the piece is a king. I would then have a 2 dimensional 8 by 8 array of references to Pieces and a linked-list of black pieces and a linked-list of red pieces. Each element of the array would point to either a piece from the red or black list or to an "Empty" piece (null would work for this). When you move a piece you simply update the Piece object in the list and move the reference from its current location to the new location, setting the old location to the empty piece. For a slight increase in the cost of an update you get an efficient way to iterate over either sides pieces and a constant time lookup of the state of any particular spot on the board.

You would have to iterate over the full list to remove a dead piece, however this can also be made efficient with a slight change to piece. You can store a bool "dead" in the Piece object. When a piece is killed, set dead to true and remove it from the board by replacing the reference to it with the empty piece. When you iterate through either list of pieces simply remove any piece marked as dead from the list.