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

 Games of Perfect
 Information

 What We Need
 Board
 Representations

 Move Generation
 Search Techniques
 Evaluation

 Printable version

 


  The Series

 Getting Started
 Data Structures
 Move Generation
 Basic Search
 Advanced Search
 Evaluation
 Functions


 

Board Representations

In the early days of chess programming, memory was extremely limited (some programs ran in 8K or less) and the simplest, least expensive representations were the most effective.  A typical chessboard was implemented as an 8x8 array, with each square represented by a single byte: an empty square was allocated value 0, a black king could be represented by the number 1, etc.

When chess programmers started working on 64-bit workstations and mainframes, more elaborate board representations based on "bitboards" appeared.  Apparently invented in the Soviet Union in the late 1960's, the bit board is a 64-bit word containing information about one aspect of the game state, at a rate of 1 bit per square.  For example, a bitboard might contain "the set of squares occupied by black pawns", another "the set of squares to which a queen on e3 can move", and another, "the set of white pieces currently attacked by black knights". Bitboards are versatile and allow fast processing, because many operations that are repeated very often in the course of a chess game can be implemented as 1-cycle logic operations on bitboards.

Part II of this series covers board representations in detail.


Next : Move Generation