Discrete Morse theory and chess

Question

There are many mathematical objects that are similar to groups and Cayley graphs of groups but lack homogeneity in some sense. Graphs of webpages with edges corresponding to links are one example. One long-studied example is chess. Some moves have inverses, and others do not. If we create a graph of all positions, it is certainly not homogeneous, and many methods developed for analyzing groups fail miserably (for instance, the graph is finite, so is delta-hyperbolic, but this gives no helpful information).

On the other hand, Morse theory is designed to help one study complex structures by picking out the points of greatest interest, ie the critical points. It has been used in several discrete settings such as video compression to help sort through mounds of intractable data.

My question is, has a version of discrete Morse theory been used to analyze chess? For instance, the critical points would perhaps correspond to positions with a local maximum or minimum number of moves; the absolute minima represent checkmates, the maxima represent positions with a lot of freedom.

Because chess is so well studied, I wonder if this hasn't been studied before. Does anyone know of a reference where Morse-like ideas were used to analyze chess?

Answer 1

The quick answer to your question is no, discrete Morse theory has not been used to study chess moves yet (unless this has been done in some very obscure journal). I would like to highlight a few likely reasons for this current state of affairs.

If I understand your question correctly, you are interested in the following scheme:

1. build a directed graph $G$ whose vertices correspond to positions on the chessboard with an edge $a \to b$ if a valid move takes you from $a$ to $b$,

2. construct a discrete Morse function on $G$ whose discrete vector field is only allowed to pair those $a$ and $b$ which are related by bidirectional (i.e., invertible) arrows $a \leftrightarrow b$.

The basic problem with such an approach, simply put, is that $G$ is huge and might contain positions which have not been reached in the entire recorded history of the game. As such, there is no complete "input space" $G$ on which you could impose your discrete Morse function, even if the process of imposing such a function could be performed in a distributed way. By contrast, even the example you have given regarding video compression assumes that the entire uncompressed video is accessible in the first place.

Note also that there is no known method for declaring that such-and-such cells will be critical when imposing a discrete Morse function. The discrete vector field must be acyclic, and depending on the topology of $G$ one might end up with many more critical cells than the "absolute maxima and minima" which were originally intended.

Finally, the following statement from your question is somewhat ambiguous:

Morse theory is designed to help one study complex structures by picking out the points of greatest interest, ie the critical points.

While it is certainly true that a discrete Morse function $f$ on a given cell complex $X$ allows one to construct a homotopy-equivalent Morse complex $M_f(X)$ built out of the critical cells of $f$, all the attaching map information is computed using the non-critical cells. Once you compute these attaching maps you can throw away those uncritical cells, but you must know all of them to begin with.

I think the idea is interesting, and may bear fruit if one restricts from the hopelessly unknown $G$ with "all possible positions" to the much more tractable $G' \subset G$ which is the subgraph spanned by all positions attained by grandmasters in recorded championship games.