IMDEA Software

IMDEA initiative

Home > Events > Invited Talks > 2024 > A Practical Algorithm for Chess Unwinnability

Miguel Ambrona

Tuesday, November 5, 2024

11:00am 302-Mountain View and Zoom3 (https://zoom.us/j/3911012202, password:@s3)

Miguel Ambrona, Cryptography Engineer, Input Output Global (IOHK)

A Practical Algorithm for Chess Unwinnability

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 6 billion games), successfully identifying all unfairly classified games in the database.