Difference between revisions of "Board Representation"

From Chessprogramming wiki
Jump to: navigation, search
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 68: 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=  

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