25,161
edits
Changes
Created page with "'''Home * Chess * Position''' FILE:DuchampGlassBoard.jpg|border|right|thumb||link=http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp |[[Arts#Duc..."
'''[[Main Page|Home]] * [[Chess]] * Position'''
[[FILE:DuchampGlassBoard.jpg|border|right|thumb||link=http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp
|[[Arts#Duchamp|Marcel Duchamp]] <ref>Photo by [https://en.wikipedia.org/wiki/Arnold_T._Rosenberg Arnold T. Rosenberg], [[Arts#Duchamp|Marcel Duchamp]] playing chess on a sheet of Glass, 1958, see [https://en.wikipedia.org/wiki/Francis_Naumann Francis M. Naumann], [https://www.slu.edu/arts-and-sciences/fine-and-performing-arts/faculty/bailey-bradley.php Bradley Bailey] ('''2009'''). ''[http://www.francisnaumann.com/Chess%20Book/ Marcel Duchamp: The Art of Chess]''</ref> <ref>[http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp Marcel Duchamp: Chess Master] [https://www.slu.edu/sluma-home Saint Louis University Museum of Art] [https://en.wikipedia.org/wiki/Saint_Louis_University Saint Louis University : SLU]</ref>
]]
The '''Chess Position''' describes how [[Pieces|pieces]] are placed on the [[Chessboard|chessboard]], as printed as [[Diagrams|chess diagram]], image or photograph from a [[Chess Game|game of chess]]. In 1996 [[Shirish Chinchalkar]] determined 10<span style="vertical-align: super; font-size: 90%;">46</span> as upper bound for the number of reachable chess positions <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>. The [[Encoding Moves#MoveIndex|maximum number of moves]] per chess position seems 218 <ref>[https://www.stmintz.com/ccc/index.php?id=424966 Subject: Maximum Number of Legal Moves] by [http://onezero.org/ Andrew Shapira], [[Computer Chess Forums|CCC]], May 08, 2005</ref>.
Of course, the information of any arbitrary chess position which occurs inside the game of chess, might be determined from a certain initial starting position and a [[Move List|sequence of moves]] (half-moves), which leads to this position. Anyway, an efficient data structure for a chess position, which is [[Incremental Updates|incrementally updated]] during game play and [[Search|search]] is essential for a chess playing program.
=Specifying a Chess Position=
Except the determination of three fold [[Repetitions|repetitions]], which requires the whole move record, at least from the last [[Irreversible Moves|irreversible move]] (half-move) played, the chess position should keep track of various informations related to the position also for efficiency reasons. Another issue is to make chess positions persistent with a maximum of information required, but without the whole game history, as specified by the [[Forsyth-Edwards Notation]] or [[Extended Position Description]].
Beside piece placement, as considered by the [[Board Representation|board representation]], the [[Side to move|side to move]] is essential, which might take only one [[Bit|bit]] inside an appropriate data structure for a chess position. Additionally, the [[Castling]] ability for both sides, as reflected by the [[Castling rights|castling rights]] and a possible [[En passant|en passant]] target square (or [[Files|file]]) is needed to further completely specify the position, as well as the [[Halfmove Clock|halfmove clock]] to cover the [[Fifty-move Rule|fifty-move rule]].
=Summary=
A chess positions consists of
* [[Pieces|Piece]] placement on the [[Chessboard]] as considered by the [[Board Representation]]
* [[Side to move]]
* [[Castling rights]]
* [[En passant]] target square
* [[Halfmove Clock]]
=Positions inside the Search=
In the context of Search, a position is the [[Node|node]] inside a [[Search Tree|search tree]]. To completely determine the position with respect to [[Repetitions|repetitions]], one additionally needs a [[Move List|move list]] or any other appropriate data structure, to keep up to 100 reversible half-moves, likely associated with [[Zobrist Hashing|Zobrist keys]] of the intermediate positions.
* [[Incremental Updates]]
* [[Copy-Make]]
=Positions=
* [[Initial Position]]
* [[Test-Positions]]
=Notations=
* [[Extended Position Description]] (EPD)
* [[Forsyth-Edwards Notation]] (FEN)
* [[Forsyth-Edwards Expanded Notation]] (FEEN)
=Flipping and Mirroring=
* [[Color Flipping]]
* [[Diagonal Mirroring]]
* [[Horizontal Mirroring]]
* [[Vertical Flipping]]
=See Also=
* [[Board Representation]]
* [[Chess Game]]
* [[Chess#Maxima|Chess Maxima]]
* [[Chessboard]]
* [[Diagrams]]
* [[Graphics Programming]]
* [[Moves]]
* [[Node]]
* [[Pieces]]
: [[Piece Recognition]]
* [[Transposition]]
* [[User Interface]]
=Publications=
* [[Jürg Nievergelt]] ('''1977'''). ''Information content of chess positions.'' ACM SIGART Newsletter 62, pp. 13-14. Reprinted as: ''Information content of chess positions: Implications for game-specific knowledge of chess players'', pp. 283-289. [http://www.doc.ic.ac.uk/~shm/MI/mi12.html Machine Intelligence 12] (eds. [[Jean Hayes Michie]], [[Donald Michie]], [http://www.cs.ioc.ee/~tyugu/ E. Tyugu]). Clarendon Press, Oxford, 1991. ISBN 0-19-853823-5.
* [[Bernhard Balkenhol]] ('''1994'''). ''Data Compression in Encoding Chess Positions.'' [[ICGA Journal#17_3|ICCA Journal, Vol. 17, No. 3]], [http://www.balkenhol.net/papers/icca94.ps.gz zipped ps]
* [[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]
* [[Alex de Voogt]] ('''2002'''). ''[http://psycnet.apa.org/index.cfm?fa=buy.optionToBuy&id=2003-03501-005 Reproducing board game positions: Western Chess and African Bao]''. [http://www.verlag-hanshuber.com/zeitschriften/journal.php?abbrev=sjp&show=editorial Swiss Journal of Psychology], Vol 61, No. 4
=Forum Posts=
==1980 ...==
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.05_sri-unix.426_net.chess.txt compact representation of a position] by [[Bill Vaughan]], net.chess, January 5, 1982
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982 » [[Zobrist Hashing]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a0a82ffbb59b7ced Re: Hashing function for board positions] post 4 by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997</ref>
==1990 ...==
* [https://groups.google.com/d/msg/rec.games.chess/pyM6LfZPbvY/DO2V0y4BezIJ entropy of chess positions] by [[John Tromp]], [[Computer Chess Forums|rgc]], April 15, 1991
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c15c92ded7ed6400/ estimated number of chesspositions] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], October 27, 1995
* [https://www.stmintz.com/ccc/index.php?id=69647 number of moves in position] by [[Leonid Liberman|Leonid]], [[CCC]], September 19, 1999
: [https://www.stmintz.com/ccc/index.php?id=69704 Re: number of moves in position] by [[Leonid Liberman|Leonid]], [[CCC]], September 21, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=106847 Min # of bits needed to store a chess position] by [[James Robertson]], [[CCC]], April 20, 2000
* [http://mathforum.org/kb/message.jspa?messageID=364071 Minimum bits to encode a chess position] by Ken Payson, [http://mathforum.org/ The Math Forum @ Drexel University], February 8, 2002
* [https://www.stmintz.com/ccc/index.php?id=323898 Making positions in eps] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], October 27, 2003 » [[Forsyth-Edwards Notation#FEN2EPS|Fen2eps]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=48952 allowing invalid positions] by Eric Langedijk, [[CCC]], August 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50832 Counting endgame positions] by [[Kirill Kryukov]], [[CCC]], January 08, 2014 <ref>[http://kirill-kryukov.com/chess/nulp/ NULP in chess endgames] by [[Kirill Kryukov]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=51744 Total possible chess positions?] by [[Matthew R. Brades]], [[CCC]], March 26, 2014 » [[Chess#Maxima|Chess Maxima]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57065 Binary FEN] by [[J. Wesley Cleveland]], [[CCC]], July 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61792 Max moves in a position] by [[Laurie Tunnicliffe]], [[CCC]], October 22, 2016 » [[Chess#Maxima|Chess Maxima]], [[Move List]]
=External Links=
* [http://stackoverflow.com/questions/1831386/programmer-puzzle-encoding-a-chess-board-state-throughout-a-game Programmer Puzzle: Encoding a chess board state throughout a game] from [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow]
* [http://www.chesspositiontrainer.com/ Chess Position Trainer] by Stefan Renzewitz and Gregory Prentice
* [http://kirill-kryukov.com/chess/nulp/ NULP in chess endgames] by [[Kirill Kryukov]]
=References=
<references />
'''[[Chess|Up one Level]]'''
[[FILE:DuchampGlassBoard.jpg|border|right|thumb||link=http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp
|[[Arts#Duchamp|Marcel Duchamp]] <ref>Photo by [https://en.wikipedia.org/wiki/Arnold_T._Rosenberg Arnold T. Rosenberg], [[Arts#Duchamp|Marcel Duchamp]] playing chess on a sheet of Glass, 1958, see [https://en.wikipedia.org/wiki/Francis_Naumann Francis M. Naumann], [https://www.slu.edu/arts-and-sciences/fine-and-performing-arts/faculty/bailey-bradley.php Bradley Bailey] ('''2009'''). ''[http://www.francisnaumann.com/Chess%20Book/ Marcel Duchamp: The Art of Chess]''</ref> <ref>[http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp Marcel Duchamp: Chess Master] [https://www.slu.edu/sluma-home Saint Louis University Museum of Art] [https://en.wikipedia.org/wiki/Saint_Louis_University Saint Louis University : SLU]</ref>
]]
The '''Chess Position''' describes how [[Pieces|pieces]] are placed on the [[Chessboard|chessboard]], as printed as [[Diagrams|chess diagram]], image or photograph from a [[Chess Game|game of chess]]. In 1996 [[Shirish Chinchalkar]] determined 10<span style="vertical-align: super; font-size: 90%;">46</span> as upper bound for the number of reachable chess positions <ref>[[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]</ref>. The [[Encoding Moves#MoveIndex|maximum number of moves]] per chess position seems 218 <ref>[https://www.stmintz.com/ccc/index.php?id=424966 Subject: Maximum Number of Legal Moves] by [http://onezero.org/ Andrew Shapira], [[Computer Chess Forums|CCC]], May 08, 2005</ref>.
Of course, the information of any arbitrary chess position which occurs inside the game of chess, might be determined from a certain initial starting position and a [[Move List|sequence of moves]] (half-moves), which leads to this position. Anyway, an efficient data structure for a chess position, which is [[Incremental Updates|incrementally updated]] during game play and [[Search|search]] is essential for a chess playing program.
=Specifying a Chess Position=
Except the determination of three fold [[Repetitions|repetitions]], which requires the whole move record, at least from the last [[Irreversible Moves|irreversible move]] (half-move) played, the chess position should keep track of various informations related to the position also for efficiency reasons. Another issue is to make chess positions persistent with a maximum of information required, but without the whole game history, as specified by the [[Forsyth-Edwards Notation]] or [[Extended Position Description]].
Beside piece placement, as considered by the [[Board Representation|board representation]], the [[Side to move|side to move]] is essential, which might take only one [[Bit|bit]] inside an appropriate data structure for a chess position. Additionally, the [[Castling]] ability for both sides, as reflected by the [[Castling rights|castling rights]] and a possible [[En passant|en passant]] target square (or [[Files|file]]) is needed to further completely specify the position, as well as the [[Halfmove Clock|halfmove clock]] to cover the [[Fifty-move Rule|fifty-move rule]].
=Summary=
A chess positions consists of
* [[Pieces|Piece]] placement on the [[Chessboard]] as considered by the [[Board Representation]]
* [[Side to move]]
* [[Castling rights]]
* [[En passant]] target square
* [[Halfmove Clock]]
=Positions inside the Search=
In the context of Search, a position is the [[Node|node]] inside a [[Search Tree|search tree]]. To completely determine the position with respect to [[Repetitions|repetitions]], one additionally needs a [[Move List|move list]] or any other appropriate data structure, to keep up to 100 reversible half-moves, likely associated with [[Zobrist Hashing|Zobrist keys]] of the intermediate positions.
* [[Incremental Updates]]
* [[Copy-Make]]
=Positions=
* [[Initial Position]]
* [[Test-Positions]]
=Notations=
* [[Extended Position Description]] (EPD)
* [[Forsyth-Edwards Notation]] (FEN)
* [[Forsyth-Edwards Expanded Notation]] (FEEN)
=Flipping and Mirroring=
* [[Color Flipping]]
* [[Diagonal Mirroring]]
* [[Horizontal Mirroring]]
* [[Vertical Flipping]]
=See Also=
* [[Board Representation]]
* [[Chess Game]]
* [[Chess#Maxima|Chess Maxima]]
* [[Chessboard]]
* [[Diagrams]]
* [[Graphics Programming]]
* [[Moves]]
* [[Node]]
* [[Pieces]]
: [[Piece Recognition]]
* [[Transposition]]
* [[User Interface]]
=Publications=
* [[Jürg Nievergelt]] ('''1977'''). ''Information content of chess positions.'' ACM SIGART Newsletter 62, pp. 13-14. Reprinted as: ''Information content of chess positions: Implications for game-specific knowledge of chess players'', pp. 283-289. [http://www.doc.ic.ac.uk/~shm/MI/mi12.html Machine Intelligence 12] (eds. [[Jean Hayes Michie]], [[Donald Michie]], [http://www.cs.ioc.ee/~tyugu/ E. Tyugu]). Clarendon Press, Oxford, 1991. ISBN 0-19-853823-5.
* [[Bernhard Balkenhol]] ('''1994'''). ''Data Compression in Encoding Chess Positions.'' [[ICGA Journal#17_3|ICCA Journal, Vol. 17, No. 3]], [http://www.balkenhol.net/papers/icca94.ps.gz zipped ps]
* [[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]]
* [[Alex de Voogt]] ('''2002'''). ''[http://psycnet.apa.org/index.cfm?fa=buy.optionToBuy&id=2003-03501-005 Reproducing board game positions: Western Chess and African Bao]''. [http://www.verlag-hanshuber.com/zeitschriften/journal.php?abbrev=sjp&show=editorial Swiss Journal of Psychology], Vol 61, No. 4
=Forum Posts=
==1980 ...==
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.05_sri-unix.426_net.chess.txt compact representation of a position] by [[Bill Vaughan]], net.chess, January 5, 1982
* [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt compact representation of chess positions] by [[Tom Truscott]], net.chess, January 7, 1982 » [[Zobrist Hashing]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/a0a82ffbb59b7ced Re: Hashing function for board positions] post 4 by [[James Gillogly|Jim Gillogly]], [[Computer Chess Forums|rgcc]], May 12, 1997</ref>
==1990 ...==
* [https://groups.google.com/d/msg/rec.games.chess/pyM6LfZPbvY/DO2V0y4BezIJ entropy of chess positions] by [[John Tromp]], [[Computer Chess Forums|rgc]], April 15, 1991
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/c15c92ded7ed6400/ estimated number of chesspositions] by [[Vincent Diepeveen]], [[Computer Chess Forums|rgcc]], October 27, 1995
* [https://www.stmintz.com/ccc/index.php?id=69647 number of moves in position] by [[Leonid Liberman|Leonid]], [[CCC]], September 19, 1999
: [https://www.stmintz.com/ccc/index.php?id=69704 Re: number of moves in position] by [[Leonid Liberman|Leonid]], [[CCC]], September 21, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=106847 Min # of bits needed to store a chess position] by [[James Robertson]], [[CCC]], April 20, 2000
* [http://mathforum.org/kb/message.jspa?messageID=364071 Minimum bits to encode a chess position] by Ken Payson, [http://mathforum.org/ The Math Forum @ Drexel University], February 8, 2002
* [https://www.stmintz.com/ccc/index.php?id=323898 Making positions in eps] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], October 27, 2003 » [[Forsyth-Edwards Notation#FEN2EPS|Fen2eps]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=48952 allowing invalid positions] by Eric Langedijk, [[CCC]], August 13, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=50832 Counting endgame positions] by [[Kirill Kryukov]], [[CCC]], January 08, 2014 <ref>[http://kirill-kryukov.com/chess/nulp/ NULP in chess endgames] by [[Kirill Kryukov]]</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=51744 Total possible chess positions?] by [[Matthew R. Brades]], [[CCC]], March 26, 2014 » [[Chess#Maxima|Chess Maxima]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57065 Binary FEN] by [[J. Wesley Cleveland]], [[CCC]], July 24, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=61792 Max moves in a position] by [[Laurie Tunnicliffe]], [[CCC]], October 22, 2016 » [[Chess#Maxima|Chess Maxima]], [[Move List]]
=External Links=
* [http://stackoverflow.com/questions/1831386/programmer-puzzle-encoding-a-chess-board-state-throughout-a-game Programmer Puzzle: Encoding a chess board state throughout a game] from [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow]
* [http://www.chesspositiontrainer.com/ Chess Position Trainer] by Stefan Renzewitz and Gregory Prentice
* [http://kirill-kryukov.com/chess/nulp/ NULP in chess endgames] by [[Kirill Kryukov]]
=References=
<references />
'''[[Chess|Up one Level]]'''
