Board Representation

**[[Home]] * Board Representation**
|| [[image:Überschach.jpg width="222" height="254" link="http://www.jmrw.com/Chess/Tableau_echecs/pages/045.htm"]] ||~   || A chess program needs an internal **board representation** to maintain [[Chess Position|chess positions]] for its [[Search|search]], [[Evaluation|evaluation]] and [[Chess Game|game-play]]. Beside modelizing the [[Chessboard|chessboard]] with its [[Pieces|piece]]-placement, some additional information is required to fully specify a chess position, such as [[Side to move|side to move]], [[Castling rights|castling rights]], possible [[En passant|en passant]] target square and the number of [[Reversible moves|reversible moves]] to keep track on the [[Fifty-move rule|fifty-move rule]].

To begin with, we further elaborate on the pure data structures to represent the board and its piece-placement. There are piece centric and square centric representations as well as hybrid solutions. ||
|| [[Arts#Klee|Paul Klee]], Überschach, 1937 <ref>[[http://www.jmrw.com/Chess/Tableau_echecs/index.htm|Tableaux Échecs - Chess Paintings]]</ref> ||~   ||^   ||
[[toc]][[#PieceCentric]]
=Piece Centric= 
A **piece centric** representation keeps [[Linked List|lists]], [[Array|arrays]] or sets of all [[Pieces|pieces]] still on the board - with the associated information which [[Squares|square]] they occupy. A popular piece centric representative is the set-wise [[Bitboards|bitboard-approach]]. One 64-bit word for each piece type, where one-bits associate their [[Occupancy|occupancy]].
* [[Piece-Lists]]
* [[Piece-Sets]]
* [[Bitboards]]
[[#SquareCentric]]
=Square Centric= 
The **square centric** representation implements the inverse association - is a [[Squares|square]] empty or is it [[Occupancy|occupied]] by a particular [[Pieces|piece]]? The most popular square centric representations, [[Mailbox|mailbox]] or it's [[0x88]]-enhancements - are basically [[Array|arrays]] of direct [[Pieces#PieceCoding|piece-codes]] including the empty square and probably out of board codes. Hybrid solutions may further refer piece-list entries. 
* [[Mailbox]]
> [[8x8 Board]]
> [[10x12 Board]]
> [[0x88]]
> [[Vector Attacks]]

=Hybrid Solutions= 
While different algorithms and tasks inside a chess program might prefer one of these associations, it is quite common to use redundant board representations with elements of both. Bitboard approaches often keep a 8x8 board to determine a piece by square, while square centric board array approaches typically keep [[Piece-Lists|piece-lists]] and/or [[Piece-Sets|piece-sets]] to avoid scanning the board for [[Move Generation|move generation]] purposes. 

=Move Generation= 
With a board representation, one big consideration is the generation of [[Moves|moves]]. This is essential to the [[Chess Game|game playing]] aspect of a chess program, and it must be completely correct. Writing a good move generator is often the first basic step of creating a chess program.
* [[Move Generation]]
* [[Perft]]

=Make and Unmake= 
* [[Incremental Updates]]
* [[Copy-Make]]
* [[Make Move]]
* [[Unmake Move]]
* [[General Setwise Operations#UpdateByMove|Bitboard Update By Move]]

=See Also= 
* [[Nibble#ArrayOfNibbles|Array of Nibbles]]
* [[Attack and Defend Maps]]
* [[Chess Position]]
* [[Chinese Chess Board Representation]]
* [[Graphics Programming]]
> [[Extended Position Description]] (EPD)
> [[Forsyth-Edwards Notation]] (FEN)
* [[Quad-Bitboards]]

=Publications=
* [[Claude Shannon]] (**1949**). //[[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt|Programming a Computer for Playing Chess]]//. [[http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|pdf]] from [[The Computer History Museum]]
* [[Alex Bell]] (**1972**). //[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm|Games Playing with Computers]]//. [[http://en.wikipedia.org/wiki/Allen_%26_Unwin|Allen & Unwin]], ISBN-13: 978-0080212227
* [[Dan Spracklen]], [[Kathe Spracklen]] (**1978**). //First Steps in Computer Chess Programming//. [[Byte Magazine#BYTE310|BYTE, Vol. 3, No. 10]], [[http://archive.computerhistory.org/projects/chess/related_materials/text/4-4.First_Steps.Byte_Magazine/First_Steps_in_Computer_Chess_Programing.Spracklen-Dan_Kathe.Byte_Magazine.Oct-1978.062303035.sm.pdf|pdf]] from [[The Computer History Museum]]
* [[Vladan Vučković]] (**2008**). //The Compact Chessboard Representation//. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]]
* [[Vladan Vučković]] (**2012**). //An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding//. [[http://www.doiserbia.nb.rs/issue.aspx?issueid=1761|Yugoslav Journal of Operations Research, Vol. 22, No. 1]], [[http://www.doiserbia.nb.rs/img/doi/0354-0243/2012/0354-02431200011V.pdf|pdf]]

=Forum Posts= 
==1999==
* [[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/2ffae88f631ac20d|Datastructures in computer chess]] by Gustav Grundin, [[Computer Chess Forums|rgcc]], May 11, 1999
* [[http://www.stmintz.com/ccc/index.php?id=69942|How do you represent chess boards in your chess programms]] by Brian Nielsen, [[CCC]], September 22, 1999
> [[http://www.stmintz.com/ccc/index.php?id=71016|Re: How do you represent chess boards in your chess programms]] by [[Sven Reichard]], [[CCC]], September 29, 1999
==2000 ...==
* [[http://www.stmintz.com/ccc/index.php?id=265915|Differences between 0x88 ,10x12 and Bitboards!?]] by Axel Grüttner, [[CCC]], November 19, 2002
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2407&p=11195|Fruit's Board Representation?]] by [[Steve Maughan]], [[Computer Chess Forums|Winboard Programming Forum]], April 27, 2005
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4442|Board representation : 0x88 or 10x12 ?]] by Philippe, [[Computer Chess Forums|Winboard Forum]], March 02, 2006
* [[http://www.talkchess.com/forum/viewtopic.php?t=22023|Board Types in '08]] by [[Joshua Shriver]], [[CCC]], June 28, 2008
==2010 ...==
* [[http://www.talkchess.com/forum/viewtopic.php?t=47615|I'm Puzzled - Storing Piece Info & Magic Move Gen...]] by [[Steve Maughan]], [[CCC]], March 27, 2013
* [[http://www.talkchess.com/forum/viewtopic.php?t=48324|Table-less bitboards (bitrays?)]] by [[Harm Geert Muller]], [[CCC]], June 18, 2013
* [[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52878|Best Board Representation for 32bit CPUs]] by net, [[Computer Chess Forums|Winboard Forum]], July 14, 2013
* [[http://talkchess.com/forum/viewtopic.php?t=59691|Some questions from a beginner]] by Tim Hagen, [[CCC]], March 30, 2016
* [[http://www.talkchess.com/forum/viewtopic.php?t=65962|best board representation for variants (javascript) ?]] by [[Mahmoud Uthman]], [[CCC]], December 10, 2017 » [[JavaScript]], [[Games#ChessVariants|Chess Variants]]

=External Links= 
* [[http://en.wikipedia.org/wiki/Board_representation_%28chess%29|Board representation (chess) from Wikipedia]]
* [[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm|Chapter 3: Board Games - 3.1 CHESS]] from [[Alex Bell]] (**1972**). //[[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm|Games Playing with Computers]]//. [[http://en.wikipedia.org/wiki/Allen_%26_Unwin|Allen & Unwin]], ISBN-13: 978-0080212227
* [[http://www.craftychess.com/hyatt/boardrep.html|Chess board representations]] by [[Robert Hyatt]]
* [[http://www.ics.uci.edu/~eppstein/180a/970408.html|Board representations | Lecture notes]] by [[David Eppstein]], April 8, 1997
* [[http://chess.verhelst.org/1997/03/10/representations/|Chess Board Representations]] by [[Paul Verhelst]]
* [[http://www.fam-petzke.de/cp_board_en.shtml|Chess Programming - The Chess Board]] by [[Thomas Petzke]]
* [[http://lexicon.ft.com/term.asp?t=board-representation|board representation definition]] from [[http://lexicon.ft.com/overview.asp|Financial Times Lexicon]]
* [[http://labraj.uni-mb.si/en/Representation_of_Chess_Game|Representation of Chess Game - Computer Architecture and Languages Laboratory]], [[University of Maribor]]

=References= 
<references />
**[[Home|Up one Level]]**