25,161
edits
Changes
First trial
'''[[Main Page|Home]] * Board Representation'''
[[File:Paul_Klee_Ueberschach.jpg|left|thumb|200px|Paul Klee, Überschach, 1937 <ref>[[Arts#Klee|Paul Klee]], Ueberschach, 1937, [https://commons.wikimedia.org/wiki/File:Paul_Klee_Ueberschach.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons|Wikimedia Commons], [https://en.wikipedia.org/wiki/Kunsthaus_Z%C3%BCrich|Kunsthaus Zürich]</ref>]] 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.
=<span id="PieceCentric"></span>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]]
=<span id="SquareCentric"></span>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]]
** [[Extended Position Description]] (EPD)
** [[Forsyth-Edwards Notation]] (FEN)
* [[Chinese Chess Board Representation]]
* [[Graphics Programming]]
* [[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 />
'''[[Main Page|Up one Level]]'''
[[File:Paul_Klee_Ueberschach.jpg|left|thumb|200px|Paul Klee, Überschach, 1937 <ref>[[Arts#Klee|Paul Klee]], Ueberschach, 1937, [https://commons.wikimedia.org/wiki/File:Paul_Klee_Ueberschach.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons|Wikimedia Commons], [https://en.wikipedia.org/wiki/Kunsthaus_Z%C3%BCrich|Kunsthaus Zürich]</ref>]] 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.
=<span id="PieceCentric"></span>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]]
=<span id="SquareCentric"></span>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]]
** [[Extended Position Description]] (EPD)
** [[Forsyth-Edwards Notation]] (FEN)
* [[Chinese Chess Board Representation]]
* [[Graphics Programming]]
* [[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 />
'''[[Main Page|Up one Level]]'''
