Difference between revisions of "Chess Position"
GerdIsenberg (talk | contribs) (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...") |
GerdIsenberg (talk | contribs) |
||
(11 intermediate revisions by the same user not shown) | |||
Line 2: | Line 2: | ||
[[FILE:DuchampGlassBoard.jpg|border|right|thumb||link=http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp | [[FILE:DuchampGlassBoard.jpg|border|right|thumb||link=http://www.slu.edu/sluma-home/past-exhibitions/2009/duchamp | ||
− | |[[ | + | |[[:Category:Marcel Duchamp|Marcel Duchamp]] <ref>Photo by [https://en.wikipedia.org/wiki/Arnold_T._Rosenberg Arnold T. Rosenberg], [[:Category:Marcel 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 | + | The '''Chess Position''' describes how [[Pieces|pieces]] are placed on the [[Chessboard|chessboard]], as printed as 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 [[Andrew Shapira]], [[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. | 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. | ||
Line 12: | Line 12: | ||
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]]. | 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 | + | 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= | =Summary= | ||
Line 18: | Line 18: | ||
* [[Pieces|Piece]] placement on the [[Chessboard]] as considered by the [[Board Representation]] | * [[Pieces|Piece]] placement on the [[Chessboard]] as considered by the [[Board Representation]] | ||
* [[Side to move]] | * [[Side to move]] | ||
− | * [[Castling | + | * [[Castling Rights]] |
* [[En passant]] target square | * [[En passant]] target square | ||
* [[Halfmove Clock]] | * [[Halfmove Clock]] | ||
Line 47: | Line 47: | ||
* [[Chess#Maxima|Chess Maxima]] | * [[Chess#Maxima|Chess Maxima]] | ||
* [[Chessboard]] | * [[Chessboard]] | ||
− | |||
* [[Graphics Programming]] | * [[Graphics Programming]] | ||
* [[Moves]] | * [[Moves]] | ||
Line 53: | Line 52: | ||
* [[Pieces]] | * [[Pieces]] | ||
: [[Piece Recognition]] | : [[Piece Recognition]] | ||
+ | * [[Retrograde Analysis]] | ||
* [[Transposition]] | * [[Transposition]] | ||
* [[User Interface]] | * [[User Interface]] | ||
Line 61: | Line 61: | ||
* [[Shirish Chinchalkar]] ('''1996'''). ''An Upper Bound for the Number of Reachable Positions''. [[ICGA Journal#19_3|ICCA Journal, Vol. 19, No. 3]] | * [[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 | * [[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 | ||
+ | * [[Manuel Cristóbal López-Michelone]], [[Jorge Luis Ortega-Arjona]] ('''2020'''). ''A description language for chess''. [[ICGA Journal#42_1|ICGA Journal, Vol. 42, No. 1]] | ||
=Forum Posts= | =Forum Posts= | ||
==1980 ...== | ==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.05_sri-unix.426_net.chess.txt sri-unix.426: compact representation of a position] by [[Bill Vaughan]], [http://quux.org:70/Archives/usenet-a-news/NET.chess 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> | + | * [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.05_duke.1553_net.chess.txt Re: sri-unix.426: compact representation of a position] by [[Tom Truscott]], [http://quux.org:70/Archives/usenet-a-news/NET.chess net.chess], January 5, 1982 |
+ | * [http://quux.org:70/Archives/usenet-a-news/NET.chess/82.01.07_duke.1593_net.chess.txt Re: sri-unix.444: compact representation of chess positions] by [[Tom Truscott]], [http://quux.org:70/Archives/usenet-a-news/NET.chess 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 ...== | ==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 | * [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 | ||
Line 79: | Line 81: | ||
* [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=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]] | * [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]] | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=52214 Position validity] by [[Russell Reagan]], [[CCC]], May 04, 2014 | ||
==2015 ...== | ==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=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]] | * [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]] | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73614 Canonical Position Representation] by Dmitry Shechtman, [[CCC]], April 10, 2020 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685 On the number of chess positions] by [[John Tromp]], [[CCC]], July 09, 2021 | ||
+ | : [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685&start=34 Re: On the number of chess positions] by [[John Tromp]], [[CCC]], April 02, 2022 | ||
+ | : [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=77685&start=42 Re: On the number of chess positions] by [[Peter Österlund]], [[CCC]], April 03, 2022 » [[Retrograde Analysis]] | ||
=External Links= | =External Links= | ||
− | * [ | + | * [https://github.com/tromp/ChessPositionRanking GitHub - tromp/ChessPositionRanking: Software suite for ranking chess positions and accurately estimating the number of legal chess positions] |
− | * [ | + | * [https://stackoverflow.com/questions/1831386/programmer-puzzle-encoding-a-chess-board-state-throughout-a-game Puzzle: Encoding a chess board state throughout a game] from [https://en.wikipedia.org/wiki/Stack_Overflow Stack Overflow] |
− | * [ | + | * [https://www.chesspositiontrainer.com/index.php/en/ Chess Position Trainer] by Stefan Renzewitz and Gregory Prentice |
+ | * [https://kirill-kryukov.com/chess/nulp/ NULP in chess endgames] by [[Kirill Kryukov]] | ||
=References= | =References= | ||
Line 92: | Line 101: | ||
'''[[Chess|Up one Level]]''' | '''[[Chess|Up one Level]]''' | ||
+ | [[Category:Marcel Duchamp]] |
Latest revision as of 11:43, 4 April 2022
The Chess Position describes how pieces are placed on the chessboard, as printed as chess diagram, image or photograph from a game of chess. In 1996 Shirish Chinchalkar determined 1046 as upper bound for the number of reachable chess positions [3]. The maximum number of moves per chess position seems 218 [4].
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 sequence of moves (half-moves), which leads to this position. Anyway, an efficient data structure for a chess position, which is incrementally updated during game play and search is essential for a chess playing program.
Contents
Specifying a Chess Position
Except the determination of three fold repetitions, which requires the whole move record, at least from the last 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, the side to move is essential, which might take only one bit inside an appropriate data structure for a chess position. Additionally, the Castling ability for both sides, as reflected by the castling rights and a possible en passant target square (or file) is needed to further completely specify the position, as well as the halfmove clock to cover the fifty-move rule.
Summary
A chess positions consists of
- 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 inside a search tree. To completely determine the position with respect to repetitions, one additionally needs a move list or any other appropriate data structure, to keep up to 100 reversible half-moves, likely associated with Zobrist keys of the intermediate positions.
Positions
Notations
- Extended Position Description (EPD)
- Forsyth-Edwards Notation (FEN)
- Forsyth-Edwards Expanded Notation (FEEN)
Flipping and Mirroring
See Also
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. Machine Intelligence 12 (eds. Jean Hayes Michie, Donald Michie, E. Tyugu). Clarendon Press, Oxford, 1991. ISBN 0-19-853823-5.
- Bernhard Balkenhol (1994). Data Compression in Encoding Chess Positions. ICCA Journal, Vol. 17, No. 3, zipped ps
- Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
- Alex de Voogt (2002). Reproducing board game positions: Western Chess and African Bao. Swiss Journal of Psychology, Vol 61, No. 4
- Manuel Cristóbal López-Michelone, Jorge Luis Ortega-Arjona (2020). A description language for chess. ICGA Journal, Vol. 42, No. 1
Forum Posts
1980 ...
- sri-unix.426: compact representation of a position by Bill Vaughan, net.chess January 5, 1982
- Re: sri-unix.426: compact representation of a position by Tom Truscott, net.chess, January 5, 1982
- Re: sri-unix.444: compact representation of chess positions by Tom Truscott, net.chess, January 7, 1982 » Zobrist Hashing [5]
1990 ...
- entropy of chess positions by John Tromp, rgc, April 15, 1991
- estimated number of chesspositions by Vincent Diepeveen, rgcc, October 27, 1995
- number of moves in position by Leonid, CCC, September 19, 1999
- Re: number of moves in position by Leonid, CCC, September 21, 1999
2000 ...
- Min # of bits needed to store a chess position by James Robertson, CCC, April 20, 2000
- Minimum bits to encode a chess position by Ken Payson, The Math Forum @ Drexel University, February 8, 2002
- Making positions in eps by Renze Steenhuisen, CCC, October 27, 2003 » Fen2eps
2010 ...
- allowing invalid positions by Eric Langedijk, CCC, August 13, 2013
- Counting endgame positions by Kirill Kryukov, CCC, January 08, 2014 [6]
- Total possible chess positions? by Matthew R. Brades, CCC, March 26, 2014 » Chess Maxima
- Position validity by Russell Reagan, CCC, May 04, 2014
2015 ...
- Binary FEN by J. Wesley Cleveland, CCC, July 24, 2015
- Max moves in a position by Laurie Tunnicliffe, CCC, October 22, 2016 » Chess Maxima, Move List
2020 ...
- Canonical Position Representation by Dmitry Shechtman, CCC, April 10, 2020
- On the number of chess positions by John Tromp, CCC, July 09, 2021
- Re: On the number of chess positions by John Tromp, CCC, April 02, 2022
- Re: On the number of chess positions by Peter Österlund, CCC, April 03, 2022 » Retrograde Analysis
External Links
- GitHub - tromp/ChessPositionRanking: Software suite for ranking chess positions and accurately estimating the number of legal chess positions
- Puzzle: Encoding a chess board state throughout a game from Stack Overflow
- Chess Position Trainer by Stefan Renzewitz and Gregory Prentice
- NULP in chess endgames by Kirill Kryukov
References
- ↑ Photo by Arnold T. Rosenberg, Marcel Duchamp playing chess on a sheet of Glass, 1958, see Francis M. Naumann, Bradley Bailey (2009). Marcel Duchamp: The Art of Chess
- ↑ Marcel Duchamp: Chess Master Saint Louis University Museum of Art Saint Louis University : SLU
- ↑ Shirish Chinchalkar (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3
- ↑ Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005
- ↑ Re: Hashing function for board positions post 4 by Jim Gillogly, rgcc, May 12, 1997
- ↑ NULP in chess endgames by Kirill Kryukov