Copenhagen Cocoa

Programing a checkers-engine in C

Thursday, November 5th, 2009 at 11:03 pm

As some of you might know I am currently working on a checkers-engine written in ansi-c, my inital goal was to create an engine that at some point could be run on the iPhone, in a nice user-friendly enviroment.

The engine is far from complete, but I decided to share my findings with the rest of you, and I hope some find it useful. By sharing my desing concepts, I hope to get some great feedback and ideas how to increse engine efficientcy.

Currently my engine can generate a list of all posible jumps, or moves, from any given position. My next challenge is to work on the ai.

This first chapter will cover the concept of bit-boards, and the design pattern I used, to define my game.

A standard american checkers board, consists of 8×8 squares, though since pieces only move diagonaly, half of the squares are inaccessable, this gives us a total of 32 squares. 32 is the exact amount of bits in a standard integer, this means we can represent our whole game with three ints, a int representing all the black pieces, one representing all the white pieces, and at last one representing the crowned pieces, also known as kings.

Storing our game in a memory efficient way demands special code to decompress and present the game in an understandable way. Finding jumps and moves is a lot faster though, and can be done efficiently with bit rotations and very few exceptions, if you choose the right bitboard layout.

Doing some research on the Internet, I found a very nice article explaining different bitboard layouts, I set on the one showed below (on the lefthand side), since it has the fewest exceptions which will be very convenient when we need to find movers and jumpers later.

The greatest advantage of the layout I chose is that any bit rotation <<7 (seven to the left) results in a north-westren move, and likewise any <<1 (one to the left) results in a north-eastren move.
To minimize confusion I defined an array containing single bits, so I can locate a bit based on its real position, as an example bitBoardforRealPosition[2] = 0x80000000 this bitboard can then be and'ed to another bitboard to filter out the specefic location, and check if there is anything there.

Challenge: Find your a way to represent a bitboard and write a function that can print a character based board from a struct of three ints (black, white, and kings). The end result should look something like this.

00|{ }[ ]{ }[ ]{ }[ ]{ }[ ]
04|[w]{ }[ ]{ }[ ]{ }[ ]{ }
08|{ }[ ]{ }[W]{ }[ ]{ }[b]
12|[ ]{ }[ ]{ }[ ]{ }[b]{ }
16|{ }[ ]{ }[b]{ }[ ]{ }[ ]
20|[ ]{ }[ ]{ }[ ]{ }[ ]{ }
24|{ }[ ]{ }[ ]{ }[b]{ }[b]
28|[B]{ }[ ]{ }[ ]{ }[ ]{ }

If you have any questions please leave a comment below.