Difference between revisions of "Board Representation"

From Chessprogramming wiki
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 49: 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 61: 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 68: 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 74: 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://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://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]]
 
* [http://labraj.uni-mb.si/en/Representation_of_Chess_Game Representation of Chess Game - Computer Architecture and Languages Laboratory], [[University of Maribor]]
  

Latest revision as of 21:01, 28 January 2020

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 ...

Re: Yet another new bitboard move generation method by Harm Geert Muller, Winboard Forum, October 01, 2006 [2]

2010 ...

External Links

References

Up one Level