Can you say "Combinatorial Game Theory"?

A very interesting academic paper was written several years ago by National Master Dr. Noam Elkies, a Professor of Mathematics at Harvard University (world-class problemist). For those in math and computer science, "combinatorics" is known as an esoteric subject dealing with probabilistic counting, graphology and set theory.  Not straightforward by any means!

Elkies wrote a paper titled, "On Numbers and Endgames: Combinatorial Game Theory in Chess Endgames," which attempts to dissect endgames in combinatorial problems, or combinatorial game theory (CGT). He focuses primarily on positions where "mutual zugzwang" is possible, but does so by looking at the chess board in subgames. He writes,

"To find interesting CGT aspects of chess we look to the endgame. With most or all of the long-range pieces no longer on the board, there is enough room for a decomposition into several independent subgames. Also, it is easier to construct mutual Zugzwang positions in the endgame because there are fewer pieces that could make neutral moves; indeed it is only in the endgame that mutual Zugzwang ever occurs in actual play. If a mutual Zugzwang is sufficiently localized on the chessboard, one may add a configuration of opposing pawns that must eventually black each other, and the first player who has no move on that configuration loses the Zugzwang."

Mutual zugzwang has been presented at this site by
IM-elect Stephen Muhammad, but this novel way of counting may have application in a actual play. Many players learn counting methods and use geometric guides for endgame play. While this paper may not be readable to all, the examples are certainly understandable and instructive. Take the following position:

Elkies states, 

"The kingside is an instance of the mutual Zugzwang known in chess literature as the "trébuchet": once either White or Black runs out of pawns moves, he must move his king, losing the g-pawn and the game. Clearly White has one free pawn move on the e-file, and Black has two on the a-file, provided he does not rashly push his pawn two squares on the first move. Finally, the c-file gives White four free moves (the maximum on a single file), again provided Pc2 moves only one square at a time. Thus the value of Diagram 1 is 1-2+4=3, and White wins with at least two free moves to spare regardless of who moves first".

Interesting concept! There are many more throughout the paper including the one below. Can you find the winning move for white?

Note: Adobe Acrobat is needed to read Dr. Elkies paper. You may try opening the document from the link below, but if you get  a message "internal error occurred," right click on the link below and save it to your hard drive and open from there. The error has to do with the picture formatting within the browser.

Noam Elkies' "On Numbers and Endgames: Combinatorial Game Theory in Chess Endgames,"
Games of No Chance, Volume 29, 1996.

Noam Elkies website


See solution here.

Posted by The Chess Drum: 15 February 2004