An Analysis of Unwinnable Chess Positions : chess

0
17
An Analysis of Unwinnable Chess Positions : chess


Categorizing Unwinnable Games

Background

Usually, the outcome of a game of chess is clear. There are the various ways to draw, and a player wins by delivering checkmate, or if their opponent resigns or runs out of time. However, there is a nuance to these rules that isn’t often thought about. Specifically, you cannot win a game on time if it would be impossible for you to win over the board.

[I]f a player does not complete the prescribed number of moves in the allotted time, the game is lost by the player. However, the game is drawn, if the position is such that the opponent cannot checkmate the player’s king by any possible series of legal moves

FIDE Law 6.9 (PDF)

This leads to an interesting problem when a player runs out of time. In order to properly adjudicate the outcome of the game, you must first determine whether the opponent of the player that ran out of time could ever possibly deliver checkmate. In some cases, this determination is easy (e.g. if a player only has a king, they cannot possibly deliver checkmate). However, some cases are trickier to determine, which is acknowledged in the Lichess FAQ:

In rare cases this can be difficult to decide automatically (forced lines, fortresses). By default we always side with the player who did not run out of time.

This means that there are occasions when Lichess will award a player a win after their opponent ran out of time, even though there is no series of moves that could lead to checkmate (and it would be a draw under FIDE rules).

Of course, somebody eventually made a project to find all of these games and created the Chess Unwinnability Analyzer (known as CHA):

Our analysis led to identifying a total of 94,858 games that were unfairly classified. Namely, games that were lost by the player who ran out of time, but their opponent could not have checkmated them by any possible sequence of legal moves.

I should note that this is less than 0.003% of all games played on Lichess, so it is not a frequent issue.

Categorizing Unwinnable Games

I was interested in learning more about these unwinnable positions and used the list of games produced by CHA as my starting point. There were 92,693 games when I downloaded the list in July.

Abandoned Games

First, CHA found all games that were won on time despite the winner not being able to checkmate their opponent. However, these include some games where their opponent left the game and it was deemed abandoned by Lichess.

For example, in this game black’s only legal move is to capture white’s queen, which would leave white with no way to ever checkmate black. However, black instead left the game and the win was awarded to white.

In some cases, no side was able to make progress and one side eventually quit rather than continue. E.g this game where a pawn blockade prevented either side from having any meaningful options. After 45 moves of shuffling kings around, black simply gave up on the game and left. There were 7,935 games that were abandoned, despite the abandoning side having no way to lose.

Games by Ply and Possible Outcome

After removing the abandoned games, there were 84,758 unwinnable games remaining. However, this analysis is concerned with categorizing the final position of these games and some of these games had identical final positions. After removing duplicates, there were 67,789 unique unwinnable positions remaining.

The vast majority of these positions had a sequence of moves (either forced or with minimal options) that would lead the side that had not run out of time to be checkmated, stalemated, or end up with insufficient material. I decided to categorize the positions by the possible outcome and maximum ply to reach that situation. An example may make this clearer. In this game, white’s only move when they ran out of time was h5+. Black must move their king in response, at which point it is a stalemate. Thus, the game can last 2 more ply and ends in stalemate.

Some games can end in multiple different ways, all of which are unwinnable for one side. In this game white timed out while black’s king was trapped. If white played Rh5#, they would have won by checkmate. If white played Rxg4, black’s king is freed and they can play Kxg4, however black would have insufficient material to checkmate. If white made another move, black would have been stalemated. Despite the different possible outcomes, any move white would’ve made in this scenario would have made it clear that black could not win.

Max Ply Result Positions Example
0 Insufficient Material 685 Game
0 Stalemate 352 Game
1 Checkmate 1961 Game
1 Checkmate / Insufficient Material 29 Game
1 Checkmate / Stalemate 361 Game
1 Checkmate / Stalemate / Insufficient Material 46 Game
1 Insufficient Material 35601 Game
1 Stalemate 5776 Game
1 Stalemate / Insufficient Material 597 Game
2 Checkmate / Stalemate / Insufficient Material 1 Game
2 Insufficient Material 1 Game
2 Stalemate 1863 Game
3 Checkmate 15 Game
3 Checkmate / Stalemate 9 Game
3 Checkmate / Stalemate / Insufficient Material 1 Game
3 Insufficient Material 3 Game
3 Stalemate 55 Game
3 Stalemate / Insufficient Material 14 Game
4 Stalemate 11 Game
6 Stalemate 3 Game
7 Stalemate 2 Game
8 Stalemate 4 Game
11+ ??? 20399

The strangest results here are definitely the 0-ply stalemates. That is, somebody managed to win the game on time despite the fact that the game should have been already over due to stalemate. It’s always possible that Lichess is not reporting some detail that would make clear why the game was resolved this way, but it certainly looks like a bug (possibly it’s been resolved since the games took place). Similarly, the 0-ply insufficient material results also look like a bug.

Closed Positions and Types of Pawn “Blockades”

Now, there are 20399 remaining positions that can continue at least 11 ply without resulting in checkmate, stalemate or insufficient material. The vast majority of these positions involve blocked pawns forming an impassable wall, such as in this game. It is similar in concept to a [fortress](https://en.wikipedia.org/wiki/Fortress_(chess)) or the pawns could be considered blockaded. Neither term is a perfect fit, since they often are used for situations where a defender chooses a structure that can be held with proper defense, as opposed to these positions where they are completely impassible with any series of moves. Nevertheless, I’ve chosen to refer to positions of this type as a “blockade” for this analysis.

Sets of opposing pawns may combine to build a wall if they are offset from each other in certain ways. This diagram shows the possible offsets for opposing pawns. If a white pawn is added at any of the x’s and a black pawn is added directly in front of it, then they extend a series of squares that are impassable for both kings. If these single opposing pawns continue across the board and constrain both kings to their respective side, I call it a “simple blockade”. There are 8535 possible pawn structures that form a simple blockade, with many times that number of possible positions because the kings may be on different squares. The previously mentioned game in this section is a simple blockade.

Some positions look similar to simple blockades, but don’t quite fit the definition. For example, in this game, the g and h pawns don’t actually form an impassable wall by themselves. If the f pawns were not there, the black king would be able to go to g5, then capture h5. However, if we remove the h-pawns entirely, this would be a simple blockade. Thus, I call it a “simple blockade with extra pawns”.

Finally, among the pawn blockades, there are some more complicated positions. In this game, doubled white pawns on the f-file combine with doubled black pawns on the e-file to build an atypical wall. These however, are still pawn walls.

Category of Pawn Blockade Number of Positions Example
Simple 14141 Game
Simple w/ Extra Pawns 4540 Game
Other Wall 238 Game

Piece Blockades

The previous section discussed blockades with only pawns. However, there are similar positions that include pieces. Generally, there will be an extra bishop that is blocked by pawns on the same color as it, such as in this game.

The same type of walls as above apply

Category of Piece Blockade Number of Positions Example
Simple 1100 Game
Simple w/ Extra Pawns 319 Game
Other Wall 4 Game

I do think this game deserves a special mention for being the only blockade in the list that has a knight on the board.

Non-wall Blockades

This category is similar to pawn blockades in that there are a number of pieces that are permanently immovable. However, it is distinct in that:
1.) The pawns do not form a wall across the entire board and
2.) The king is one of the immobile pieces.

These are positions that would be stalemates, except the side with the trapped king has another piece that can’t do anything effective. The king is stuck in the corner, or 1 square over

Remaining Positions

There are 7 positions that have not yet been addressed.

4 of them are almost blockades, but there is still a pawn move yet to be played, so they don’t fit my code’s definition: 1, 2, 3, 4

1 is a 14-ply stalemate. It looks similar to a non-wall blockade, but white’s bishop is trapped, so stalemate is unavoidable. Logically, there’s nothing special about this compared to the 8-ply stalemates. It just takes a long time to run through all the possibilities when you get up to 14-ply, so I set the limit to 10-ply.

Then finally, we have 2 extremely similar looking positions with identical pawn structures: 1, 2

White is stuck shuffling the king back and forth forever. Black could capture the g2 pawn, but that would instantly lead to stalemate.

Source Code, Disclaimer and Acknowledgments

Source code may be found at my Github. The repository also includes all the positions broken down by ply / outcome as they were in this post, if you’re interested in seeing additional positions.

This project was just a hobby, so don’t expect it to cover 100% of cases or be totally bug free. See licensing for more (Spoiler: It says you can copy and modify it, but makes no guarantees that it is accurate/useful).

Special thanks to:



Source link