Chess and Incompleteness
February 5, 2021
Chess and Logic #
Chess and Logic, huh?
There’s something fundamental linking them, and I’m not talking about using logic to beat a game of chess. The rules of chess are similar to the axioms of a logical system. This got me thinking, can we demonstrate Kurt Gödel’s incompleteness theorem in chess?
If you’re not familiar (and it’s a large and difficult territory should you decide to venture there), the incompleteness theorem says that “logic systems can describe true statements that can not be derived using that system”.
I decided I wanted to try, so let’s get to it!
On Completeness and Consistency #
Completeness and consistency are at the heart of the incompleteness theorem, which concludes there can not be an axiomatic system of logic that is both complete (the system can derive every statement that is true) and consistent (the system can derive false statements).
Or rather, by fixing consistent in place we’d say “Any consistent formal logic is incomplete”. Meaning, broadly, if you have a set of logical rules there will be statements of that logic that are true but that you can’t get to using only those rules.
We fix consistent because consistency is a necessity in logic, completeness is just a nice to have. If I offer you a system in which I can prove 1 + 1 = 2, you might be with me so far. But if I follow up with a proof that 1 + 1 also equals 3, it’s over before we even start looking into completeness.
Chess #
I think Chess is like a system of logic, so let’s play with it a little. There are rules. We can exhaustively enumerate those rules (but we won’t, we’ll just give some examples).
Let’s focus on pawns.
- Pawns can move ahead by one or two squares on their first move.
- On any move after their first, and except when attacking, pawns can only move ahead by one square.
- Attacking (consuming) an enemy piece is only allowed through moving diagonally forward by one square.
- An attack is allowed if the opposing pawn has just exercised its right in its first move to move two squares instead of one and your pawn would otherwise normally be able to attack if the opposing pawn had only moved ahead one square instead of two. (This is the only example of an attack in chess where an opposing piece can be consumed by moving to a square it does not occupy. It is a rule that surprises new chess players and leads to accusations of cheating, but it is a real rule and it is called En Passant- French for “in passing”)
- Finally, if a pawn reaches the opposite side of the board it can be turned into any piece (usually a queen) except the king.
Now you can see why I am not going to attempt to list all the rules of all the pieces, it would be very time consuming. And we can all agree there are in fact rules of chess laid out elsewhere. The point isn’t what those rules are, it’s what we can do with them.
Experienced chess players will likely agree a game of chess can be a fascinating expression of decisions. Indeed, observing some of the games of the grandmasters like Magnus Carlsen can put your jaw on the floor. They’re like works of art, beautiful landscapes or orchestral symphonies in their own way.
These rules are analogous to the rules of oh, let’s take algebra. There’s addition, subtraction, multiplication, and division. There are rules about associativity, commutativity, etc.
So if we can agree that the rules of chess are analogous to an axiomatic logical system what can we do with that? Can we demonstrate the incompleteness theorem in chess?
I think we can. I think it might not even be that hard. We can at least try. All we have to do is wrap our heads around completeness and consistency in the rules of chess. But before we do that, let’s discuss the chess analogue of true and false statements in logic.
Valid Chessboard Configurations #
What is a valid board configuration? One that doesn’t violate any of the rules? Given a random chess board with pieces in various positions it can be hard to tell if that state was achieved by starting with neat rows of pieces in their legal starting position and by following the rules, or if they were just chaotically and randomly placed there. Furthermore, there’s not a good way to say a given board is in violation of any of the rules if the rules primarily concern themselves with transitions between board states. That is, the rules are mostly about moves. But luckily for us, there are rules we can use to immediately detect an invalid board configuration, such as that each player should not have more than one king. A pawn can not become a king by reaching the end of the board. So you could easily tell a board had been arrived at illegally if there were more than two kings on it.
Completeness in Chess #
Completeness in a logic system means that every truthful expression can be derived using the logical system. What does completeness in chess mean? Logic concerns itself with truth, chess concerns itself with winning chess. That is to say achieving checkmate. Could completeness in chess mean that every checkmate can be derived using the rules of chess? That sounds vaguely promising. We can probably be more general, though. Let’s try completeness in chess means every valid board configuration can be derived using the rules.
Consistency in Chess #
Consistency in a logic system means that no false expressions can be derived using the logical system. What does consistency in chess mean? I’d say it means something like “you can’t get to an invalid board state by playing by the rules”. That sounds promising. Chess is a consistent system if by following the rules you don’t end up with a board configuration that is illegal. It is consistent if by following the rules you never end up with more than 2 kings on the board.
Similar to how we can derive the fundamental theorem of algebra, we can play a game of chess and end in a valid configuration of the board (and also checkmate).
We can also play a game of chess and walk away from it having followed all the rules but before anyone achieves checkmate. We don’t even have to call it a draw, we can just mutually agree to walk away and pretend it never happened. The configuration of the board at that point is still legally derived, even if somewhat uninteresting compared to a game that concluded in a checkmate.
This is similar to a mathematical proof which stops before reaching an interesting statement. You have followed all the rules to an unsatisfying end. You let us all down. You should be ashamed. Why have you done this?
Is Chess Complete? #
A critical element of the incompleteness theorem is self reference, or Hofstadter’s strange loops. Kurt Gödel derived a statement in a logic system that said of itself “I am not derivable”. But it was just derived! If the statement was true, then there is a true statement that cannot be derived (ignoring the fact we clearly just derived it) by the system therefore the system cannot be complete. If the statement was false, then there is a false statement derived by the system, therefore the system could not be consistent.
Kurt Gödel proved in a formal logical system something about formal logical systems involving proofs. This is meta, and indeed his proof was meta too. He used a formal logical system to make a statement about the formal logical system which was inconsistent with itself while being a totally valid expression of the system.
This would be like arriving at a checkmate in chess after only following the rules in which a paradoxical statement about chess was expressed. That is to say, where each of the pieces had a word printed on them and when played a certain way, the outcome is simultaneously a valid checkmate but also the words on the pieces spell out “I am a board configuration that can not be arrived at by following the rules of chess”.
Paradox time #
If that sentence is true, then the game we just legally played was actually arrived at illegally (even if we’re doubly sure we followed the rules). This game of chess says that there are valid board configurations in chess that can not be arrived at legally, and therefore chess is incomplete.
If that sentence is false, then we just played a legal game that resulted in a statement about chess that is not true and therefore chess is inconsistent.
Chess can therefore not be complete if it is consistent, and it can not be consistent if it is complete.
In order to verify this, are there valid configurations of chess boards that can not be achieved by following the rules? Certainly. Put all 32 normal starting pieces in the lower half of the board, alternating in color. There is no way to get into that state following the rules, but nothing about that state is in violation of any rules and is therefore valid.
Conclusion #
The incompleteness theorem is a brilliant and agile attack on formal logical systems and it brought numerous prominent mathematicians of the period to their knees, in particular Bertrand Russell and his efforts in producing the Principia Mathematica which is probably for the best since it takes hundreds of pages of dense symbols to arrive at the conclusion that 1 + 1 = 2.
Chess is not unlike a formalized logic. It has rules, and those rules can be used to carry the weight of ideas. Including ideas about those rules.
This post was in part inspired by this post which goes much deeper, provides more history and more details while taking the angle of actually implementing Gödel’s arithmetic in Lisp.