For every game, is there a formula $f(G)$ which takes the game state $G$ as input and whose output can be interpreted as draw/win/lose?

35 Views Asked by At

For the tic-tac-toe example, we may set the game state after a move by each player (X and O played), or equivalently before the move of the first player:

$M$ = \begin{bmatrix}M_{11}&M_{12}&M_{13}\\M_{21}&M_{22}&M_{23}\\M_{31}&M_{32}&M_{33}\end{bmatrix}

With $M_{ij}$ as 1 for the X's and -1 for the O's and 0 for no input.

In this case, is there a formula $f$ = $f(M)$ = $f(M_{ij})$ which can tell you if the game is winning, drawn or losing for the first player? As a false example, imagine if $det(M) < 0$ meant that the first player is losing, $det(M)=0$ that the game is drawn and $det(M)>0$ as a win for the starting player.

I would like to know if such as formula exists, which I suspect is true at least for a simple game such as tic-tac-toe, for more complicated games such as chess, and also if it is theoretically possible for any and all win/lose/draw games between two players.

What I am asking is distinct from a table-base lookup. I don't want to find a nifty way of encoding game states to an index in a theoretically computed table-base. I am asking if it is true that a theoretical formula exists for these games which only inputs the current game state and outputs something which can be interpreted as a win/draw/loss (if you want to be stricter, a function whose input game state cannot be solely determined by the output).

In the example of chess, I am asking if there is a theoretical function that can parse the encoded game state analytically (no looking ahead) and decide if the game is winning, losing or drawn.

In case I did not clarify well enough, I am willing to edit the question with your comments.