30 Jun 10
Originally posted by JS357Assuming every chess game is finite (I'll come back to this), and both players play rationally, chess has a solution (or more scientifically, "pure strategy Nash Equilibrium"😉 according to the Games Theory. This was proved by Zermelo in 1912 (although there are some issues concerning that proof); this result was generalised for all finite games of perfect information by Kuhn in 1953.
In the context of this question the relevant characteristics of chess are that the starting position is defined, the allowable moves are defined, the player designated "white" moves first, the moves and resulting positions are known to both players and are determined by each player's choice, not chance, and a winning, losing, or drawing position is attainable ...[text shortened]... lways win, or at least, always avoid losing. This sounds like a game theory master's thesis.
In practise, however, to find this solution is very difficult.
First, there there are so many possible chess games - the popular (conservative) estimate is around 10^123 , and some say it can be as large as 10^1000 for the first 40 moves only. As for the comparison with the number of atoms in the known universe - the upper bound for those is thought to be 10^89, meaning you would need all the atoms in 10000000000000000000000000000000000 (potentially much more) of such universes to match the number of possible games.
Second, working out all the variations is only a start. To find the solution one has to apply the "backward induction" (or other method using similar idea), ie at the highest level of the game tree (5949, or whatever the highest possible number of moves in a game with the enforced 50 moves rule is) the player whose turn it is chooses the move that leads to the successive node with the highest payoff for him (or makes an arbitrary selection in case there are several possibilities), and so on, all the way up to the root. This means on average 30 or so (again, whatever the average possible moves a player can have on his turn) comparisons at every (or almost every - I just cannot see how this can be avoided) node of the tree.
This will give you an outcome of the game - White wins, Black wins, or a draw - and ONE "perfect game" (strategy). For a complete mathematical solution, how I understand it, you would need to find ALL of the strategies for both players, ie all of the "perfect games", and there are likely to be zillions and gazillions of those; the numbers involved are so vast it's beyond me. And that is assuming both players play rationally, otherwise the numbers are simply crazy.
And what about the issues of storing, maintaining, accessing, using and manipulating all this information?
But yes, theoretically chess has a solution.
Assuming it is a finite game. This is from the FIDE Laws of Chess:
------------------------------------------------------------------------------------------
[[[9.2 The game is drawn upon a correct claim by the player having the move, when the same position, for at least the third time (not necessarily by a repetition of moves):
a. is about to appear, if he first writes his move on his scoresheet and declares to the arbiter his intention to make this move, or
b. has just appeared, and the player claiming the draw has the move.
Positions as in (a) and (b) are considered the same, if the same player has the move, pieces of the same kind and colour occupy the same squares, and the possible moves of all the pieces of both players are the same.
Positions are not the same if a pawn that could have been captured en passant can no longer be captured in this manner. When a king or a rook is forced to move, it will lose its castling rights, if any, only after it is moved.
9.3 The game is drawn, upon a correct claim by the player having the move, if:
a. he writes his move on his scoresheet and declares to the arbiter his intention to make this move, which shall result in the last 50 moves having been made by each player without the movement of any pawn and without any capture, or
b. the last 50 consecutive moves have been made by each player without the movement of any pawn and without any capture.]]]
---------------------------------------------------------------------------------------
The key is the words "upon a correct claim". What if none of the players make a "(correct) claim"? Consider the following situations:
(1) Two machines, infinitely repaired, if necessary, neither programmed to claim the draw under the above rules, play chess with no time control/with time increments after each move - if the theoretical solution of chess is a draw, the game will last forever, ie it is infinite.
(2) Two players play chess for fun, with no clocks ticking, and suddenly one of them cannot continue to play (eg. human dies, machine breaks down) - the outcome of the game is undefined.
These examples may look pedantic/unlikely/laughable, etc, however in mathematics you cannot cut corners - for a stonewall proof every single case must be covered. Therefore, IMO, until there is an official and undisputed way to deal with situations like the two above, chess as we know it must be treated for mathematical purposes as an infinite game/game with undefined outcome and thus does (and can) NOT have a solution.
30 Jun 10
Originally posted by kes29First of all, in a game theory sense, the act of claiming a draw IS a move. You cant arbitrarily exclude it anymore than you could exclude a move by a piece. Therefore your two examples are meaningless because they dont include all of the options available to the players.
Assuming every chess game is finite (I'll come back to this), and both players play rationally, chess has a solution (or more scientifically, "pure strategy Nash Equilibrium"😉 according to the Games Theory. This was proved by Zermelo in 1912 (although there are some issues concerning that proof); this result was generalised for all finite games of perfect info ...[text shortened]... nite game/game with undefined outcome and thus does (and can) NOT have a solution.
Second, when you reach a position of 3 fold repitition the player has three choices. To claim a draw, repeat the position or play another move that breaks the symmetry. If a player is in an unwinnable position he MUST take the draw according to game theory because game theory assumes that all players are rational. If the game is unwinnable then "draw" produces the highest payoff so that player will always choose to draw. It wouldnt be rational to choose a lower payoff. If the player is in the superior position then he won't choose to draw but then his opponent will have the same options he had and WILL choose to draw. So the only time they would continue to repeat is if they are both in unwinnable postitions. In that case there would be a Nash equilibrium strategy of (repeat,repeat) which is drawn. The mistake you make is assuming that we have to wait for the game to be finished in order to determine what the Nash Equilibrium is. We dont. Infinitely reapeated games can have a Nash Equilibrium just like finite games can. Once it is estasblished that (repeat, repeat) is the correct strategy then the game is drawn as far as game theory is concerned. The players can play the same moves until the end of time and it still wont change anything.
Chess is solvable and will be solved a lot sooner than most people think. I keep seeing atronomical numbers thrown around but the truth is its mostly just wishful thinking. Deep Blue could analyze 200 million positions per second and thats ancient technology compared to whats available today. The only thing that you would need to solve chess right now is to combine someone who wants to do it with the resources needed to do it and the knowledge of how to do it. Chess could be solved right now. And at the rate at which computer processing is doubling in about 50 years most people will have computers powerful enough to solve chess on their phone.
01 Jul 10
Originally posted by savage4731So do you think in our lifetime we will see a computer that can play perfect chess?
First of all, in a game theory sense, the act of claiming a draw IS a move. You cant arbitrarily exclude it anymore than you could exclude a move by a piece. Therefore your two examples are meaningless because they dont include all of the options available to the players.
Second, when you reach a position of 3 fold repitition the player has three choi ...[text shortened]... about 50 years most people will have computers powerful enough to solve chess on their phone.
01 Jul 10
Originally posted by USArmyParatrooperI think chess probably will be solved in my lifetime and I think after it is there will be a long debate on what the "perfect" game is. There will be people who define perfect as purely mathematical. There will be some who define it as purely aesthetic. And there will be some who define "perfect" as competitively perfect as in which variation produces the most problems for the opponent while still eliminating any chance of losing. There will also be a lot of people claiming that their favorite player has already played the perfect game and trying to use the solution as proof.
So do you think in our lifetime we will see a computer that can play perfect chess?
So, to answer your question, I think we'll see computers that cant be beaten but to call it "perfect" depends on what you mean by "perfect".
01 Jul 10
Assuming computers continue to evolve to greater processing speeds and larger memory, then it is inevitable that chess will eventually be solved as there is a finite number of possibilities. However, that is a LONG way off! Personally, i don't think that will kill chess, as a player would have to memorise billions and billions of variations. Humans can't do that... 😉
- Joined
- 29 Dec 08
- Moves
- 6788
01 Jul 10
..."If the game is unwinnable then "draw" produces the highest payoff so that player will always choose to draw. It wouldn't be rational to choose a lower payoff."...(This concerns the draw by repetition and draw by 50-move rule, both of which make it optional to claim a draw.)
But declining to claim draw is not choosing a lower payoff, points-wise. If the game is unwinnable (assuming you mean for both sides) the value of claiming a draw on current move n (0.5), is no greater than the value of claiming a draw on move n+1, because there will never be a move which offers less than this value of 0.5. So the player having the option of claiming a draw will be indifferent to doing so, without external motivation or, call it, external programming. Of course, humans in human settings have motivations that lead to early decisions, such as mere boredom, but what would justify putting a rule into a computer chess program, like "in unwinnable/unlosable positions, claim draw by 3-repetition or 50-move rule, as soon as possible"? Do you want to tell the machine that 0.5 now, is greater than 0.5 later?
01 Jul 10
Hi Marink.
"Personally, i don't think that will kill chess,..."
Let's just say some computer eventually does solve and produces the
perfect game. Then we will all know the best opening move. (and reply).
OTB chess will go the same way as draughts/checkers which was
computer solved a long time ago.
That was quite easy for a modern computer - only 32 squares are used,
captures are forced and all the men, till they are crowned, move the same.
Then the only difference is that the crowned pieces can go backwards.
In Chess players will draw openings by lots which is what they now
do in draughts/checkers tournaments.
01 Jul 10
Originally posted by greenpawn34Hi greenpawn34!
In Chess players will draw openings by lots which is what they now
do in draughts/checkers tournaments.
You might know of this story which I cant remember where it comes from nor if it is true or not.
"Chess was originally a gambling game where the pieces which moved were dictated by the throw of a die.
1 was a King , 2 a Queen, 3 A Rook, 4 A Bishop, 5 a Knight, 6 a pawn.
If the move could not be legally made, then a pawn MUST move if able. Otherwise the King must move.
If the king is in check then no die is rolled and the player can choose their response"
02 Jul 10
Originally posted by JS357By "unwinnable" I meant that the player whose turn it is to move has a position that cannot be won with correct play by the opponent. It could potentially be lost but the best he could hope for is a draw.
(This concerns the draw by repetition and draw by 50-move rule, both of which make it optional to claim a draw.)
But declining to claim draw is not choosing a lower payoff, points-wise. If the game is unwinnable (assuming you mean for both sides) the value of claiming a draw on current move n (0.5), is no greater than the value of claiming a draw on move n+ ...[text shortened]... as soon as possible"? Do you want to tell the machine that 0.5 now, is greater than 0.5 later?
The payoff for a draw on each successive move would be lower. If we assume the payoff for a draw is .5 and the probability of the draw occuring if chosen on that move is 100% then that would be .5* 100%= .5. For each move after that the probablilty of a draw goes down. There's still the possibilty of losing or of any number of things intervening and preventing a draw even if its forced. So if we say the probablility of a draw on n+1 is only 99% then that would be .5*99%= .495, a lower payoff.
The logical thing to do when faced with two lines that lead to the same conclusion is to choose the most efficient one. Computers do that already right now. If a computer has a choice between a mate in 1 or a mate in 10 it will choose the mate in 1.
02 Jul 10
Originally posted by TiwakingThat's sounds pretty fun. Might give that a go in my next game.
Hi greenpawn34!
You might know of this story which I cant remember where it comes from nor if it is true or not.
"Chess was originally a gambling game where the pieces which moved were dictated by the throw of a die.
1 was a King , 2 a Queen, 3 A Rook, 4 A Bishop, 5 a Knight, 6 a pawn.
If the move could not be legally made, then a pawn MUST move ...[text shortened]... ve.
If the king is in check then no die is rolled and the player can choose their response"
02 Jul 10
"If a computer has a choice between a mate in 1 or a mate in 10
it will choose the mate in 1."
So that is their secret - damm clever these things.
Hi Tiwaking.
Yes a form of chess was played with dice - the pieces moved a bit
different then.
If anyone asks you where did chess come from tell them the game
we played today was invented by the Spanish in the early 1500's.
They increased the power of the Bishop, make a Queen a Rook and Bishop
combined and gave the pawn two moves. (they got riid of the dice).
02 Jul 10
Originally posted by greenpawn34Just because you know the best first move, doesn't mean your opponent has to respond with the best reply! It is totally possible for black to get a good game with any number of deviations that a computer would beat but requires a human to think. There is no way a human can memorise every 'best move' for every possible game in every possible variation even if that game can be 100's of moves in length. Chess is far too complicated for that, i think we're all aware of that... 🙂
Hi Marink.
"Personally, i don't think that will kill chess,..."
Let's just say some computer eventually does solve and produces the
perfect game. Then we will all know the best opening move. (and reply).
OTB chess will go the same way as draughts/checkers which was
computer solved a long time ago.
That was quite easy for a modern computer - ...[text shortened]... ers will draw openings by lots which is what they now
do in draughts/checkers tournaments.
02 Jul 10
Originally posted by savage4731No, the truth is that raw computational power is useless if you want to brute force solve chess, you would have to break several fundamental laws of physics to even contain the analysis. The reason engines are getting stronger is due to refinements of the heuristics used to search for moves rather than the hardware.
Chess is solvable and will be solved a lot sooner than most people think. I keep seeing atronomical numbers thrown around but the truth is its mostly just wishful thinking. Deep Blue could analyze 200 million positions per second and thats ancient technology compared to whats available today. The only thing that you would need to solve chess right now is ...[text shortened]... in about 50 years most people will have computers powerful enough to solve chess on their phone.
For the past 50 years computational power has doubled every two years as predicted by Moore's law--at the current rate the universe will die of old age before computers catch up with chess.