Has anyone attempted to characterize chess mathematically?

Question

From years of being student, researcher, and practitioner of chess, I feel like it possesses completeness and elegance that are found in mathematical proofs and theories. Thus, it seems only natural to imagine that it should be possible to describe chess in mathematical terms. By that I mean an elegant description, like a compact set of formulas or a proof that chess belongs to such and such field of mathematics. Intuitively, it feels like it should be able to fit in group theory. Does anyone know what attempts have been made in this regard? I would like to specifically exclude engines, neural networks, and the like from the discussion because, despite the obvious success in increasing the quality of play, those attempts do not constitute theoretical proof.

Answer 1

There are many different aspects of chess which can be formalized mathematically. Since the 19th century at least, chess has been mined as a resource to drive mathematical innovation. So when talking about a mathematical characterization of chess, it's not a single modeling that we are talking about, which grabs every feature, but rather a number of models, in which the power of each is paradoxically in the letting go of some aspect of chess which is not relevant for that analysis.

• Perhaps the earliest success (not counting the counting :-) of grains of rice on a chessboard) was Zermelo's Theorem (yes by one of the founders of ZF Set Theory) which states that in chess "either White can force a win, or Black can force a win, or both sides can force at least a draw".

• Combinatorial Game Theory (developed by celebrated mathematicians John H. Conway, Elwyn Berlekamp and Richard Guy) has been successfully applied to chess. A couple of assumptions in this theory go against its general applicability to chess though. One is that a win in CGT is solely if your opponent can’t move which does not address stalemate. Secondly there is the notion of “entailing move” (e.g. check) where if one person plays, the other player must respond rather than the first player playing again. But Noam Elkies has derived some non-trivial results in chess endgames by computing their CGT value - references given in his chess page http://www.math.harvard.edu/~elkies/chess.html: "On Numbers and Endgames" and "Higher Nimbers [sic] in Pawn Endgames on Large Chessboards".

• You mentioned group theory - well curiously the set of combinatorial games under composition does form an abelian group! To be fair, the two obstacles mentioned above do prevent chess itself from behaving in this way.

• There is a massive amount of combinatorial work which has been done around the chessboard. Vaclav Kotesovec has published online an 800 page book just on the subject of non-attacking chess pieces (generalizing the 8 queens problem massively). See http://www.kotesovec.cz/ for the link. This is related to Magic Squares, Experimental Design, etc.

• There is also, starting in Finland with Eero Bonsdorff, a long lineage in path enumeration chess problems, counting the number of ways that a position can be reached. This often involves the analysis of Standard Young Tableaux, which also underpin representation theory of symmetric groups. Fibonacci numbers, Catalan numbers and Euler numbers are all frequently found here, together with other combinatorial identities whose realization can be found lurking in ingenious chess compositions. See https://pdb.dieschwalbe.de/search.jsp, and type g='mathematics' in the search box.

• The Knight's Tour problem is also famous for helping to push the study of Hamiltonian graphs, and particularly the challenge of counting the number of such objects. See https://www.mayhematics.com/t/t.htm.

• The theory of computation also asks about the complexity of chess. Generalizations of chess to larger nxn boards are for example EXPTIME-complete: A. S. Fraenkel and D. Lichtenstein, "Computing a perfect strategy for nxn chess requires time exponential in n", Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.

• Determination of legality & dead position are both PSPACE-complete on nxn boards: Josh Brunner, Erik D. Demaine, Dylan Hendrickson, Julian Wellman "Even Cooperative Chess is Hard", arXiv:2010.09271v1 [cs.CC] 19 Oct 2020

• Full axiomatization of generalized chess I think there is also research value in a mathematical description of how chess conventions apply consistently to chess problems including fairy chess. Guus Rol has a very ambitious program which reduces each turn to “micro-phases” and claims to be able to determine with great accuracy how fairy conditions interact in complex “retro-active” situations, where both retro and forward logic is necessary. I don’t know if he will ever complete his theory.

• Limited axiomatization: I personally would like to see a more modest theory, which treats each move as atomic and although it doesn’t cover fairy chess so well, at least can cover retro-active aspects of problem conventions such as castling and e.p. Even that has not been done yet.

• The mathematical physicist Roger Penrose published a chess position about 2 years ago which was intended to argue his long-held position that there is a fundamentally different kind of reasoning displayed by humans than an AI grounded in computable functions can demonstrate. See https://en.chessbase.com/post/a-chess-problem-holds-the-key-to-human-consciousness

• Even though the theory of random graphs, and Monte Carlo analysis has been applied very successfully to engines, particularly the most recent generation, I don't think this disqualifies it from being considered a mathematical theory.

• There is also a linear algebra approach to counting moves and positions. “If chess is a graph, what is its maximum eigenvalue?” is a very real and interesting question. See Francois Labelle's site at http://wismuth.com/chess/statistics-games.html

• Linear algebra can be applied successfully to other chess-related questions e.g. how many ways are there for a rook to move from a1 to h8 in exactly n moves? How about a king?

• For many years, the well-known mathematicians and chess problemists, Noam Elkies & Richard Stanley, have been collaborating on a book on chess and mathematics. I don't know when it will finally emerge, or whether they have given up on this. But "The Mathematical Knight" given on Noam's chess page linked earlier perhaps gives a foretaste of that book. Richard Stanley is one of the leading lights in Combinatorics: see http://www-math.mit.edu/~rstan/chess/queue.pdf, and Noam's birthday article https://arxiv.org/pdf/math/0508645.pdf

• There is also perhaps a role for some kind of "probabilistic mechanics" or some such, to explain large-scale behaviours in tablebases. Why, for example, does there not appear to be an increase in the maximum length of winning lines when one scales from 7 pieces to 8 in the board?

A few books

• There is also already a book "Mathematics and Chess" by Miodrag S. Petkovic, reprinted by Dover, that if you can excuse the typos contains a raft of different math puzzles inspired by chess. Particularly I liked the geometrical ones, many of which were new to me.

• A comment below mentioned "Games & Mathematics" by David Wells, which gives chess as an example of an abstract game, and also devotes a chapter to how chess is not mathematics.

• Another excellent Dover reprint is the late John Beasley's "The Mathematics of Games", which chess examples throughout. He was an endgame theorist involved with early tablebases, but had a sense of whimsy which led to many other problems. Particularly Chapter 10 "When the counting has to stop" examines what makes chess hard, to play and to analyze with mathematics.

Other links

Some of these ideas are listed in a Wikipedia page: https://en.wikipedia.org/wiki/Category:Mathematical_chess_problems, and there's a more specific page https://en.wikipedia.org/wiki/Mathematical_chess_problem.

If anyone else has other examples of chess and mathematics, please mention them in comments and I will try to incorporate them in this response. If anyone has links that illustrate the topics I am mentioning, please add them, thanks.

Finally: math.stackexchange.com has 1300 entries related to chess!?!

Answer 2

Here are some starting spots in reading up on Game theory which is the mathematical tool that would be most appropriate for making claims about chess.

This is a light history of early game theory. Chess is a "perfect information game" and there are some interesting things one can claim about this category of games. See this for example. I would also read up on Claude Shannon. Shannon's number gives a bound on game complexity tree. For standard chess we have an intractable puzzle but you could make a smaller variants and solve these smaller games. Here's an example of this. The authors claim to have solved a smaller 5x5 variant of chess.

Answer 3

Not really. At least not serious mathematicians.

It is covered somewhat in Game Theory but other approaches like Group Theory do not seem to fit; although there might some higher dimensional non-linearish type description that could be found.

So Algebra which includes Groups, and Topology too, seem to be out but perhaps it could fit in Analysis if somebody cared enough to try it. But that would an advanced mathematician who would be more likely to attempt a better problem that would lead to their PhD and a job teaching.

Answer 4

The rules of chess are very mathematical already. All pieces move in a very strict way and all the rules are totally deterministic. The board itself is 8x8. Black and white squares mathematically do not have any particular meaning.

Can you model chess rules using group theory? Certainly. But, it would be quite some task to define anything useful out of it. Can you model chess using language theory? Again, sure, matrix theory, state machine, graph theory...? Absolutely. It might be even fun to do that. There is nothing in particular that makes all these modeling impossible or weird.

However, these would not be able to play chess really, only move figures around in a correct manner.

And that is not what chess is about. At the moment, we are really trying to minimize the memory that is consumed by one recorded position and then using various heuristics(, because that is what playing chess is: it is a heuristic science, and it is unlikely that we will ever be able to make it anything more than that), we are trying to calculate the next best move either in our heads or using computer.

So the best possible mathematical description of chess, with the purpose of playing it well, at the moment is a set of heuristic algorithms for deciding the next best move. Beyond that is just a pure compactification problem of describing a position with the least possible amount of memory.

There is an area of describing chess using machine learning algorithms, but this is nothing more than trying various heuristics and using raw computer power to decide which are playing better chess. You just apply all known statistical methods and try to fit a winning strategy with some of them. Nothing really smart about artificial intelligence. That is why it is called artificial. ;)

Answer 5

I'd like to add some reflections to the answers. First, we probably have to distinguish how chess is played by a chessplayer, computer, or mathematician. The main point here is that these three may use different criteria when making moves. The mathematician tries to optimize his or her game in general while a chessplayer or neural network may use local criteria. In its turn, the chessplayer may wish to make the game interesting rather than just to win. Thus, analyzing the criteria, we may apply mathematics that includes not only the pure optimization but also symmetries, i.e. group theory. To my mind, mathematics is more about such kind of beauty and that's why it can be applied to chess in a non-trivial way.

Now, I'll try to describe mathematically one of the "symmetrical" criteria which is well-known for a chessplayer (though I'm not a professional player). At the beginning of the game, white has 20 moves, and one could not use all of them according to his or her preferences. But it seems rather natural that the number of moves satisfying some strategy decreases in time. Thus, if two players built the decision tree they would find out that the outdegrees of vertices become smaller and smaller. Thus, the player may wish to terminate the game finding such a move that leads to a path, that is a part of the decision tree s.t. each its vertex is followed exactly by one vertex. This corresponds to the situation when two players both don't know the result and it's the game that shows it in a clear way. To generalize the task, one may wish to find the moves that lead to an abstract subgraph of the decision tree (say, with a well-known group of symmetries).

P.S. Yet another way to think how group theory can be applied in chess is to note that the moves of K, Q, R, B, N form natural groups with at most 4 generators.

Answer 6

As an applied mathematician, I feel that mathematics very seldom solves any problem in a practical sense, apart from those that reduce to some form of counting. There are many problems that lead to differential equations, for example, that present points of interest in their own right, but to apply them to any real engineering situation assumptions must be made that can never be completely reliable. An engineer must understand both their power and their limitations.

The relationship that exists is that some aspect of a "real world" problem may have an interesting abstract structure and if this captures the interest of enough people it becomes part of mathematics. It goes in directions determined by the possibilities for rigorous thought. After a while it no longer matters if there is any visible connection to the origin.

In the case of chess, there are a very few abstract aspects with practical value, mostly to do with Pawn endgames. Rigorous statements like "either somebody should win or it's a draw" are too general to be useful and are not really interesting either. Useful statements would apply to specific positions and there are too great a diversity of these for any "mathematical" statement to apply to all of them. A strong player sees the exceptions to the rule

Answer 7

Anyone looked at the mathematics behind alpha-zero describing chess completely even without having a engine. One might see the engine implementations as measure instruments for such mathematical model of chess.

It does consider a big space that is bound to contain the solutions, which is far from from assuming impractical complete tree knowledge as in most game theory about chess (that i am aware of).

It handles uncertainty, in the approximation process. Allowing access to the solution via approximation (at least in theory). We just have to be confortable with asymptotic behavior perhaps.

It also use probability spaces in order to be compatible with the type of data coming in from its measurements (RL). I would say, as long as you included the data relationship with the model, you might have something of a mathematical characterization, be it of statistical nature.

Answer 8

I'd hate to say it, but mathematically speaking chess as we play it is very boring. It is a perfect information game, without any non-determinism, for two alternating players. This means that chess is either a win for white, a win for black, or a draw. The optimal strategy for chess is trivial and known: minimax. As far as maths is concerned, chess is solved.

Answer 9

Chess isn't the sort of object that mathematicians are interested in studying. Mathematicians care about problems that are in some way infinite: either infinite objects or finite objects of which there are infinitely many examples. Chess is completely finite. There is only one chess, it uses a finite board, there are finitely many possible positions. If chess is played rationally (and we can't hope to characterize it without that assumption) then games are finite in length. "Rational" basically means that either player will claim a draw as soon as they have the right to, and that means that games are less than about 5900 moves, which means there are only finitely many games. A mathematician might study the prime numbers, but they're not going to study the single number 1827368429.

To a mathematician, "solve chess" is just a calculation, and mathematicians aren't interested in calculations. The fact that it's a culturally important calculation might encourage somebody to try, but it's hard to see anybody having the time to do something so complicated. It's the sort of thing that would take decades of full-time work and, if you failed, you'd have basically nothing.