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

Basic Board Representations

Back in the 1970's, personal computer memory was at a premium (that's an understatement if there ever was one!), so the most compact the board representations, the better.  There is a lot to be said for the most self-evident scheme: a 64-byte array, where each byte represents a single square on the board and contains an integer constant representing the piece located in that square.  (Any chess board data structure also needs a few bytes of storage to track down en passant pawn capture opportunities and castling privileges, but we'll ignore that for now, since this is usually implemented separately, and pretty much always the same way.)

A few refinements on this technique soon became popular:

• The original SARGON extended the 64-byte array by surounding it with two layers of "bogus squares" containing sentinel values marking the squares as illegal.  This trick accelerated move generation: for example, a bishop would generate moves by sliding one square at a time until it reached an illegal square, then stop.  No need for complicated a priori computations to make sure that a move would not take a piece out of the memory area associated with the board.  The second layer of fake squares is required by knight moves: for example, a knight on a corner square might try to jump out of bounds by two columns, so a single protection layer would be no protection at all!
• MYCHESS reversed the process and represented the board in only 32 bytes, each of which was associated with a single piece (i.e., the white king, the black King's Knight's pawn, etc.) and contained the number of the square where that piece was located, or a sentinel value if the piece had been captured.  This technique had a serious drawback: it was impossible to promote a pawn to a piece which had not already been captured.  Later versions of the program fixed this problem.

Today, this type of super-miserly structure would only be useful (maybe) if you wrote a chess program for a Palm Pilot, a cell phone or a set-top box where 80-90% of resources are consumed by the operating system and non-game services.  However, for some other types of games, there is really no alternative!

For more information on vintage chess programs, read David Welsh's book, Computer Chess, published in 1984.

Next : Bit Boards