Wednesday, 14 March 2007

Board Representation

The past two weeks (even before the start of this blog) I have been trying to decide which representation scheme to use. From a bit of research on the net, I found the following techniques:

8x8-element array (or 64-element array)
Straight forward and very intuitive. The main problem with this approach is legality checking. Every time a sliding piece (queen, bishop or rook) moves the program needs to check if a boundary has been crossed. That will be slow. I also had some experience with this in my very first chess engine.

12x12-element array (or 144-element array)
At first glance I wanted to throw out this idea, but after looking at it, I decided that after bit-boards (see below) this can be pretty quick. All I do is to surround the board with a constant INVALID pointer, which makes checking for legality quick and painless. This is the approach that I am going to use in Vicki.

0x88 approach
In this approach the first 4 bits stores the row, and the last 4 the column. Since the rows and columns ranges from 0-7, the 3rd and 7th (counting from 0) are not used. By using this technique it is relatively cheap to determine an invalid board position. Merely and with 0x88 (10001000 in binary) and if the value is non-zero, the position is invalid.

This is a technique used by most high-end chess engines. It can be very fast, but is rather tricky to implement, especially the rotated bit-board variety. It is based on the idea of soring information in 64-bit integers. By applying various bitwise operations the boards are manipulated all at once. I am still not sure how to effectively retrieve the list of moves from the bit-board set and have decided to leave this for later.


Anonymous said...

I found this site using [url=][/url] And i want to thank you for your work. You have done really very good site. Great work, great site! Thank you!

Sorry for offtopic

Jaco van Niekerk said...

You are very welcome!

Anonymous said...