Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2022.2
URN: urn:nbn:de:0030-drops-159721
URL: https://drops.dagstuhl.de/opus/volltexte/2022/15972/
Ambrona, Miguel
A Practical Algorithm for Chess Unwinnability
| pdf-format: |
|
Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games.We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.
BibTeX - Entry
@InProceedings{ambrona:LIPIcs.FUN.2022.2,
author = {Ambrona, Miguel},
title = {{A Practical Algorithm for Chess Unwinnability}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {2:1--2:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15972},
URN = {urn:nbn:de:0030-drops-159721},
doi = {10.4230/LIPIcs.FUN.2022.2},
annote = {Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
| Keywords: | chess, helpmate, unwinnability, timeout, dead position | |
| Seminar: | 11th International Conference on Fun with Algorithms (FUN 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 23.05.2022 | |
| Supplementary Material: | https://github.com/miguel-ambrona/D3-Chess |
