Difference between revisions of "Board Representation"
GerdIsenberg (talk | contribs) (First trial) |
GerdIsenberg (talk | contribs) |
||
| (12 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| | + | [[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]] | ||
| − | |||
** [[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 60: | Line 61: | ||
* [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=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.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.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006 » [[Titboards]] | ||
| + | : [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&start=6 Re: Yet another new bitboard move generation method] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], October 01, 2006 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=52861&start=8 Re: multi-dimensional piece/square tables] by Tony P., [[CCC]], January 28, 2020</ref> | ||
* [http://www.talkchess.com/forum/viewtopic.php?t=22023 Board Types in '08] by [[Joshua Shriver]], [[CCC]], June 28, 2008 | * [http://www.talkchess.com/forum/viewtopic.php?t=22023 Board Types in '08] by [[Joshua Shriver]], [[CCC]], June 28, 2008 | ||
==2010 ...== | ==2010 ...== | ||
| Line 67: | Line 70: | ||
* [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 73: | Line 77: | ||
* [http://www.craftychess.com/hyatt/boardrep.html Chess board representations] by [[Robert Hyatt]] | * [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://www.ics.uci.edu/~eppstein/180a/970408.html Board representations | Lecture notes] by [[David Eppstein]], April 8, 1997 | ||
| − | |||
* [http://www.fam-petzke.de/cp_board_en.shtml Chess Programming - The Chess Board] by [[Thomas Petzke]] | * [http://www.fam-petzke.de/cp_board_en.shtml Chess Programming - The Chess Board] by [[Thomas Petzke]] | ||
| − | |||
* [http://labraj.uni-mb.si/en/Representation_of_Chess_Game Representation of Chess Game - Computer Architecture and Languages Laboratory], [[University of Maribor]] | * [http://labraj.uni-mb.si/en/Representation_of_Chess_Game Representation of Chess Game - Computer Architecture and Languages Laboratory], [[University of Maribor]] | ||
| Line 81: | Line 83: | ||
<references /> | <references /> | ||
'''[[Main Page|Up one Level]]''' | '''[[Main Page|Up one Level]]''' | ||
| + | [[Category:Paul Klee]] | ||
Latest revision as of 22:01, 28 January 2020
Home * Board Representation
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.
Contents
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.
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
- Array of Nibbles
- Attack and Defend Maps
- Chess Position
- Chinese Chess Board Representation
- Graphics Programming
- Quad-Bitboards
Publications
- Claude Shannon (1949). Programming a Computer for Playing Chess. pdf from The Computer History Museum
- Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
- Dan Spracklen, Kathe Spracklen (1978). First Steps in Computer Chess Programming. BYTE, Vol. 3, No. 10, pdf from The Computer History Museum
- Vladan Vučković (2008). The Compact Chessboard Representation. ICGA Journal, Vol. 31, No. 3 » Array of Nibbles
- Vladan Vučković (2012). An Alternative Efficient Chessboard Representation based on 4-Bit Piece Coding. Yugoslav Journal of Operations Research, Vol. 22, No. 1, pdf
Forum Posts
1999
- Datastructures in computer chess by Gustav Grundin, rgcc, May 11, 1999
- How do you represent chess boards in your chess programms by Brian Nielsen, CCC, September 22, 1999
- Re: How do you represent chess boards in your chess programms by Sven Reichard, CCC, September 29, 1999
2000 ...
- Differences between 0x88 ,10x12 and Bitboards!? by Axel Grüttner, CCC, November 19, 2002
- Fruit's Board Representation? by Steve Maughan, Winboard Programming Forum, April 27, 2005
- Board representation : 0x88 or 10x12 ? by Philippe, Winboard Forum, March 02, 2006
- Yet another new bitboard move generation method by Zach Wegner, Winboard Forum, September 22, 2006 » Titboards
- Re: Yet another new bitboard move generation method by Harm Geert Muller, Winboard Forum, October 01, 2006 [2]
- Board Types in '08 by Joshua Shriver, CCC, June 28, 2008
2010 ...
- I'm Puzzled - Storing Piece Info & Magic Move Gen... by Steve Maughan, CCC, March 27, 2013
- Table-less bitboards (bitrays?) by Harm Geert Muller, CCC, June 18, 2013
- Best Board Representation for 32bit CPUs by net, Winboard Forum, July 14, 2013
- Some questions from a beginner by Tim Hagen, CCC, March 30, 2016
- best board representation for variants (javascript) ? by Mahmoud Uthman, CCC, December 10, 2017 » JavaScript, Chess Variants
- CCR board representation by Maksim Korzh, CCC, November 25, 2018 » Array of Nibbles
External Links
- Board representation (chess) from Wikipedia
- Chapter 3: Board Games - 3.1 CHESS from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
- Chess board representations by Robert Hyatt
- Board representations | Lecture notes by David Eppstein, April 8, 1997
- Chess Programming - The Chess Board by Thomas Petzke
- Representation of Chess Game - Computer Architecture and Languages Laboratory, University of Maribor
References
- ↑ Paul Klee - Ueberschach, 1937, [1] Wikimedia Commons, Kunsthaus Zürich
- ↑ Re: multi-dimensional piece/square tables by Tony P., CCC, January 28, 2020
![[1]](https://commons.wikimedia.org/wiki/File:Paul_Klee_Ueberschach.jpg){kind=link}