Theoretical Chess

There are some important things to understand about the formalism/terminology used in game theory. Before that I want to introduce some way to talk about the complete game tree of SCC and I'm going to give an explicit model of the game of SCC.

Because we are keeping track of when a position reached in a game of SCC would be an automatic draw, the FEN notation is not sufficient for representing a position. The standard for FEN is here
en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notation

While the "halfmove clock" value in FEN keeps track of the information needed for the 50-move draw rule, the information needed to determine the 3-time repetition rule automatic draw is too complex for a short notation such as FEN.

If the 3-time repetition rule can be ignored then I'll use FEN. Otherwise the simplest solution is to use the game moves themselves to give a "signature" for the position.

The initial position will have an empty move list. If this would be confusing I'll refer to the initial position of SCC as V0.
This is the root node, the root of the game tree, and is denoted v^0 and v_0 in the formalism in these references:
en.wikipedia.org/wiki/Extensive-form_game#Formal_definition
plato.stanford.edu/entries/epistemic-game/#ExtGamBasDef

Hence, the FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 0 1 , is V0.

The position
1.Nf3 Nf6 2.Ng1 Ng8 3.Nf3 Nf6 4.Ng1 Ng8
is a draw automatically by the 3-time repetition rule.
It's FEN is rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w - - 8 5. But we cannot tell from this FEN that we have a draw. Indeed the following position
1.Nf3 Nf6 2.Nd4 Ng8 3.Nf3 Nf6 4.Ng1 Ng8
has the same FEN and is not an automatic draw.

The position 1.f4 d5 2.g4 Qh4#, which I'll denote FM (Fool's Mate), is an example of a terminal node in the complete game tree for SCC. Both players being what game theory calls "rational", can determine that FM is a win for Black and hence it has a payoff of (0,1).

In both the links above the formalism names the set of all terminal nodes. To be more descriptive in my notation I'll use the following:

- V0. The root node. The initial position of SCC.
- Moves. The set of move designations of SCC. Not all moves are applicable to all positions. The standard short algebraic notation (SAN) for chess moves will be used.
- Nodes. The set of positions (nodes) in the complete game tree. [Technically, the function moves, and sets Nodes and DecisionNodes would be defined recursively; another consequence of allowing the 3-time repetition rule.]
- Terminal. The set of terminal positions. We can determine if a position in SCC is a terminal position. FM is an example of a terminal node. A node is terminal iff it is checkmate or a draw.
- DecisionNodes. The set Nodes\Terminal; i.e. the positions that are not terminal.
- moves: DecisionNodes -> PowerSet(Moves). moves is a function that takes as argument a decision node and returns a set of the moves. Those moves are the allowed moves from that decision node per the rules of SCC.
- Successor(n1,n2). Successor is a relation induced on DecisionNodes x Nodes by the possible moves. That is, n2 is a successor of n1 if there is a move that produces n2 from n1.
- TransClosure. TransClosure is the transitive closure of the Successor relation.
- There are two players. White and Black, denoted 1 and 2. The set of the players is N = {1, 2}.
- turn: DecisionNodes -> N. A function that returns the player for any decision node. Given what we have done this function can be computed from the position.
- utility_n: Terminal -> Real_numbers. For n=1,2 a function that returns a real number given a terminal node. In game theory this is called the "utility" function or the "payoff profile function". There is one function for each player. As an example, for the Fools Mate terminal node we have, utility_1(FM)=0 and utility_2(FM)=1.
(or -1 instead of 0, if you want chess to be a zero-sum game).

So what we have above is an example of applying Definition 4.3 (Perfect Information Extensive Game) from
plato.stanford.edu/entries/epistemic-game/#ExtGamBasDef
to SCC. By the way, what they call "Act" in their definition would be here the set of all possible moves, which is called Moves above.

I give here examples of using the notation in #15. Yes, this is pedantic, but here it is anyway.

Definitions: Some positions (nodes) of SCC follow.
V0 = initial position of SCC
V1 = 1.e4
V2 = 1.e4 e5
V3 = 1.e4 e5 2.Nf3
V4 = 1.e4 e5 2.Bc4
V5 = 1.e4 e5 2.Bc4 d6
V6 = 1.e4 e5 2.Bc4 d6 3.Qh5
V7 = 1.e4 e5 2.Bc4 d6 3.Qh5 Nf6
V8 = 1.e4 e5 2.Bc4 d6 3.Qh5 Nf6 Qxf7#

- V8 is a terminal position; i.e. V8 in Terminal.
- V1-V7 are all elements of DecisionNodes.
- e4, e5, Bc4, etc are all in Moves.
- moves(V0) = {a3, a4, b3, b4, c3, c4, d3, d4, e3, e4, f3, f4, g3, g4, h3, h4, Na3, Nc3, Nf3, Nh3} the 20 possible moves for White in the initial position.
- Successor(V0,V1). That is, V1 is a successor of V0.
- TransClosure(V2,V8). That is V8 has V2 as a parent in the transitive closure under the Successor relation.
- turn(V0)=1, turn(V6)=2. That is, it is White's turn in the initial position V0 and it is Black's turn in position V6.
- utility_1(V8)=1, utility_2(V8)=0. V8 is a terminal position and so utility_1, utility_2 are both defined for V8. White wins, Black loses.

As we can see in #16, standard game theory applied to chess is trivial.

The terminal nodes are the checkmate/drawn positions. Both players know how to tell if a position is such. Both players agree on the payoff of these terminal nodes. Hence, they know each other's utility functions; which are only applied at these terminal nodes. There is no probability to the utility functions; the positions are checkmate or draw.

It is trivial to change the normal payoffs from standard chess' (1,0), (0,1), (1/2,1/2) to (1,-1), (-1,1), (0,0) and thereby make SCC a zero-sum game.

The Nash equilibrium is easy computed by both players as is their "strategies"; which means only the moves they will play in any position. Hence, SCC is a strictly determined game per the definition here
en.wikipedia.org/wiki/Strictly_determined_game

Per here en.wikipedia.org/wiki/Game_theory#Perfect_information_and_imperfect_information
"A game is one of perfect information if all players know the moves previously made by all other players."

So SCC is a perfect information game.

Per here en.wikipedia.org/wiki/Complete_information#Complete_versus_perfect_information
"Complete information is the concept that each player in the game is aware of the sequence, strategies, and payoffs throughout gameplay."

By "sequence" this means the moves played, "strategies" was defined above, as was payoffs. We've seen SCC has all these and so SCC is a complete information game as well.

I can hear the screams. "Chess is only complete information if you have the complete game tree and can perform the min/max procedure. Chess players do not necessarily look-ahead to checkmate/draw!"

True enough. So define for me in the models of these papers the "game" of chess that you are thinking of.

You see that is the crux of the problem. Game theory wanted to define the game; which I've made explicit in #15. Game theory then wanted to show what the "strategies" would be to maximize the payoffs for the players. But strategies here has a term-of-art meaning; not the usual meaning. And the answer is trivial.

If you are going to define chess in game theory as game theory currently is, then you have to define the terminal nodes, and the utility function on those terminal nodes. For chess, that is trivial.

And if you do not use the complete game tree in your game of chess, what are you using that fits the game theory model? Game theory requires terminal nodes. Game theory requires a *game*; not an incomplete game tree.

I am at a loss in understanding how game theory can help when we cannot see the terminal nodes.

See lichess.org/forum/team-jomegas-tabia/opening#2
for some numbers off the web on the size of SCC.

Despite game theory having only trivial things to say about chess, some people are trying to use what part of the game tree we do know to increase our knowledge of chess. An example is web pages that look at statistics from the endgame tablebases. Another, flawed in my opinion, example are the web pages using databases of games or computer generated moves for statistics. While both of these may interest people, I think they do little to help people play better chess.

An interesting mathematical question regarding the partial game tree is
"What are some interesting measures of the complexity of a chess position with respect to how many well-known patterns emerge from it while analyzing it?"

The more patterns someone knows the less complex the position is!

What is known about simpler variants of chess in terms of win/loss/draw?