Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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).
like image 237
devoured elysium Avatar asked Oct 15 '10 22:10

devoured elysium


People also ask

What type of board game is checkers?

Checkers (American English), also known as draughts (/drɑːfts, dræfts/; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces.

What are the characteristics of checkers?

Checkers is played by two persons who oppose each other across a board of 64 light and dark squares, the same as a chessboard. The 24 playing pieces are disk-shaped and of contrasting colours (whatever their colours, they are identified as black and white).


2 Answers

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.

like image 67
Charlie Martin Avatar answered Nov 04 '22 08:11

Charlie Martin


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.

like image 30
Oren A Avatar answered Nov 04 '22 10:11

Oren A