Convergent board positions in chess
January 11, 2015 2:41 PM Subscribe
How many common convergent board positions are there? What are they? What's their distribution across a game length spectrum? If end-game results are available, is there are correlation between the state-history and the outcome?
While reading Nick Bostrom's book Superintelligence, I came across the passage, "In any realm significantly more complicated than a game of tic-tac-toe, there are far too many possible states (and state-histories) for exhaustive enumeration to be feasible."
I'm curious not about the computational explosion, but the idea of similar states with different state-histories as it applies to chess. For example, both players advancing their king pawn two spaces, or both players advancing their king pawn one space each for two turns.
What I want to know: How many common convergent board positions are there? What are they? What's their distribution across a game length spectrum? (Probably clustered at the beginning for opening scenarios and at the end for common checkmates?) If end-game results are available, is there are correlation between the state-history and the outcome? (While on one hand it seems that similar board positions have identical decision trees downstream, they also have different processes as inputs, which might be useful for a sufficiently good player to extrapolate to future moves.)
While reading Nick Bostrom's book Superintelligence, I came across the passage, "In any realm significantly more complicated than a game of tic-tac-toe, there are far too many possible states (and state-histories) for exhaustive enumeration to be feasible."
I'm curious not about the computational explosion, but the idea of similar states with different state-histories as it applies to chess. For example, both players advancing their king pawn two spaces, or both players advancing their king pawn one space each for two turns.
What I want to know: How many common convergent board positions are there? What are they? What's their distribution across a game length spectrum? (Probably clustered at the beginning for opening scenarios and at the end for common checkmates?) If end-game results are available, is there are correlation between the state-history and the outcome? (While on one hand it seems that similar board positions have identical decision trees downstream, they also have different processes as inputs, which might be useful for a sufficiently good player to extrapolate to future moves.)
Best answer: Because there are many fewer pieces on the board in an endgame, it's much more likely to have convergence there. For example, I'm sure you will find many identical King + Rook + Pawn vs King + Rook positions when searching through a large corpus (the database I use has 6 million games).
The most extreme common case of convergence I can think of in the openings is this one, which can easily be reached from the Caro-Kann, the Queen's Gambit Accepted, and the Semi-Tarrasch, all of which start very differently.
Of course, any time that players repeat moves in a game (say, by checking back and forth), they've reached the same state twice with different state-histories (unless you count being one step closer to being able to claim a draw by repetition as a change in the state, which is perfectly arguable).
posted by dfan at 6:03 PM on January 11, 2015
The most extreme common case of convergence I can think of in the openings is this one, which can easily be reached from the Caro-Kann, the Queen's Gambit Accepted, and the Semi-Tarrasch, all of which start very differently.
Of course, any time that players repeat moves in a game (say, by checking back and forth), they've reached the same state twice with different state-histories (unless you count being one step closer to being able to claim a draw by repetition as a change in the state, which is perfectly arguable).
posted by dfan at 6:03 PM on January 11, 2015
I don't know if this helps answer "how many," but this is known as transposition when it happens in the opening.
posted by DevilsAdvocate at 3:52 AM on January 12, 2015
posted by DevilsAdvocate at 3:52 AM on January 12, 2015
Best answer: Yes, transposition is the word you're looking for. Reading about pretty much any opening like, say, the Nimzo-Indian Defense, you will come across lines like:
"Black's delay in committing to a pawn structure makes the Nimzo-Indian (sometimes colloquially referred to as the "Nimzo") a very flexible defence to 1.d4. It can also transpose into lines of the Queen's Gambit or Queen's Indian Defence."
Because of the way non-pawn pieces can circle back around and return to their starting positions, there are an almost unlimited number of ways any given position can be achieved (not literally innumerable because of the threefold repetition rule). Of course, most of these are far from "common," but it's all going to rest on where you draw the line of common.
In fact, the threefold repetition rule is a good line of approach on this topic. It's rarely invoked, but is needed often enough to be considered a vital part of the game rules. If you look at any game where it was invoked (and there are some good examples right there in the wikipedia article), you will find positions that came up at least three times in the same game with different move histories. Of course, I suppose one could argue that the positions aren't strictly the same simply because the repetition count has been incremented...
In terms of common convergent positions, my gut feeling is that the vast majority of them are going to be in the endgame. There are many "standard" checkmates and draws depending on remaining material, and many extremely different game histories can lead to identical final positions, like this one. In fact, it is telling that many chess computers now include exhaustive position databases for many endgame configurations.
posted by 256 at 6:36 AM on January 12, 2015
"Black's delay in committing to a pawn structure makes the Nimzo-Indian (sometimes colloquially referred to as the "Nimzo") a very flexible defence to 1.d4. It can also transpose into lines of the Queen's Gambit or Queen's Indian Defence."
Because of the way non-pawn pieces can circle back around and return to their starting positions, there are an almost unlimited number of ways any given position can be achieved (not literally innumerable because of the threefold repetition rule). Of course, most of these are far from "common," but it's all going to rest on where you draw the line of common.
In fact, the threefold repetition rule is a good line of approach on this topic. It's rarely invoked, but is needed often enough to be considered a vital part of the game rules. If you look at any game where it was invoked (and there are some good examples right there in the wikipedia article), you will find positions that came up at least three times in the same game with different move histories. Of course, I suppose one could argue that the positions aren't strictly the same simply because the repetition count has been incremented...
In terms of common convergent positions, my gut feeling is that the vast majority of them are going to be in the endgame. There are many "standard" checkmates and draws depending on remaining material, and many extremely different game histories can lead to identical final positions, like this one. In fact, it is telling that many chess computers now include exhaustive position databases for many endgame configurations.
posted by 256 at 6:36 AM on January 12, 2015
I agree that endgames and early openings are going to have the most convergent positions. As people said above, expert players know some of the most common transpositions that can be reached from different move orders in the opening. In the endgame, you get variations on pretty simple (piece-wise) themes like king/rook/pawns vs. king/rook/pawns. Again, good players study endgames and work towards manipulating things towards a known favorable setup with the common goal of queening a pawn first, then checkmate or resignation by the opponent.
The middle game is where there are so many different positions that you just give up and study more general things like tactics and pawn structures.
posted by freecellwizard at 8:46 AM on January 12, 2015
The middle game is where there are so many different positions that you just give up and study more general things like tactics and pawn structures.
posted by freecellwizard at 8:46 AM on January 12, 2015
This thread is closed to new comments.
posted by hoist with his own pet aardvark at 4:51 PM on January 11, 2015