Theoretical Chess

This thread is to hold post about chess and its variants as viewed mathematically.
The word "theoretical" here is not to be confused with "theory" as used when discussing the Schools of Chess.
Instead, the word refers to "theory" as it is used by mathematicians.

There are many chess variants - even for standard chess. They do not all have names. This causes an issue at the very start because to apply some mathematical theory to chess one has to be precise about what chess variant you are talking about!

"Standard chess" refers to the many variants of chess that adhere to the FIDE laws of chess, and leaving out Appendix F which describes Chess960.
See: www.fide.com/FIDE/handbook/LawsOfChess.pdf

From that document ...
"The Laws of Chess cannot cover all possible situations that may arise during a game, nor can they regulate all administrative questions. Where cases are not precisely regulated by an Article of the Laws, it should be possible to reach a correct decision by studying analogous situations which are discussed in the Laws. The Laws assume that arbiters have the necessary competence, sound judgement and absolute objectivity. Too detailed a rule might deprive the arbiter of his freedom of judgement and thus prevent him from finding the solution to a problem dictated by fairness, logic and special factors."

There are at least two groups of people that have had issues with the FIDE rules - mathematicians and chess programmers. They have issues for the same reason; the FIDE document is in no way an axiomatic treatment of the rules of chess!

The document is replete with cases of using words and phrases that it defines later, or, worse, does not define at all. Emanual Lasker, a mathematician and WCC, pointed out a flaw in the FIDE rules in existence during his life that allowed games to be infinitely long. Another famous example was the rule for castling that had to be amended when it was pointed out that, according to the rule at the time, it was legal to castle with a Rook that had been promoted from a pawn! Chess programmers, who are not necessarily chess players (!), needed the rules to be precise so that they could program a computer to play by the intended rules.

From that quoted paragraph above from the FIDE rules document, you can see that FIDE has punted the issue to the arbiters at a tournament. The arbiters are suppose to know, from experience, what the intended rules are.

Rule 5.2d (the three position repetition rule) and 5.2e (the 50-move rule) do *not* require that the game be drawn. Both rules say "may be drawn". The draw has to be declared. If not, play continues. However, tournament directors need the games to finish in each round in a timely manner. So FIDE has added new rules that allow arbiters to declare drawn a game that has had a repetition of position 5 times or a game for which the 75-move rule applies (a rule similar to the 50-move rule).

Two other interesting rules concerning draws are these:

Rule 9.1a allows for tournaments in which players cannot agree to a draw; whether in less than a specified number of moves *or at all*, without the consent of the arbiter!

Rule 10.2 allows an arbiter to declare a game a draw on request of a player in the Quickplay Finish phase of a game under certain conditions.

I have no intention to fill the gap by writing an axiomatic treatment of chess. Instead, I'm going to describe the game (or more precisely a collection of games) that follow intended rules and expect the reader to know by experience what I mean.

I'm going to call the main variant of chess "Standard Core Chess" (SCC). The standard game of chess as described in the FIDE document is the intention. For our current purposes, the rules of chess pertaining to serious competition play will be omitted. Those are Articles 6-14 which cover: the chess clock, irregularities, the recording of the moves, procedures for claiming certain drawn games, quickplay finish, the conduct of the players, the role of the arbiter, and resolution of questions through FIDE. Also, Article 4 will be omitted because it covers the act of physically moving the pieces.

I assume that some mechanism is used to keep any chess game from being infinitely long. For concreteness you can assume that a 3-time repetition of position is an automatic draw and that the 50-move rule is also an automatic draw. Both of those are implemented draws on Lichess, for example.

In normal SCC, a win counts as 1 point for the winner, a loss counts as 0 points for the loser, and a draw counts as 1/2 a point each. There will be no other consideration of a "payoff" than these points. For SCC to be "zero-sum", a win would be counted as 1, a loss -1, and draws would count as 0.

There is no consideration of whom is actually playing White/Black. Indeed, from the mathematical point of view the reference to "player" is a convenience of exposition. [Compare with set theory. The first order logical formulas that are the axioms of ZFC do not use the word "set"!] Similarly there is no consideration of the length of time White/Black takes to make a move, the actual physical mechanisms being used to play, or anything else that is irrelevant for a mathematical treatment. Again, I rely on experience to know what is irrelevant.

Every position that occurs in any game of SCC can be evaluated to see if, by the rules, the position is a win/draw/loss or as yet none of those. If it is none of those, then there are a finite positive number of possible moves for the player on the move. Imagine creating a tree where the root node is the initial position. There are then 20 possible moves for White. Create 20 nodes from the root. In each of those positions there are 20 possible moves for Black. Create 20 nodes for those coming from the 20 nodes just made for White. Continue this way. For each position that occurs evaluate it to see if the position is a win/draw/loss. Remember that we are keeping track of the rules for an automatic draw per post #3.

The resulting tree is finite! An obvious algorithm will determine from this tree the following:
- whether SCC is a win or loss for either player with best play, or whether it a draw with best play, and
- a complete record of how a player should play the game to achieve the best result - in particular, a determination of the move a player should make for any position they could face. This record may not be unique but at least one can be chosen while implementing the algorithm.

That complete record is an example of what in game theory is called a "pure strategy", which is basically what a player has chosen to play in any given position. Each player could have figured this out prior to playing and come to the table with a pure strategy for every possible game.

It is unfortunate that this is called a "strategy" because that word has a different meaning in the phrase "mixed strategy" in game theory, and is only marginally related to the word "strategy" in the chess literature.

Note that in this creation of the tree and the strategy, that knowledge of how the opponent has played in the past or will play in the future, or their "style", or how others have played or will ever play is irrelevant. Both players can produce a pure strategy as described above without such knowledge, and indeed from a mathematical point of view that is exactly what they should do. This is not chess in real life; this is mathematics. We can discuss real life chess issues elsewhere.

The tree described above is called a "complete game tree" in game theory. The reference below on Game_tree explains this in more detail and also gives an algorithm for solving a game for which you have a complete game tree.

en.wikipedia.org/wiki/Game_tree
en.wikipedia.org/wiki/Game_theory#Perfect_information_and_imperfect_information
en.wikipedia.org/wiki/Perfect_information
en.wikipedia.org/wiki/Game_theory#Zero-sum_/_non-zero-sum
en.wikipedia.org/wiki/Strictly_determined_game
en.wikipedia.org/wiki/Strategy_(game_theory)#Pure_and_mixed_strategies

In game theory there are multiple ways, formalisms, to describe a game. Examples are the Normal-form and extensive-form. I don't see any benefit to these formalisms for analyzing SCC.

There are also what are called topological games. I don't see any way to map the SCC game tree to a topological game. I also don't see any way to solve SCC using a topological game.

There is also a field of mathematics called Determinacy, which studies games, but these are two-player games of perfect information in which the players make an infinite sequence of moves and there are no draws. SCC does not satisfy those conditions.

en.wikipedia.org/wiki/Determinacy
en.wikipedia.org/wiki/Normal-form_game
en.wikipedia.org/wiki/Extensive-form_game
en.wikipedia.org/wiki/Topological_game

I think that maybe, the sharp distinction between mathematics and real life, can be nuanced.

They are different. And a road map is different from the reality it is meant to describe. A topographical map of the same reality, is also different. Two models that we may use for different purposes in our dealing with the reality that they point to.

So, perhaps, what you are actually, and precisely describing, is that the assumptions underlying the axiomatic building blocks of the currently available game theory, can not be all verified in the case of the reality of the chess games (SCC) that we have recorded and studied.

However, the set of all legal chess games of SCC type can still be described uniquely, past ones, and not yet played ones, even if we can't construct all of them now, or in the future, even if we had to construct another universe just to compute them (that is the only humor, and only a caricature to express the nature of the impossibility, not mathematically impossible, but impossible still). The rules are there, the initial conditions are known. The unique description formalism is actually being used in many type of databases, and is used in the literature, at the base of your other threads. That is empirical data, already recorded about the reality, that some mathematical modelling frameworks could attempt to explain and predict.

Physics is an example of the most direct and reproducible way of using mathematical models to understand the reality that those models have been attached to, via a careful tethering of the models assumptions to the constantly update body of empirical data. Some of that data, and experiments designed to produce the data, even need that the models first be developed for the systems of measurement of the reality to be able to test the validity of the model predictions.

This does not constitute circular logic, only that we humans, when confronted to the complexity of some reality, need some models as frameworks to further understand how parts, previously identified to act in a reproducible manner, and with some possibility of controlling some other parts, and restrict the context of reality to reproducible circonstances.

We need stories, that can be share, so that the work of understand what they describe can be made through cooperation of the many, whether in direct communication, or across generations, through cultural memory, and its propagation.

Existing game theory applied to SCC, to my knowledge, only applies to the complete game tree for SCC. Game theory applied to SCC says what I put in lichess.org/forum/team-jomegas-tabia/theoretical-chess#4.

I see no application to SCC with the complete game tree to the subjects listed in the links in #5
lichess.org/forum/team-jomegas-tabia/theoretical-chess#5

That leaves us in my mind with the question, "Can existing game theory help in analyzing SCC when all one has is a partial game tree (per definition in en.wikipedia.org/wiki/Game_tree).

At the moment, I don't see how game theory can help there. Game theory assume you know what the payoffs are. Either the payoffs for the terminal nodes in the extensive form representation, or in the matrix in the normal form representation. But we don't know that. At best we have a probability we might assign a payoff.

I see that this might be covered in game theory as part of its talk on games with incomplete information.
en.wikipedia.org/wiki/Extensive-form_game#Incomplete_information

Look at that link carefully. They introduce "Nature" to assign the probabilities as a third player and then they say "In the case of private information, every player knows what has been played by nature." Then the example still has the final payoffs (listed on the left and right of the picture).

Indeed, in the formal definition you can see that the payoffs are known; they are specified by the payoff profile function.
en.wikipedia.org/wiki/Extensive-form_game#Formal_definition

The probabilities are then "nature's" choices that determine the actual payoffs applicable per the player's choices. Look back at the simple example they have in the game depicted by the picture under the title section "Incomplete Information" - the payoffs are listed on the left and right of that picture and effectively decided by nature's choice. In that example, nature "played" first. Nature chooses the ability of the job applicant. In the general mathematical model the probabilities are specified and known by the players.

Let's try to apply this to SCC with a partial game tree. To make this incredibly simple, assume we have the limiting case of the empty partial game tree, which means we are only looking at the initial position of chess. "Nature" in the sense of that web page, is choosing the payoffs for the game, but what can nature be choosing? Chess is deterministic.

The only thing I can think of is to pretend that nature chooses the probabilities of the payoffs for the 20 possible White moves. The payoffs can still be taken as the usual (1,0), (0,1) or (1/2,1/2) but now the picture splits into 20 pieces depending on White's first move (in analogy to that picture on that page splitting in 2 depending on player 1's choice of U or D and nature's choice of its first move).

White knows the probabilities and the payoffs. So how does White proceed? I think it is simple. For each of the 20 moves there are probabilities p1, p2, p3 for the above payoffs. White computes a probability-payoff for a move as p1 * 1 + p2 * 0 + p3 * 0.5, orders the moves by the largest of these to the smallest and then picks any move with a largest probability-payoff.

For example if we take the Lichess master database as nature then for 1.e4 we have
p1=0.33, p2 = 0.25, p3=0.42 and the probability-payoff is 0.54. Continuing with the other first choices for White and assuming ones not listed have a probability of 0,0,0 we can choose a move with the largest probability-payoff.

A human or chess program could assign similar probabilities determined in any way they see fit. Typically, this is what a human means when they say they've evaluated their chance of a win/loss/draw in a position. Computers typically give their evaluation of a position not as a list of 3 probabilities for win/loss/draw, but as a real number indicating their assessment of the position on some point-count scale - such as what Stockfish does.

Of course one can extend the above example to SCC with a partial game tree beyond the empty partial game tree. For any partial game tree assume nature is determining the probabilities for win/loss/draw for each parent of a terminal node's moves. Compute what I called the probability-payoff and choose either the maximum or minimum depending on who is on the move. Perform the usual min/max procedure to arrive at the initial position given. This gives you a move to play in that position that maximizes the payoff. However, there is a problem now with the application of the mathematical model to how SCC is actually played by humans and machines.

The problem is that after the move is played from the initial position, the opponent will be responding to a position using a different partial game tree! So will the first player once it is their move again. The new partial game tree will usually be extended to further moves than before and the resulting probability-payoffs may not correspond to the values arrived at before.

I don't see anything in the mathematical model of extensive form games with incomplete information that models this situation.

I have an even more troubling problem with this. Chess is deterministic; we just don't know the answers to all positions. Hence, pretending that "nature" assigns a probability to the moves in a position is basically a wrong use of the model to start with. In the example game on
en.wikipedia.org/wiki/Extensive-form_game#Incomplete_information the job applicant is different each time the game is played. It is assumed that the applicant has either low or high ability with some probability. But an SCC chess game has no such randomness.

It is tempting to think that an SCC chess game with a partial game tree might be modeled by extensive form games with incomplete information because that mathematical model has a probability component and because humans talk about chess using words from probability theory. But humans are using the words in an imprecise manner and are not always talking about probabilities based only on the partial game tree from the position at hand.

At the end of lichess.org/forum/team-jomegas-tabia/theoretical-chess#9 I said
"Typically, this is what a human means when they say they've evaluated their chance of a win/loss/draw in a position. "

That is not quite correct! Humans do not just use the partial game tree to evaluate a terminal node - they use their past experience and theories of chess; theories here in the sense of the ideas expounded by the schools of chess. Indeed, it is not at all unusually for a chess master to take the position at hand and evaluate it using an empty partial game tree; that is they do not look ahead at all! This is mysterious to a novice beginner and that beginner is likely to think that chess masters are looking ahead widely and deeply in a partial game tree. You can find such statements by beginners all over the net. The statements are incorrect.

A chess master, of course, can calculate a partial game tree. For them the tree is almost always skinny and deep. That is each position has only a few moves that they pursue, and that, plus the chess masters vision ability for future positions, makes it possible for them to look far ahead. They also have the experience of having played many games, and they may have theory that they know in general terms - theory such as the idea of a minority attack. Based on all of that, humans evaluate their chances (probability of win/loss/draw) on the terminal nodes in the partial game tree they have constructed.

We end up back in the same place as we were at the end of #9; a payoff can be calculated for the moves in the position at hand. But now we have added something; two things actually - experience and chess theory.

Instead of the cheat, and incorrect application, we used in #9 where we pretended that nature chooses the probabilities of the payoffs for the moves at a terminal node, can we have nature involved in some other way?
Instead of just the partial game tree, can we include the other data a chess master uses - experience and chess theory? Is there a way to now model the situation with the game theory of extensive form games with incomplete information?

I had some hope that the paper from plato.stanford.edu/entries/epistemic-game/ would help, but I still don't see how. Maybe in the references there is something.

From that paper:
"John Harsanyi, for instance, argued that all uncertainty about the structure of the game, that is all possible incompleteness in information, can be reduced to uncertainty about the payoffs (Harsanyi 1967–68). (This was later formalized and proved by Stuart and Hu 2002)."

Interesting result, but the standford paper above never talks about this. Instead it spends its time talking about a) rationality of the opponent and b) other ways to do utility of payoffs (instead of using numbers).

"Rationalizability Principle: A player should always try to interpret her information about the behavior of her opponents assuming that they are not implementing ‘irrational’ strategies."

A well known principle in software engineering and chess. It is best to assume that the coder of the code you are reading is not an idiot. They put that code in for good reason. In chess, you should assume your opponent will make the best move, and is aware of the best plans for both sides.

It seems what I would want is a feedback loop that modifies the probabilities on the next pass once the player deepens the look-ahead.