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:

  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