Chess & Matrices: Can Matrix Transformations Determine Optimal Moves?

[Brad_Ad23]

Just an idle question I suppose...but we all know one can represent a chessboard as an 8 by 8 matrix. Let white be positive and black be negative.

Pawns are 1's
Rooks are 2's
Knights are 3's
Bishops are 4's
Queens are 5's
Kings are 6's
empty spaces are 0's

Is there any way to use matrices and their transformations of when you make a move to determine what the next optimal move is based off of the original matrix?

 

[LogicalAtheist]

Barely familiar with a matricies other than what one looks like. Don't know a thing about them. I also don't play Chess. Frankly, I don't like chess. But it seems to a "smart persons" game. So, should I play? I know how, but would have ZERO strategy, I could easily learn with a good "master chess" book.

 

[Brad_Ad23]

Greetings. Chess is a very logical game and if you get into it, loads of fun. I never started with a strategy either, but you develop your own.

My question with matrices relates to whether or not they can be used to reveal an underlying ultimate strategy.

 

[LogicalAtheist]

Yeah. Well I tend to stick to things I'm quite good at, and I never thought I'd want to become great at chess. In otherwords, I don't know if I'd ever enjoy unless I was very good and people we're jealous how good I was. I've come lately to find that I should stick to things I truly enjoy, rather than things I just would enjoy being good at. But hey, maybe someday I'll practice on my own with a method book.

Sorry to blog down your question, heh. I'll repeat it here so it isn't missed further:

"My question with matrices relates to whether or not they can be used to reveal an underlying ultimate strategy."

 

[BoulderHead]

Originally posted by Brad_Ad23
Just an idle question I suppose...but we all know one can represent a chessboard as an 8 by 8 matrix. Let white be positive and black be negative.

Pawns are 1's
Rooks are 2's
Knights are 3's
Bishops are 4's
Queens are 5's
Kings are 6's
empty spaces are 0's

Is there any way to use matrices and their transformations of when you make a move to determine what the next optimal move is based off of the original matrix?

Brad,
Where did you come up with such values? The Standard relative values are;

1 = Pawn
3 = Bishop
3 = Knight
5 = Rook
9 = Queen
With the King = Game

Though the Bishops and Knights are given an equal value, each has its own advantage, with the Bishop generally being given a slight edge.

 

[Brad_Ad23]

these aren't relative values. These are numerical values based off of position.

 

[BoulderHead]

It's all Greek to me

I'm curious aobut how these pieces were numbered.
[edit]
I must of missed something when the professor went over matrices??

 

[dav2008]

Originally posted by BoulderHead
Brad,
Where did you come up with such values? The Standard relative values are;

No no no ..He is just assigning arbitrary numbers for each piece..in other words instead of a visual board with pieces you havea 8 by 8 matrix with numbers representing pieces, like so:

 2 3 4 6 5 4 3 2
 1 1 1 1 1 1 1 1
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1
-2-3-4-6-5-4-3-2

Excuse me if i have the queen/king backwards, i forget..

 

[BoulderHead]

Originally posted by dav2008
No no no ..He is just assigning arbitrary numbers for each piece..in other words instead of a visual board with pieces you havea 8 by 8 matrix with numbers representing pieces, like so:

 2 3 4 6 5 4 3 2
 1 1 1 1 1 1 1 1
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1
-2-3-4-6-5-4-3-2

Excuse me if i have the queen/king backwards, i forget..

Huh, is this how the computers play the game?

 

[Brad_Ad23]

2 3 4 6 5 4 3 2
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1
-2-3-4-5-6-4-3-2

is the correct one i believe

 

[ahrkron]

It is possible to find matrices that, upon addition, will "move" the digits within the chessboard matrix (a very simple example would be a matrix with a -1 in the position of the white pawn initial position and +1 in its final position). However, these matrices would need to be supplemented with a set of rules (or some other extra structure) that say when they can be applied, and when they are advantageous. These rules would need to use information about strategy and position of all pieces. It seems that the matrices would not help much in optimizing a move.

AI techniques used for chess deal directly with these "higher-level" rules. Matrices can be used to store the state of the chessboard but, AFAIK, the evaluation of each possible move doesn't use regular matrix transformation on them.

 

[schwarzchildradius]

AI techniques used for chess deal directly with these "higher-level" rules. Matrices can be used to store the state of the chessboard but, AFAIK, the evaluation of each possible move doesn't use regular matrix transformation on them.

Definitely the state of the board is stored in a matrix. I was under the impression that the computer had a very fast but simple algorithm for playing chess and simply made millions of test moves 4-5 moves into the future and picked the best final outcome of these.

 

[plus]

Originally posted by schwarzchildradius
Definitely the state of the board is stored in a matrix. I was under the impression that the computer had a very fast but simple algorithm for playing chess and simply made millions of test moves 4-5 moves into the future and picked the best final outcome of these.

It is generally a bit more sophisticated than that. The computer does make test moves, and then rates the position it is in via a static evaluation. It then sees which move the opponent would make, to give its best position,etc. to predict outcome x number of moves infront.

 

[schwarzchildradius]

that doesn't seem that much more sophisticated ;) but that is good to know!

 

[plus]

You were seeming to imply that the computer considered all possible sequences of moves. It is more selective in the moves it considers.

But yes, it is the same idea - to find the best move.

 

[ahrkron]

You can see the process of generating moves as a tree where, out of each branch, many smaller branches (possible moves) are allowed.

The process of looking for the best move can be as "dumb" as generating all possible branches, assigning a "grade" to each final outcome and selecting the best of them (which already requires a good deal of thought to define how to assign a single number to each possible board position), but the number of possible moves grows rapidly, so that you can only look ahead a few moves if you do this.

There are many ways to cut "bad" branches on the go, so that you use your resources on the most promising branches. A lot of expertise has to go into deciding which branches to cut, and which are still promising at each step.

 

[Brad_Ad23]

Yes, yes, but what I am wondering is if there is some inherent strategem burried within the game itself, dealing with matrices, that could perhaps lead directly to the optimal solution? I gather nobody knows for sure at the least, but hope that it is not totally out of the question.

 

[plus]

Originally posted by Brad_Ad23
Yes, yes, but what I am wondering is if there is some inherent strategem burried within the game itself, dealing with matrices, that could perhaps lead directly to the optimal solution? I gather nobody knows for sure at the least, but hope that it is not totally out of the question.

If the optimal solution for chess were known, then there would be no room for debate.

I know the optimal solutions for smaller games such as othello (or reversi) has been found. But certainly not for chess.

 

[wimms]

Originally posted by ahrkron
You can see the process of generating moves as a tree where, out of each branch, many smaller branches (possible moves) are allowed.

The process of looking for the best move can be as "dumb" as generating all possible branches, assigning a "grade" to each final outcome and selecting the best of them (which already requires a good deal of thought to define how to assign a single number to each possible board position), but the number of possible moves grows rapidly, so that you can only look ahead a few moves if you do this.

Generally, computer relying onto weighting branches alone will succeed with playing against layman only. Top players will find it amazingly stupid and boring to conquer. I'm not top player, so I speak only from reading other's comments and opinion I've gathered myself.

Reason for this is that weighted branches are merely fuzzy constraints to available strategies. To implement strategy needs time, in chess speak, number of moves. Opponent must recognise strategy, and find its own strategy that during its implementation also counteracts or brakes enemies strategy. Most limited resource is 'time', number of moves to achieve the goal. Then there is limited freedom to change strategy based on opponents reactions and state of the board. Who can maintain most freedom of available strategies and at the same time reduce that for opponent, has advantage. That limits number of optimal branches for opponent, or imposes more constraints to its freedom of choise. As at beginning of game there is huge amount of possibilities, such advantage translates into mental overload of constrained opponent, gives advantage in 'chess-time' (opponent desperately needs slightly more moves to change fortuna), and leaves more freedom to 'clean up' small mistakes.

There is a reason why they maintain huge database of analysed games, both humans and computers. They're for recognition of set of strategies that were successful. Without such database, computer will also be unable to play top chess. They encode strategies, and counter-strategies, that may depart from dumb branch-weighting enormously.
Discovering new strategy is somewhat like discovering new mathematics, and is what truly puts human above computers so far. It requires intelligence in its highest form. Computers compensate with brute force.

Originally posted by Brad_Ad23
What I am wondering is if there is some inherent strategem burried within the game itself, dealing with matrices, that could perhaps lead directly to the optimal solution?

No, there exists no optimal solution. Every move possibly changes whole state of the board and space of optimal moves. Picking suboptimal move or even branch of moves is far from meaning lost game. Suboptimal move can easily ruin possible strategy space of opponent, forcing him to change strategies in now suboptimal state. Unexpected and illogical moves are usually what puts opponents into deepest think mode. Departure from known ground forces players into 'discovering new chess' mode, that's hard to computers due to lack of abstract thinking, and hard to humans due to huge space of possibilities.

Sticking with same good strategy after a stupid move can actually be stupid. Moves change applicable strategies, thus chess isn't just search for optimal moves.

Computers are beaten easily by departing from known chess in clever manner, thus tricks and deception is another level of strategy on its own. Exhaustion by forcing opponent into combinatorial explosion, etc.

 

[sol]

Seen your thread on Chess and the matrices.

http://www.fortunecity.com/emachines/e11/86/chess.html

I was just curious of the extension of the logic used here in terms of squares dark and light.


Just a twist.

This was presented in information the other day, and I thought it quite intriguing. Does it provide futher thinking in the thread presented here. Don't know? Does it matter. Nope

Sol

 

[STAii]

Sorry to interrupt the conversation.
As far as i know (i am not a good chess player, but ..) there are certain movements in chess that does not need thinking, they are ALWAYS winning movements, specially talkin about the first 10 movements in the game.
So maybe the computer bases itself on a big DB of cases in which a certain movement is always usefull, and checks the DB after each user's movements (this might make it a little faster).

by Brad_Ad23
2 3 4 6 5 4 3 2
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
-1-1-1-1-1-1-1-1
-2-3-4-5-6-4-3-2

is the correct one i believe

I don't this so, in chess the white king faces the black king, which is not the case in your matrix. Also, the white king lies on a black square, and the black king on a white square, and since the number of rows equals 8 (an even number), in your matrix both the white and black king will lie on the same color.

 

[Hurkyl]

No, there exists no optimal solution.

Yes, there is, in principle, an optimal solution. The number of chess board positions is finite, so with sufficient computing power you could analyze all possible continuations of a game and determine which move gives the best results. You could further tune your optimal solution to your opponent by pruning away continuations that involve moves that, while are strictly better, your opponent would not have performed. (Though this requires some knowledge of your opponent)

It may even be possible that there exists a strategy that guarantees a win no matter what your opponent does.

 

[wimms]

Originally posted by Hurkyl
Yes, there is, in principle, an optimal solution. The number of chess board positions is finite, so with sufficient computing power you could analyze all possible continuations of a game and determine which move gives the best results.

Are you good chess player? I find your position unlikely, because after analyzing all possible continuations you'd find about few zillion that all equally 'gives the best results', and that you can choose only few to pursuit, as each takes lots of moves. IF these few are broken by opponent, all of your analysis is waste of time.

There is a kind of HUP inside chess. You either can know optimal solution and are not being able to use it (equal opponent!), or you don't know optimal solution and still use one close enuf intuitively. Thats the beauty of chess. For every 'optimal solution' there exists counteraction, always.

It may even be possible that there exists a strategy that guarantees a win no matter what your opponent does.

This isn't tictactoe.

 

[r637h]

To paraphrase Churchill: "Chess is the worst possible game, except for all other games."

I'm sure Matrix Analysis has an application.

If so, one computer program or another probably uses it to play.

Very interesting question. I'll try to contribute.

Rudi

 

[Hurkyl]

This isn't tictactoe.

Correct, chess is not tic-tac-toe.

However, like tic-tac-toe, chess is a game with a finite number of board positions, and can, in principle, be brute forced from the starting position down through all possible combinations of moves (though, at present, that feat is too formidible to attempt)

 

[wimms]

Originally posted by Hurkyl
However, like tic-tac-toe, chess is a game with a finite number of board positions, and can, in principle, be brute forced from the starting position down through all possible combinations of moves (though, at present, that feat is too formidible to attempt)

Yes-yes, I completely agree with that part. It IS possible to brute force all possible combinations. My point was merely that this is not enough, or more likely - useless. Any game is infinitesimal subset of all possible combinations, and knowing all possible combinations "doesn't make a game".

From any state of board, you could find optimal solution. But that optimal solution depends on what opponent does. You assume that opponent takes also optimal solution, and contradiction occurs - one of players has to fail. Therefore, one opponent is going to make suboptimal move, sending whole 'optimal solution' way south. At this point, 'new optimal solution' must be found. Over and over again. And that's precisely what chess players are constantly doing. Single move on the board can change notion of optimal solution. When players recognise what 'optimal solution' opponent invented, they immediately try to ruin it. And its always possible, unless player has already failed.

From any state there are many equally optimal solutions, and player has to choose ONE to pursuit. When that choice is made, player is committed, he has spent some of his most precious resource - number of moves. And if that 'path' is ruined, player is left with shaky ground. Do you see what I mean?

 

[chroot]

Originally posted by wimms
From any state of board, you could find optimal solution. But that optimal solution depends on what opponent does.

Of course -- and every time your opponent moves, you'd have to calculate the most optimal move.

The idea is a "dictionary." Because there are a finite number of board states, you could (in principle) solve every single one for the best move. Then playing perfect chess just boils down to looking up the board state in the dictionary and making the pre-computed best move.

Chess is a turn-based game, so all chess computers work one move at a time. We're not talking about designing forty-move strategies and then hoping the opponent does the right (wrong) things. Instead, you just imagine that every board state has a single optimal move. This is why you can walk up to a chess game in progress (having no information about the game other than its current state) and still know what move to make.

You are correct that there could be dozens of moves which are all ranked "optimal" when considering only the state of the board at one time. You can break the tie by considering the results of all possible opponent moves, and then all your moves after his. At this point, the likelihood of any two moves being equally good is very small.

You assume that opponent takes also optimal solution, and contradiction occurs - one of players has to fail.

Good chess is actually based around the concept of forced moves -- situations where, even when playing perfectly, a player must move into a situation where he loses a piece, or some development. Chess would be no fun without gambits and forced moves. Your idea that two perfect players would never lose to each other is, quite frankly, silly.

Of course, such perfect chess would be pretty boring -- perfect chess players would always make the same moves. In fact, given two perfect chess players, the very first move would determine the entire game. Since you can only move 18 ways in the start-game, there would be exactly 18 different chess games -- period.

At this point, 'new optimal solution' must be found. Over and over again. And that's precisely what chess players are constantly doing.

And not coincidentally, it's exactly what chess computers are doing.

- Warren

 

[Hurkyl]

From any state there are many equally optimal solutions, and player has to choose ONE to pursuit. When that choice is made, player is committed, he has spent some of his most precious resource - number of moves. And if that 'path' is ruined, player is left with shaky ground. Do you see what I mean?

I know what you mean; you're only thinking one move at a time. When a game theorist says "optimal move", they are looking ahead for all possible moves.

 

[wimms]

Originally posted by Hurkyl
I know what you mean; you're only thinking one move at a time. When a game theorist says "optimal move", they are looking ahead for all possible moves.

No. I'm not thinking one move at a time. Let's maybe call what you mean 'optimal strategy' that consists of and is picked from ALL predicted possible moves of both players. After analysing all possible moves, we find strategy that with highest force leads to win. Now to implement that strategy, you have to make moves in its direction. Opponent has to reply with 'expected' moves. As long as this is the case, we are inside our optimal strategy. If opponent makes 'bad' move, we could win faster. maybe.

But, I'm saying that there exists no single 'optimal strategy'. There are many equal strategies, too many to count. Any single of them leads to win IF opponent replies as 'expected'. Situation you get into is this: I know 100 strategies that can lead to win. I can predict any possible move. But, if I pick strategy N and make first 3 moves in it, and opponent makes moves that doesn't fit into my strategy, after 4-5 moves my strategy is canceled and won't lead to win. I know that beforehand. So I pick another strategy. But, for any strategy whatever, there always exists set of opponent moves that cancels my strategy.
So, I am forced to cause my opponent to make a 'mistake'. Thats my only strategy.

 

[Hurkyl]

But, if I pick strategy N and make first 3 moves in it, and opponent makes moves that doesn't fit into my strategy, after 4-5 moves my strategy is canceled and won't lead to win. I know that beforehand.

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.

 

[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.