Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
89 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:


 Basic Board

 Bit Boards

 Generating Hash
 Keys for Chess

 History Tables
 move generation

 Printable version


  The Series

 Getting Started
 Data Structures
 Move Generation
 Basic Search
 Advanced Search


Last month, I presented the major building blocks required to write a program to play chess, or any other two-player game of perfect information.  Today, I will discuss in a bit more detail the most fundamental of these building blocks: the internal representation of the game board.

You may be surprised to notice that, for all intents and purposes, the state of the art in this area has not changed in thirty years.  This is due to a combination of ingenuity (i.e., smart people made smart choices very early in the field's history) and necessity (i.e., good data structures were a pre-requisite to everything else, and without these effective techniques, not much would have been achieved.)

While we're at it, I will also present three support data structures which, although not absolutely required to make the computer play, are invaluable if you want it to play well.  Of these, two (one of which consumes ungodly amounts of memory) are designed to accelerate search through the game tree, while the third is used to speed up move generation.

Before we go any further, a word to the wise: in chess as in any other game, the simplest data structure that will get the job done is usually the one you should use.  While chess programmers have developed numerous clever data representation tricks to make their programs go faster, very simple stuff is quite sufficient in many other games.  If you are a novice working on a game for which there is limited literature, start with something easy, encapsulate it well, and you can experiment with more advanced representations once your program works.

Next : Basic Board Representations