Contents  Introduction  Basic Board  Representations  Bit Boards  Transposition  Tables  Generating Hash  Keys for Chess  Boards  History Tables  Pre-processing  move generation  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

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