Difference between revisions of "Board Representation"

From Chessprogramming wiki
Jump to: navigation, search
(First trial)
 
(10 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * Board Representation'''
 
'''[[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]].
+
[[File:Paul_Klee_Ueberschach.jpg|border|right|thumb|240px|[[:Category:Paul Klee|Paul Klee]] - Überschach, 1937 <ref>[[:Category:Paul 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.  
 
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.  
Line 16: Line 17:
 
** [[8x8 Board]]
 
** [[8x8 Board]]
 
** [[10x12 Board]]
 
** [[10x12 Board]]
** [[0x88]]
 
 
** [[Vector Attacks]]
 
** [[Vector Attacks]]
 +
:: [[0x88]]
  
 
=Hybrid Solutions=  
 
=Hybrid Solutions=  
Line 48: Line 49:
 
* [[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
 
* [[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]]
 
* [[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ć]] ('''2008'''). ''The Compact Chessboard Representation''. [[ICGA Journal#31_3|ICGA Journal, Vol. 31, No. 3]] » [[Nibble#ArrayOfNibbles|Array of Nibbles]]
 
* [[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]
 
* [[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]
  
Line 67: Line 68:
 
* [http://talkchess.com/forum/viewtopic.php?t=59691 Some questions from a beginner] by Tim Hagen, [[CCC]], March 30, 2016
 
* [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]]
 
* [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]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69046 CCR board representation] by [[Maksim Korzh]], [[CCC]], November 25, 2018 » [[Nibble#ArrayOfNibbles|Array of Nibbles]]
  
 
=External Links=  
 
=External Links=  
Line 81: Line 83:
 
<references />
 
<references />
 
'''[[Main Page|Up one Level]]'''
 
'''[[Main Page|Up one Level]]'''
 +
[[Category:Paul Klee]]

Revision as of 09:51, 26 January 2019

Home * Board Representation

Paul Klee - Überschach, 1937 [1]

A chess program needs an internal board representation to maintain chess positions for its search, evaluation and game-play. Beside modelizing the chessboard with its piece-placement, some additional information is required to fully specify a chess position, such as side to move, castling rights, possible en passant target square and the number of reversible moves to keep track on the 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.

Piece Centric

A piece centric representation keeps lists, arrays or sets of all pieces still on the board - with the associated information which square they occupy. A popular piece centric representative is the set-wise bitboard-approach. One 64-bit word for each piece type, where one-bits associate their occupancy.

Square Centric

The square centric representation implements the inverse association - is a square empty or is it occupied by a particular piece? The most popular square centric representations, mailbox or it's 0x88-enhancements - are basically arrays of direct piece-codes including the empty square and probably out of board codes. Hybrid solutions may further refer piece-list entries.

0x88

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 and/or piece-sets to avoid scanning the board for move generation purposes.

Move Generation

With a board representation, one big consideration is the generation of moves. This is essential to the 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.

Make and Unmake

See Also

Publications

Forum Posts

1999

2000 ...

2010 ...

External Links

References

Up one Level