Professor Quiggin at Crooked Timber has introduced a discussion of what President Obama will do after the next senate elections with the title “Zero Dimensional Chess,” which led some of the bigger wankers in the audience to wonder how 0-D Chess could occur, and from there to ponder the deeper details of the mathematics of chess. This got me thinking – I used to study mathematics, a long time ago, and I’m interested in some of its weirder applications – so I went for a brief internet wander, and while pondering the nature of how one would lay out a chess game mathematically, I thought of an amusing quantum mechanics analogy. So, here’s a brief look at what I found, plus my silly analogy.
Chess as Graph Theory
Apparently there is a well-established notion in mathenatics of a Board, which is a finite subset of a lattice of a given size. I think a lattice will be subject to the standard rules of differential geometry in finite spaces – which I was “taught” in 4th year of University by a crazy Noumean chap, but didn’t understand a word of – but it is also subject to all the rules of graph theory, some definitions of which are laid out here. Moves can be described in terms of “tours” or “cycles”, with a tour of length c referred to as a “constant length tour,” and similar definitions for tours of all the squares in the board (commonly defined as Hamiltonian Tours or Cycles). Moves with a fixed length in two dimensions (such as the Knight) are called “Leapers.” So, for example, the night is a (1,2) Leaper.
The mathematics of chess has been used to solve various forms of “Rook Problem,” which is the number of ways of placing k Rooks on a board such that no Rook can take any other Rook, for which closed solutions[1] can be found. But the fundamental problem appears to be the solution of problems called “series-movers” in which the aim is to take all of your opponent’s pieces. Unfortunately, the reference I found that introduces series movers (Kotesovec, 2009) is written in Czech, but for the abstract, so is kind of hard to read. The goal is to find solutions to such problems that are mathematically simple and to represent existing chess problems in terms of them. I’m not sure how “taking” a piece is expressed mathematically. According to Kotesovec, many of these chess problems have proven optimal solutions, but of course we know that ultimately chess problems are solved by path searching (checking all future moves), which implies that there is no optimal solution for most real-life chess situations.
Interestingly, some of the work done on these problems has been done by Donald Knuth, who I think is the chap who invented LateX.
Harvard University used to run a course on Chess and mathematics, which shows a lot of the terminology used and suggests that it relies on little more than specific applications of standard graph theory. The page seems to have the result that the number of solutions to the problem of “Mate in N” is a Fibonacci number, which is kind of surprising.
It seems like the mathematics of chess is well understood and comes down to defining certain types of allowed paths on finite graphs, and using the usual range of graph theoretic methods to solve for optimal paths (the shortest number of moves) and to find algorithms for path finding.
Chess as Quantum Mechanics
Chess consists of a two dimensional space occupied by different kinds of particles (the pieces) that move according to strict physical laws, and are annihilated by anti-particles. There are also some strict rules about the creation of new particles, and a very strict relationship between the amount of movement that can occur and time. It struck me that if you define time in terms of turns, that is as if 1 unit of time were one turn, then you really have a two-dimensional finite geometry, with energy-constrained movement of particles according to strict laws, and a set of rules for whether they can exist in the same space at all (particles of the same type) or annihilate (particles of opposite type). Some particles (the King) exert action-at-a-distance (gravity/anti-gravity) and some may have a wormhole property (knights) and some can predict the future without breaking the energy constraints (pawns taking en passant, and maybe Rooks when castling). If you extend the dimension of the board to include time as a third dimension, then I think you can model chess as a general field theory[2] on a three dimensional space of finite size, with limited gravity, strict energy constraints[3] and complex rules about the creation, destruction and movement of particles. We even have a maximum speed of movement (the maximum number of squares a Queen can move). Of course, all your calculations would have to be done using differential geometry, and you’d probably have to invent some form of dark matter (invisible knights clustered 1000 per square), but it would be an interesting problem for someone with three brains and three lifetimes to waste on utter pointlessness.
Zero-dimensional Chess
Presumably 0D chess occurs on the “null” board ([0]x[0]) so is trivial and uninteresting, but can be defined rigorously, in that all moves are trivial. But I assume that a [0]x[0] board does not have even one point, so no pieces can be placed, preventing the game from occurring.
—
fn1: For the non-mathematical reader, a closed solution is a solution which can be described by a formula rather than an approximation or an algorithm for getting the answer from a computer. Most interesting mathematical problems don’t have a closed solution. This is a very good reason not to do maths, if you value your sanity.
fn2: If I have my terminology right, QFT is the merging of general relativity (which covers gravity) and quantum mechanics (which covers energy and matter).
fn3: By energy constraints here I mean that only one move can occur per unit of time, so only one annihilation per unit of time. I think that mathematically this would act as a boundary constraint on solving Hamiltonian problems; and the finite nature of the space makes me wonder if the many-body-problem could be solved in a chess version of quantum field theory.
October 28, 2010 at 9:54 am
Wankers, indeed. 🙂
October 28, 2010 at 10:02 am
I can only count myself amongst such illustrious crew! No-one could look at my blog and judge me otherwise…
November 9, 2010 at 7:19 am
I’m not at all convinced such explorations are a waste of time. The study of so-called Invisible Chess – where one or both players cannot see all the pieces of the other player (and only learns of their locations when they happen to land a piece on a square already occupied by an invisible piece) – turns out to have application to submarine warfare. We usually don’t know the locations of our enemy’s subs unless those subs surface near an observer or unless our subs happen to encounter them underwater.
November 9, 2010 at 7:27 am
That’s interesting… what is the application of the chess game to this situation? Tactical training?
November 9, 2010 at 8:10 am
No, more strategy development: How do you decide what moves to make (eg, where to put your own pieces/subs), given ignorance as to where all your opponent’s pieces/subs are, and how should you update your strategy as you learn some of their locations. In addition, learning here is not monotonic – in other words, you may learn where a piece/sub is now, but that knowledge may soon become out of date, so it means you may again not know the location of that piece/sub in the future. Most computer models of learning don’t allow for such unlearning.
March 13, 2015 at 6:38 am
DEEP BLUE, IBM’s chess computer is said to have beaten the reigning chess World Champion both in a game, and an entire match. To me, this implies that chess has been more or less figured out mathematically. By looking at the algorithms the program uses, you have a model for measuring the value of various moves, in response to the opponent’s moves.
March 13, 2015 at 12:39 pm
Chess isn’t (to my knowledge) a solved game, which means that a computer can’t tell you the complete list of moves to make from any position (or even any starting position). The best a computer can do is brute force calculate the next X rounds of potential moves and select the optimal choices from them.
This inability to see all the way to the end of the game was what kept humans competitive for so long. I recall reading that a computer could perfectly predict the outcomes for the next 10 or so moves, but a human could roughly predict the results of strategies of 30+ moves. However, it seems that the computer’s ability to perfectly predict the following moves has reached the point that human intuition is outclassed.
Source of some of this info is xkcd:
http://xkcd.com/1002/
http://www.explainxkcd.com/wiki/index.php/1002:_Game_AIs
Reflection on the AI performance and robotics advances is also why I’m going to teach my kids Calvinball, as it’s likely to be the only human dominated pro league by the time their adults. 😛
March 13, 2015 at 1:42 pm
My impression too was that chess is not “solved” per se, just that computers can now think further ahead than humans. But your xkcd graphic suggests that humans can no longer beat computers, so in a practical sense it is “solved.” There are some classes of problems that have no theoretical solution, only the practical one of throwing computer time at the problem, and I guess for these – where you have shown they have no solution – then “we can now afford a computer that beats all humans” is the only allowable definition of “solved,” though it’s a boring one. My brief reading on the theory of chess suggested that some progress has been made towards solving some problems though – maybe the graph theory is just about more efficient ways of thinking ahead.
I’m surprised that checkers has been solved for at least some starting positions. I would have thought the possible options multiply so rapidly in the future that there is no way to solve them. Interesting …
March 14, 2015 at 7:02 pm
I interpreted the checkers solution as being for “For the standard starting position, a computer knows all the branches that should be followed to guarantee a win (or at least a draw”. So starting from any particular point (say half way through a human v human game) may not have a known solution.
March 15, 2015 at 4:33 pm
The wikipedia article on solved games says that Checkers has been “weakly solved”, meaning that from the starting position it can always secure a win or draw against any move by the opponent, provided both players play a perfect game. But it cannot necessarily win against someone who plays a losing move! Apparently this solution required analysing a search space of 10^20 moves, using 50-200 desktop computers, and was only achieved in 2007. It appears that “weakly solving” a game doesn’t necessarily guarantee a machine can always win, and checkers has not been “strongly solved” yet. Chess has only been solved for endgames and it looks like Go is going to remain the exclusive province of human intuition for some time to come …
March 15, 2015 at 6:52 pm
“it looks like Go is going to remain the exclusive province of human intuition for some time to come …”
I’m still sticking to Calvinball and strip poker. [1]
[1] Contingent on escalating series of actions being acceptable bets in strip poker. I’m pretty confident I’ll have a dirtier mind than a computer for a while yet…
March 15, 2015 at 7:22 pm
You know you’ve hit rock bottom when you’re playing strip poker against a computer …