Chess & Matrices: Can Matrix Transformations Determine Optimal Moves?

[wimms]

Originally posted by Hurkyl
But you forget; the "optimal strategy" to which I'm referring considers all possible moves; in particular it's impossible for the opponent to make a move that doesn't fit into the strategy.

Such strategy is impossibility in chess. If it were possible, they'd had found it already.
What you are saying is that there exists strategy within which whatever opponent does, we still achieve a win. Its not so. Success of your strategy always depends on what opponent does.

What I'm saying is that even if you know ALL possible moves, you HAVE TO select only 1 to make at a time. Then opponent makes his move, either one that fits your strategy or some that cancels it out. You'll never have ability to FORCE opponent into making always moves that suits you. You'll only have ability to know beforehand all opponent moves that destroys your strategy. You can't escape that, because any move on board is undoable 'decision'. When you have decided to take 1 path of many to your win, you can't take another path at the same time. And any action on board has counteraction.

Best you could achieve with knowing ALL possible moves, is this: in given state of board you'll find 100 possible paths to a win. Any of the paths needs different move after 2 turns and only few unique moves this turn. You have to choose. You know that for every move you make there exists genuine countermove that would lead to win of opponent. But You HAVE to choose.

What is your choice? Giving up? Gambling? Taking one move and after opponent makes a move that you know could lead to his win, would you capitulate? Or, would you consider facing situation like that as already lost game? But then, the only situation in which you could play is when every single opponent move is forced. There is not enough convergence in chess to offer such case even in principle.

The situation I described is uncertainty. Chess is full of states that have such Uncertainty, it consists of them! Such Uncertainty blocks your 'vision' of ALL possible Outcomes. Knowing All possible moves shows you equal chances to win and loose from any state of the board where strategic balance exists. Its the players who make decisions to win or loose.

See, there is difference between knowing the path, and walking the path.

 

[Hurkyl]

Such strategy is impossibility in chess. If it were possible, they'd had found it already.

Chess has too many board positions to brute force. That's why I keep saying "In principle".

What you are saying is that there exists strategy within which whatever opponent does, we still achieve a win.

No I am not. I am saying there exists an optimal strategy. In chess, or any game with a finite number of states, this means that exactly one of the three situations is correct:

(1) There exists a strategy for white that guarantees a win, no matter what black does.

(2) There exists a strategy for black that guarantees a win, no matter what white does.

(3) There exist strategies for both white and black that guarantee you will not lose, no matter what your opponent does.


The rules of chess are fairly complex, to my knowledge nobody has proved which case is correct or eliminated a case. (But such analysis has been made for other interesting games; for instance there is a rigorous mathematical proof that there exists a strategy in go for the first player which guarantees the second player cannot win, and similarly, you can mathematically prove there is a strategy in hex for the first player which guarantees victory)

 

[wimms]

Originally posted by Hurkyl
No I am not. I am saying there exists an optimal strategy. In chess, or any game with a finite number of states, this means that exactly one of the three situations is correct:

I see. I was confusing optimal strategy to winning strategy. Interesting, all of the options include condition no matter what opponent does. I don't think this can be the case with chess. There, everything depends on what opponent does upto some point in game where one of your pointed situations is reached. Then players think about it, and agree on one of capulation or draw.

(1) There exists a strategy for white that guarantees a win, no matter what black does.
(2) There exists a strategy for black that guarantees a win, no matter what white does.
(3) There exist strategies for both white and black that guarantee you will not lose, no matter what your opponent does.

Chess game can take any of the above cases to be true. (1) Is the case of forced moves. There are states of board when black's moves can be fully forced. (2) is for case I showed above, when best strategy for white would be to skip the move but it can't and thus is forced to commit to one of his possible winning paths, and thus can be defeated. (3) is obviously also pretty usual in chess from states where win is not possible anymore.

So, for same game of finite states, there exists ANY of these options, depending on state of board. Not 'exactly one of'. For board in chess to reach any of above options needs previous moves. Thus fight in chess is not initially for a win, but for one of above options, strategic advantage. White wants to achive 1 without ever coming across 2. Black wants to force white into 2 without ever crossing 1. And option 3 is taken as goal in case all else goes too wrong.

Based on game theory its assumed that one of these 3 options is set in stone at the very start of game. But I question that. At start of game board is inert, no move has any immediate value. Its merely setting up the stage. Moves are not independant either. They are necessarity multimove opening strategies to build up confrontation of forces.
Initially board goes from low possible possibilities to large number possibilities. Each move contributes to combinatorial explosion. So, single move can create huge number of possibilities, not reducing them. Thus options 1-2 are excluded at this stage. Tension builds, possibilities to resolve it grow. Only when players start annihilating pieces happens reduction of possibilities, 'wave function collapse', that brings board to state that can be one of the 3 you mentioned, or still not defined.

If both players could see all possible moves, then probably 3rd option is the only viable. But, goal of game is to win not to draw. This forces both players to leave 'safe ground' and attack.

You know the game rock-paper-scissors? When its played as imperfect information game, there is no optimal strategy to it, but if its played as turnbased duell, its (2) opponent can always win. I took this as example to point that in chess there are very many branches of tree that have similarities. There is uncertainty about what opponent does. There are traps into which one can't step. And so game is most of the time in razorthin balance of forces in draw condition. Single even tiniest advatange in either pawn or moves can make a game. Such thin balance in face of so vast move space makes imo single optimal strategy very unlikely to exist.

 

[Hurkyl]

Basically, the proof works like this:

First, you draw a big tree of every possible chess game history. (The three move repetition rule + finite number of board positions guarantee that there are only a finite number of game histories)

You do it as follows:

At the very top of the tree, you place the game history with no moves; i.e. the initial gamestate.

Then, you draw an edge for every move white can make, and you put the corresponding game history at the end of that edge.

Then from all of those nodes, you do the same for every possible move for black, then again for white, et cetera.


In principle, this gives is a big game tree that has the results of every possible combination moves the players can make.


Now, we work from the bottom up. The leaves of this tree represent finished games (they're leaves because there are no moves that can be made from them). We go through every leaf and label it W if white won, B if black won, and D if it was a draw.

Now, for every node in the tree such that we've labelled all of its children:

If it is white to move
:if there is a child node labelled W
::label this node W
:else if there is a child node labelled D
::label this node D
therwise label this node B
otherwise it is black to move
:if there is a child node labelled B
::label this node B
:else if there is a child node labelled D
::label this node D
therwise label this node W


The nodes labelled "W" are nodes from which white is guaranteed a win by perfect play. The nodes labelled "B" are nodes from which black is guaranteed a win by perfect play. The nodes labelled "D" are nodes where both players are guaranteed at least a draw through perfect play.

The proof that the above claim is correct is by induction:

It's obviously true when the node we consider is a leaf. White is clearly guaranteed a win if he's already won! et cetera

Now, choose some node in the tree, and assume the claim is correct for all of its descendants. It's easy to see that the claim is also true for this node!

For example, if it is white to play at this node, and one of the children is labelled "W", then white can play the move that leads to that node, and since that child node guarantees a win for white (through perfect play), the current node also guarantees a win for white, which is why we labelled it "W".


By induction and the fact the tree is finite, the above construction proves my claim that exactly one of those three possibilities is correct for any particular gamestate. In particular, there is an answer for the initial board position!



The only reason there is any uncertainty at all is because the game tree is far too large to compute (either by our brains or by computer). There is uncertainty because we run out of computing power and we're forced to guess at the labels instead of being able to continue the tree until its completed.