Chess is not solvable
Teri A Meyers
Here are my thoughts on this matter, which come more from philosophy than
from game theory. I operate on the assumption that from the initial position
neither side can force a win. This assumption may be mathematically unprovable
but neither can it be disproved, and moreover, I suspect that the vast
majority of chessmasters would agree with it based on personal experience.
(What's more, I suspect most chessmasters would reject the game theorists
idea that the starting position is (or could be) a win for Black as sheer
hogwash). Anyways, if the starting position represents a balance (a "draw"
from the perspective of game theorists), than it strikes me that the game
can only be won if someone disturbs the balance (ie, makes mistakes). So
long as the balance is held, who can say there is any theoretical upper
limit to the number of possibilities (actual moves plus the vast horizon
of possible variants). A machine which conducts a search for a win X number
of ply (whether 10 ply or a zillion) will never find it if the game is a
draw from the position where it begins its analysis (such as before move
one). However, when can the machine stop its analysis and declare the
position conclusively a draw? However many ply it goes, it finds the
position a draw, but how does it know it will not find the win by searching
one ply further? It will have to search to infinity. If it ever did
get to infinity (which by definition is impossible), could it then supply
us with "the solution" to chess in the form of the moves of the "ultimate
draw" or "ultimate game"? Or would it not provide us with an infinite
number of drawn games? One last thought comes out of this: since the
number of possibilities in a chess game is by this analysis infinite, the
computer will reach the end of them and thus never play "the" perfect
move. It may play well enough to hold the draw, but perhaps it will not
play well enough to never make mistakes. And so, even in its most
advanced state (which it will also never reach, because it will keep
improving to infinity), it may still lose.
Jerry Meyers
John Eisenberg
There are only a finite number of possible chess games.
Potentially, one could examine each one and determine
the possible outcomes. Whether there is or is not a
forced win for either side is theoretically computable.
John.
The Nordic Man
>
>Here are my thoughts on this matter, which come more from philosophy than
>from game theory. I operate on the assumption that from the initial position
>neither side can force a win. This assumption may be mathematically unprovable
Philosophy has nothing to do with game theory and there are not an infinite
amount of chess positions. There are 32 pieces and 64 squares, you figure.
To say it's solvable does not mean that one side must win; perhaps the game
is a draw. The general game theory idea is that chess is a FINITE game.
There exists only a FINITE number of legal postions. Perhaps at some point a
game can not move any further with perfect play, and then a draw by repitition
occur eventially, or one must make a mistake. Make sense?
If the game progresses farther and farther with nothing dynamic happening,
then at some point the position will repeat itself three times, a draw.
My .02 regarding the insipid topic of a God chess playing device. My
idea of a god and a perfect chess computer are quite different. A god should
by definition be omniniscient. This would mean that the god could quite
easily understand exactly what position needs to be reached to inspire the
opponent to fall in to a trap. This would be possible because the mortal
man, alas (or thank God), is NOT perfect and all-knowing. Since a perfect
chess computer could not set these traps, but only play "the solution" it
is plausible that the games would consist only of draws, wins or losses
depending on how the solution to chess pans out. Nobody can beat God, the
question is, how many pieces can he spot you...
My thanks to Mr. Fry for posting the Fischer/Spassky games. They
are much-appreciated.
Cheers and insert ;-) and :-) wherever you must to feel better.
-Michael "How Swede it is" Nyman
--
--------------------------------------------------------------------------------I know you believe you understand what you think I said, but I am not sure you
realise that what you read is not what I mean.
--------------------------------------------------------------------------------
Francis Muir
While this is true (in my experience statements from CSLI often are), it
might be more illuminating to consider the status quo. For persons playing
the game right now it might be smart to think of chess as a classic game
in the Neumann sense. That is, and depending on the understanding of your
own and your adversaries levels of skill, it might be smart to introduce
an element of randomness on those occasions when there is not a known
best move. The same thing goes for computer algorithms. They should learn
to learn the adversaries skill levels and gamesmanship and play accordingly.
Fido
Dave Chaloux
>While this is true (in my experience statements from CSLI often are), it
>might be more illuminating to consider the status quo. For persons playing
>the game right now it might be smart to think of chess as a classic game
>in the Neumann sense. That is, and depending on the understanding of your
>own and your adversaries levels of skill, it might be smart to introduce
>an element of randomness on those occasions when there is not a known
>best move. The same thing goes for computer algorithms. They should learn
>to learn the adversaries skill levels and gamesmanship and play accordingly.
This can be very true. The "Best" move can be the wrong move in some situations.
Take the case where you time handicap speed chess. I play my 9 year old son this
way adding 30 seconds to the time I have each time I lose and taking away 30
seconds each time I win. When you must win in 1 minute, the slow steady correct
method simply will not work against him. Gambits, wild sacs, etc. are the order
of the day. I can't count the number of times I have lost where I had an
overwhealming position that I wasn't able to cash in on quickly enough. Sure a
trap might be incorrect and even losing if he realizes what is going on but the
odds of that happening are pretty slim.
Sure you say but that is speed chess and we are talking "real" chess. Then how
about when you get in a time scramble at the end of the game. The "correct" move
might be so complicated you don't have time to deal with the complications.
Better to take the simplifying move that ensures you getting to the next limit.
How about when you enter an ending you are 99% sure you can grind out to a win
instead of entering a variation that probably leads to a mate in a dozen moves
for you?
How about when you open d4 instead of e4 just to shock the bejeebers out of
your opponent since you have never played d4 in a tournament.
Teri A Meyers
In article 6958, John Eisenberg responds to my article ("Chess is not
solvable", article 6947) as follows:
>
>
>I don't see what the problem is.
>There are only a finite number of possible chess games.
>Potentially, one could examine each one and determine
>the possible outcomes. Whether there is or is not a
>forced win for either side is theoretically computable.
In article 6962, Nordic Man writes, in the same vein:
>
>The general game theory idea is that chess is a FINITE game. There exist
>only a finite number of legal positions.
These arguments do not prove to me that chess is solvable, because it seems
obvious that even if a computer had a list containing every possible chess
position, this would not, in and of itself, constitute a complete evaluation
of all the nuances (ie, possible continuations and their evaluations) of each
and every one of those positions. Nothing less than such a complete
evaluation would constitute, to my mind, the "solution" to chess. The
existence of such a list would not even, in and of itself, constitute
any kind of evaluation at all (even in the crude sense of saying whether
any one of the positions in the list is a win or a draw). The whole problem,
as I see it, comes with the evaluation process, which I think will take one
on an infinite loop, as I described in my previous post. The languages of
the world are also composed of a finite number of words, but linguists tell
us that the number of sentences (or expressions) is infinite. To say that
"potentially, one could examine each one (of the positions) and determine
the possible outcomes" is to say something more than 'there are a finite
number of positions'. Just what assumptions are involved in that statemene,
are not entirely clear.
Jerry Meyers
Timothy Y. Chow
<There exists only a FINITE number of legal postions. Perhaps at some point a
<game can not move any further with perfect play, and then a draw by repitition
<occur eventially, or one must make a mistake. Make sense?
<If the game progresses farther and farther with nothing dynamic happening,
<then at some point the position will repeat itself three times, a draw.
For the record, threefold repetition and the fifty-move rule do not result
in an automatic draw---the draw must be CLAIMED (at least under USCF rules).
Hence technically a chess game can go on forever, so the theorem that either
chess is a draw or one side can force a win does not apply.
--
Tim Chow tyc...@math.mit.edu
Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
only 1 1/2 tons. ---Popular Mechanics, March 1949
Michael Schmahl [Black-Robe Mage]
> Anyways, if the starting position represents a balance (a "draw"
> from the perspective of game theorists), than it strikes me that the game
> can only be won if someone disturbs the balance (ie, makes mistakes).
It troubles me that you equate "disturbs the balance" with "makes mistakes".
There are many forms of balance. A key to the strategy of many chessplayers is to
upset the balance by making concessions in one area while strengthening the other
side. So while both players may be theoretically equal on the board, there is
still the possibility that one player can use his partial advantage in one area to
prove a win.
> However, when can the machine stop its analysis and declare the
> position conclusively a draw? However many ply it goes, it finds the
> position a draw, but how does it know it will not find the win by searching
> one ply further? It will have to search to infinity.
There are positions which are conclusively a draw. The simplest of these is King
vs. King. There is absolutely no way for either player to win this (sadly, most
computers don't recognize these types of draws -- many computers lose when they
are ahead materially but the position is a draw. The game is played, with the
computer avoiding three-time repetition, and eventually makes a worsening move,
thereby losing). There are also positions where the losing player forces a draw.
Any draw on the board (stalemate, for instance) can be considered the end point.
So infinite regression is not required.
> Jerry Meyers
Michael Schmahl [Black-Robe Mage]
But this problem is most likely intractable. The number of possible games is so
very large that it would take a vast amount of time to compute.
sven hauptfeld
>
>Here are my thoughts on this matter, which come more from philosophy than
>from game theory.
Game theory also comes from philosophy, but one that works.
> I operate on the assumption that from the initial position
>neither side can force a win.
No, no! That's not called philosophy, that's called religion. And what you
call 'assumption' is called a dogma. Philosophy must start from much more
general, abstract assumptions.
> This assumption may be mathematically unprovable
>but neither can it be disproved,
You are too religion-minded. This is not God we are discussing, it's a finite
human artefact, which can indeed be mathematically proved or disproved.
Your dogma might well be shown true (I bet it is!) but it must be shown, not
postulated.
> and moreover, I suspect that the vast
>majority of chessmasters would agree with it based on personal experience.
That's a well-known faulty argument. At one point vast majority of scholars
agreed that it was the Sun that orbited the Earth.
>(What's more, I suspect most chessmasters would reject the game theorists
>idea that the starting position is (or could be) a win for Black as sheer
>hogwash).
That is not an idea about chess. It is one of the three possibilities. The
idea of the theorem you are bashing is that those three are *only* possibi-
lities, which is quite profound regardless of how you feel about it.
>long as the balance is held, who can say there is any theoretical upper
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>limit to the number of possibilities (actual moves plus the vast horizon
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>of possible variants). A machine which conducts a search for a win X number
>of ply (whether 10 ply or a zillion) will never find it if the game is a
>draw from the position where it begins its analysis (such as before move
>one). However, when can the machine stop its analysis and declare the
>position conclusively a draw? However many ply it goes, it finds the
>position a draw, but how does it know it will not find the win by searching
>one ply further? It will have to search to infinity. If it ever did
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>get to infinity (which by definition is impossible), could it then supply
>us with "the solution" to chess in the form of the moves of the "ultimate
>draw" or "ultimate game"? Or would it not provide us with an infinite
>number of drawn games? One last thought comes out of this: since the
>number of possibilities in a chess game is by this analysis infinite, the
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>computer will reach the end of them and thus never play "the" perfect
>move. It may play well enough to hold the draw, but perhaps it will not
>play well enough to never make mistakes. And so, even in its most
>advanced state (which it will also never reach, because it will keep
>improving to infinity), it may still lose.
This is completely wrong. There is no infinity in chess. Number of positions
is finite. Number of ways to reach them is finite. Maximum length of the game
is finite (~5000 moves with both players cooperating, much less if they are
playing as opponents).
Sven
Rujith S DeSilva
There's a maximum length to a chess game, due to the 50-move rule. I think
it's something like 5000 moves. Technically, it's dependent on a player's
actually claiming the draw, but wouldn't even a computer claim the draw out of
sheer boredom? Anyway, there's no possibility of the computer losing the
game.
Rujith de Silva.
Carnegie-Mellon.
Cheong Yu
|> In article <1992Sep23.1...@CS.ORST.EDU> nym...@prism.CS.ORST.EDU (The Nordic Man) writes:
|> <There exists only a FINITE number of legal postions. Perhaps at some point a
|> <game can not move any further with perfect play, and then a draw by repitition
|> <occur eventially, or one must make a mistake. Make sense?
|> <If the game progresses farther and farther with nothing dynamic happening,
|> <then at some point the position will repeat itself three times, a draw.
|>
|> For the record, threefold repetition and the fifty-move rule do not result
|> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).
|> Hence technically a chess game can go on forever, so the theorem that either
|> chess is a draw or one side can force a win does not apply.
So under these rules, we will program the computer to always claim a
draw when a three-fold repetition or 50-move rule applies. Current
computer programs already do this, i.e. when there is Q + K vs. K, the
side with the material advantage can put the lone king in perpetual
check, but there are better moves that leads to checkmate. The
mythical, perfect computer would do the same thing, i.e. choose
forcing moves to lead to checkmate, and if there are none, be
satisfied with a draw rather than risk losing by making an inferior
move and hoping the opponent makes a bad move (this is the basic idea
behind the mini-max algorithm, i.e. minimizing your opponent's maximum
gain).
So under the USCF rules, a chess game with our mythical, perfect
computer *cannot* go on forever (because of the 50-move rule); the
theorem *does* applies; and chess *is* solvable.
|> --
|> Tim Chow tyc...@math.mit.edu
|> Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs
|> 30 tons, computers in the future may have only 1,000 vacuum tubes and weigh
|> only 1 1/2 tons. ---Popular Mechanics, March 1949
--
Cheong Yu | | (513) 865-7048
Mead Data Central | | Fax: (513) 865-1755
P.O. Box 933 | | k...@meaddata.com
Dayton, Ohio 45401 | | uunet!meaddata!kcy
Robert Hyatt
1. the game of chess *IS* solvable. That is, from the opening move, either
white wins, black wins (unlikely) or the perfect game is a draw. As a
scientist, I would call this "theoretically solvable" because, given a
fast enough computer it can be done..... The reason is that the game of
chess has a finite number of possible moves before a draw occurs, so one
side must either win or eventually reach a draw (50 move rule.)
2. Computers will never brute-force solve the game. Therefore, they will
*never* solve it. Searching partial trees won't cut it as you also eliminate
many paths that might disturb the final results. The biggest problem to
overcome are laws of physics that strictly limit the speed at which a computer
can operate and the physical size of the computer further limits it's speed.
To keep everyone happy, let me modify this to say "computers based on the
current technological level will never solve the game". This gives me an
out if if someone one day figures out how to quarks or whatever to make a
working circuit. Then the laws change a little.
3. The starting position is *not* equal. White has a distinct advantage in
that he is on move. Once white mates black, black can't respond and mate
white and "restore" the balance. Because of this, that tempo is worth some-
thing (unless the poster who mentioned zugszwang for white on the starting
board is correct.....)
Bob Hyatt
By the way, I think that the world champion is safe for several more years,
but he will eventually fall to a computer - and may even fall to a microcomputer
of the 21st century if they continue to improve. However, the game of chess
is safe.... we will never know if e4 wins or if g4 loses, etc.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
sven hauptfeld
>
>These arguments do not prove to me that chess is solvable, because it seems
>obvious that even if a computer had a list containing every possible chess
>position, this would not, in and of itself, constitute a complete evaluation
>of all the nuances (ie, possible continuations and their evaluations) of each
>and every one of those positions. Nothing less than such a complete
>evaluation would constitute, to my mind, the "solution" to chess. The
>existence of such a list would not even, in and of itself, constitute
>any kind of evaluation at all (even in the crude sense of saying whether
>any one of the positions in the list is a win or a draw).
All positions are either a completed win for one side (i.e. mate) or draw by
rules or on a path leading to one of the previous cases. Therefore, a complete
list of positions AND transitions (moves) from one position to another already
contains all evaluation information.
> The whole problem,
>as I see it, comes with the evaluation process, which I think will take one
>on an infinite loop, as I described in my previous post. The languages of
>the world are also composed of a finite number of words, but linguists tell
>us that the number of sentences (or expressions) is infinite.
That is because a sentence has unlimited length.
> To say that
>"potentially, one could examine each one (of the positions) and determine
>the possible outcomes" is to say something more than 'there are a finite
>number of positions'. Just what assumptions are involved in that statemene,
>are not entirely clear.
>
From all the postings that appeared so far, it should be clear by now.
Sven
sven hauptfeld
>
>For the record, threefold repetition and the fifty-move rule do not result
>in an automatic draw---the draw must be CLAIMED (at least under USCF rules).
>Hence technically a chess game can go on forever, so the theorem that either
>chess is a draw or one side can force a win does not apply.
>--
By the same token, mate doesn't result in automatic win. You mate your opponent
and don't realise it, he escapes with an illegal move and you don't realise it,
and you play on...
Absent-mindedness is assumed not to be part of the game, just like Turkish
bullets (there's a multi-stage problem based on a story in which some general
is playing chess during a battle with Turks, and every time he announces mate,
a bullet removes a piece, but he announces another mate, and so on...)
If you are looking for an algorithm for BEST play, you'll obviously claim
draw by repetition if it is to your advantage and will not allow it if it is
not.
Sven
Cheong Yu
|>
|> In article 6958, John Eisenberg responds to my article ("Chess is not
|> solvable", article 6947) as follows:
|> >
|> >
|> >I don't see what the problem is.
|> >There are only a finite number of possible chess games.
|> >Potentially, one could examine each one and determine
|> >the possible outcomes. Whether there is or is not a
|> >forced win for either side is theoretically computable.
|>
|>
|> In article 6962, Nordic Man writes, in the same vein:
|> >
|> >The general game theory idea is that chess is a FINITE game. There exist
|> >only a finite number of legal positions.
|>
|> These arguments do not prove to me that chess is solvable, because it seems
|> obvious that even if a computer had a list containing every possible chess
|> position, this would not, in and of itself, constitute a complete evaluation
|> of all the nuances (ie, possible continuations and their evaluations) of each
|> and every one of those positions. Nothing less than such a complete
|> evaluation would constitute, to my mind, the "solution" to chess. The
I think you would have to define "evaluation" more clearly. Do you
want the computer to give you a solution and *explain* its reasoning
as well? That's asking a little too much.
|> existence of such a list would not even, in and of itself, constitute
|> any kind of evaluation at all (even in the crude sense of saying whether
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
|> any one of the positions in the list is a win or a draw). The whole problem,
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This definition of "evaluation" is not crude at all, but very precise.
If given a position and perfect play on both sides, we can always
evaluate the current position as a forced win or a forced draw by
examining all the positions resulting from the current position.
By "perfect play", I mean the mini-max algorithm in game theory. I
don't have the definition at hand, but the basic idea of mini-max is
to minimize your opponent's maximal gain. For example, if given the
choice of making a move that will lead to 99 replies from your
opponent that are forced wins for me, but 1 reply that will allow my
opponent to force me to lose, under mini-max, I would not make that
move hoping my opponent doesn't see that 1 of out 100 replies that
would beat me.
|> as I see it, comes with the evaluation process, which I think will take one
|> on an infinite loop, as I described in my previous post. The languages of
^^^^^^^^^^^^^
Under the three-fold repetition and 50-move rule, a chess game is not
infinitely long.
|> the world are also composed of a finite number of words, but linguists tell
|> us that the number of sentences (or expressions) is infinite. To say that
^^^^^^^^^^^
However, if you impose the restriction that your sentences and
expressions must have finite length (analogous to the finite length of
a chess game), then the set of all such sentences is finite.
|> "potentially, one could examine each one (of the positions) and determine
|> the possible outcomes" is to say something more than 'there are a finite
|> number of positions'. Just what assumptions are involved in that statemene,
|> are not entirely clear.
The assumption is that the mini-max algorithm is being applied and the
normal rules of chess regarding repetition of positions is used.
Therefore, all possible chess positions can be generated and evaluated
as win or a draw at the leaf nodes of our game tree.
The point is that chess is theoretically solvable, but not in
practical amount of time.
|>
|>
|> Jerry Meyers
Tom Truscott
>*never* solve it. Searching partial trees won't cut it as you also eliminate
>many paths that might disturb the final results.
It is fair game to eliminate paths that *provably* do not disturb the final
results. And to terminate search on paths that have a provable result.
For example, many positions can be proven "drawn"
due to insufficient mating material.
In 100 years we (or some other intelligence) might develop a
sophisticated new "algebra" that allows us to calculate
the game-theoretic value of large classes of chess positions.
That would reduce the search space to the point that chess could
be solved in a practical amount of time.
Tom Truscott
Andrew Koenig
> For the record, threefold repetition and the fifty-move rule do not result
> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).
> Hence technically a chess game can go on forever, so the theorem that either
> chess is a draw or one side can force a win does not apply.
... except that there is only a finite number of possible positions anyway.
--
--Andrew Koenig
a...@europa.att.com
Joe Mattis
>These arguments do not prove to me that chess is solvable, because it seems
>obvious that even if a computer had a list containing every possible chess
>position,
Well, these arguments weren't talking about a *list* of positions, but
rather a *graph* that showed how positions were connected to each other
(a "connection" occurs when there is a legal move that can transform
one position into another). The arguments didn't mention this explicitly,
however, so your confusion is not surprising.
>this would not, in and of itself, constitute a complete evaluation
>of all the nuances (ie, possible continuations and their evaluations) of each
>and every one of those positions.
And that's *exactly* what this graph is...the possible continuations and
evaluation of every single position.
>Nothing less than such a complete
>evaluation would constitute, to my mind, the "solution" to chess.
Yep...that's why we've said that chess is solvable!
>[...] the evaluation process, which I think will take one
>on an infinite loop, as I described in my previous post.
Loops pose no theoretical limitation, since loops only kill you if you
perform the evaluation depth-first, which is unnecessary (although that's
the most practical way of proceeding).
For example, a graph for the "toy" example KQ vs KQ will contain loops, but
such a graph contains only 32,000,000 positions, which can be solved on a
workstation using the approach I described in my other message. Build the
graph, evaluate the final positions, cyclically evaluate the non-final
positions, and evaluate the "loop" (no forced mate) positions...then you
can lookup the evaluation of the initial position K(e1)Q(d1) vs K(e8)Q(d8).
>The languages of
>the world are also composed of a finite number of words, but linguists tell
>us that the number of sentences (or expressions) is infinite.
Yes...and I agree that, because of loops (reusing the same "word", in your
analogy), the number of possible chess games in infinite. However, this
merely says is that the number of ways of traversing the graph is infinite.
The *graph* *itself* is finite in size, and each node (position) can
be evaluated in finite time, as I described before.
If this is still unclear to you, I'm just down the street, so maybe we could
meet and discuss it in person. We might even (*gasp*) play an actual game.
-Joe Mattis ARPA: j...@isl1.ri.cmu.edu
UUCP: ...!ucbvax!isl1.ri.cmu.edu!j...@ucbvax.berkeley.edu
Joe Mattis
:
>Here are my thoughts on this matter, which come more from philosophy than
>from game theory.
Don't be put off by the term "game theory"...that's just an intimidating
phrase for some ideas that follow from common-sense reasoning.
>I operate on the assumption that from the initial position
>neither side can force a win.
Well, that assumption might be wrong (that's why you called it an
"assumption"), which makes the rest of your analysis invalid. But you still
raise some interesting points, so I'll address those.
>This assumption may be mathematically unprovable
>but neither can it be disproved,
Not quite true. The assumption is *practically* unprovable/undisprovable...
i.e. we cannot prove/disprove it in actual practice. However, the assumption
IS theoretically (mathematically) provable/disprovable...you just don't know
how such proofs work (yet!).
>Anyways, if the starting position represents a balance (a "draw" [...]),
>than it strikes me that the game
>can only be won if someone disturbs the balance (ie, makes mistakes).
Your statement captures the essence of the "minimax" algorithm for games.
Assign the following numeric evaluations to all possible final game positions:
Black to move (in check); no legal moves (checkmate): +1
Black to move (not in check); no legal moves (stalemate): 0
White to move (not in check); no legal moves (stalemate): 0
White to move (in check); no legal moves (checkmate): -1
Unless a player makes a mistake, White will always move in such a manner
so as to reach a position with the "maximum" possible evaluation, and Black
will move so as to reach a position with the "minimum" possible evaluation.
>[...] who can say there is any theoretical upper
>limit to the number of possibilities (actual moves plus the vast horizon
>of possible variants).
But there *is* one, since "vast" does not mean "infinite"! First, there's the
"50 move rule"...if no pawn was advanced or piece captured in the last 50
moves, either player may claim a draw. With 16 pawns (which can advance
6 ranks) and 30 pieces (which can be captured), games can last at most:
(16 * 6 + 30) * 50 = 6300 moves
before the "50 move rule" can be invoked for a draw.
But even if we ignore the "50 move rule", there are only a finite number
of possible positions. With 64 squares, which can be in one of (at most)
13 states (empty or occupied by W/B * KQRBNP), there are (at most) 13 ^ 64
board configurations. For each configuration, either W/B moves next (2),
each king can/cannot castle K/Q-side ((2*2)^2), and there are (at most)
9 "en passant" states (none or file abcdefgh). So there are (at most):
(13 ^ 64) * 2 * (4 ^ 2) * 9 ~= 5.6 * 10^73 positions
Each of these positions will either be a final position (with an evaluation
of +1, 0, or -1), or it will lead into a few of the 5.6 * 10^73 other
positions, based on the range of possible legal moves. Thus, all of chess
can be represented by a huge cyclic directed graph, where the nodes represent
positions, and the links represent legal moves. The task of "solving
chess" consists of determining evaluations for all of the unevaluated
(non-final) positions:
White to move, and can force checkmate: +1
White to move, and can force stalemate: 0
Black to move, and can force stalemate: 0
Black to move, and can force checkmate: -1
This is actually very simple! Cycle through the unevaluated positions,
performing the following computation:
IF White to move THEN
IF some move leads to a +1 position THEN
evaluate this position as +1
ELSE IF all moves lead to evaluated positions THEN
evaluate this position as the MAXIMUM of the
evaluations of all possible moves
ELSE this position remains unevaluated this cycle.
ELSE /* Black to move */
IF some move leads to a -1 position THEN
evaluate this position as -1
ELSE IF all moves lead to evaluated positions THEN
evaluate this position as the MINIMUM of the
evaluations of all possible moves
ELSE this position remains unevaluated this cycle.
Keep doing these cycles until an entire cycle is performed during which
no new evaluations were determined. The remaining unevaluated positions
represent positions where, due to repetition or lack of material, neither
side can force checkmate or stalemate. Evaluate all such positions as:
Neither side can force checkmate or stalemate: 0
Now, every possible chess position, including the initial position, has
an evaluation:
Black is checkmated, or White can force checkmate: +1
Neither side can force checkmate, thus both sides
can force a draw: 0
White is checkmated, or Black can force checkmate: -1
Theoretically, this evaluated graph can be constructed, so theoretically,
chess is solvable! But, practically, I'm confident that it will never
actually be solved.
>[...] However, when can the machine stop its analysis and declare the
>position conclusively a draw? [...] how does it know it will not find the
>win by searching one ply further? [...]
This is rather insightful for somebody who (apparently) doesn't know anything
about game theory and searching. What you've described is a serious concern
for computerized theorem provers...such programs never can be sure when to
give up and declare a theorem "unprovable", since applying "reduction" just
one more time might yield a completed proof.
But since chess positions are finite in number (unlike proofs), this concern
does not apply to chess.
edward.m.hummel
>1. the game of chess *IS* solvable. That is, from the opening move, either
>white wins, black wins (unlikely) or the perfect game is a draw.
OR the game has an "undetermined" result because the game never
ends. As long as we are talking nuances, I still see some hand-waving
in the arguments that an "optimal" player can be theoretically
developed. If the result of "solving" the game is that the game
has either a solution of "white draws or it is undetermined" then
I think it is not strictly solved. In any case, I don't see that
an "optimal" solution can be found. It will depend upon the choice
of the value of "undetermined" loops.
Teri A Meyers
My previous posts on "solvability" have generated more responses than I can
keep up with, but I will try to deal with a few of them.
In article 6997 Sven Hauptfeld chides me for my perspective as follows:
Me: "Here are my thoughts on the matter, which come more from philosophy
than game theory".
Him: "Game theory also comes from philosophy, but one that works."
Me: "I operate on the assumption that from the initial position neither
side can force a win."
Him: "No, no! That's not called philosophy, that's called religion. And
what you call 'assumption' is called a dogma. Philosophy must start
from much more general, abstract assumptions."
Obviously, Sven has a very particular version of philosophy in mind here;
certainly anyone versed in the history of philosophy will know that there
are many other ways to approach it than deduction from abstract principles.
If anything, people who insist that's the only way to go will find many other
philosophers who will accuse them of being dogmatic! All I wish to do in
working from the assumption that the initial position is dynamically
balanced (a "draw" to those who wish to assign a discrete value to my
concept of 'dynamic balance'), is to begin my chess philosophizing from
an experiential starting point (drawing on my background as a chess master),
rather than from a game theory starting point. Certainly from within
philosophy the experiential starting point is a well established approach,
though it is only one of many approaches. One can attempt to deny its
validity (as Sven later did by pointing out that at one point scholars
believed the Sun orbited the Earth, or refering to optical illusions), but
then one can also point to certain absurdities that a purely deductive
approach can lead one to; in this instance, the idea that the initial
position in chess may turn out to be a win for Black. Logically this is
true, but experientially it is a canard. If, in fact, chess were
solvable, and it were just to happen, just by chance, that as Sven
himself writes:
"Your dogma might well be shown true (I bet it is!), but it must be shown,
not postulated",
then how will the game theorist account for it? He can only say 'that's
just how it turned out,' or something of the sort. For him, it must be
shown (empirically, I suppose, since Sven says not postulated); experience
cannot count because it might be an illusion.
The truth is, experience sometimes can produce illusions, but most of the
time, it doesn't (unless we are Bobby Fischer?!), and even when it does
produce illusions, most of the time we can discover it, either on our own
or with the help of others (ie., intersubjective experience). At any rate,
I am not saying that the game theory approach to chess is not useful or
valid, I only wish to claim it is not the only useful and valid approach.
Also, I disagree with some of its conclusions. I agree there are a finite
number of legal positions. I disagree with the claim that a list of these
positions constitutes a solution to chess. Two people responded to this:
Sven, in article 7063, and Cheong Yu in article 7068.
Sven wrote "All positions are either a completed win for one side (ie. mate)
or draw by rules or on a path leading to one of the previous cases. Therefore
a complete list of positions AND transitions (moves) from one position to
another already contains all evaluation information." Well, a list of all
games possible from the initial position will contain wins, losses, and draws.
In order to separate the wheat from the chaff, you will have to make use of
some type of evaluation process not contained in your list.
Cheong Yu responds more directly to my definition of what a 'solution' to
chess would entail. First he quotes me as saying "even if a computer had
a list containing every possible chess position, this would not, in and of
itself, constitute a complete evaluation of all the nuances (ie, possible
continuations and their evaluations) of each and every one of those positions.
Nothing less than such a complete evaluation would constitute, to my mind,
the "solution" to chess."
He responds: "...Do you want the computer to give you a solution and
*explain* its reasoning as well? That's asking a little
too much."
Perhaps it is asking "too much"--too much for anyone to actually do, but
not too much to require anyone claiming to have the 'solution' to chess
to provide. Some people have argued that the computer may eventually
provide us with a forced win for White in 40 or 20 moves (or even several
different ways to force a win -- what does it matter if one is 25 moves
and another 26--mathematically, a win is win is a win)--but unless the
machine can tell us everything there is to know about all the immortal
games of chess it will not have "solved" chess in any complete sense.
Suppose (at the end of time) it finishes its analyses and tells us, Chess
is a draw. Would that be the 'solution'? It would certainly answer the
game theorist's question whether it is a win for white, black, or draw.
For myself and those like me who want to know something about that
beautiful little world that stirs our emotions, it would be pale comfort.
Jerry Meyers
(I speak for myself only, and not my wife Teri, whose ignorance of chess
is its own form of bliss).
Craig Presson
Here are my thoughts on this matter, which come more from philosophy than
from game theory. I operate on the assumption that from the initial position
neither side can force a win.
So, in your philosophy, assuming the conclusion is not a fallacy?
Maybe you _should_ go back and try game theory, then :-)
-- Craig Presson
Bradley S Watson
>>These arguments do not prove to me that chess is solvable, because it seems
>>obvious that even if a computer had a list containing every possible chess
>>position,
>>of all the nuances (ie, possible continuations and their evaluations) of each
>>and every one of those positions.
Joe Mathis responds:
>Well, these arguments weren't talking about a *list* of positions, but
>rather a *graph* that showed how positions were connected to each other
>(a "connection" occurs when there is a legal move that can transform
>one position into another). The arguments didn't mention this explicitly,
>however, so your confusion is not surprising.
If you use rectograde analysis, you don't need to show all the connections.
All you need to do is mark down whether the position is a white win or not.
You start by finding all the positions in your database where black is mated.
These are white wins. You then look through all the positions with white
to move and see if any white can make a move that would result in one of the
won positions you've previously found. If so, then that position can also
be classified as a win for white. Then look at the positions with black
to move. If ALL black's moves result in positions you've classified as won for white,
then that position is also marked as a white win. Continue this procedure until
you can't find any more white wins. Then find the mirror image of all these
white wins with the opposite side on move. These are all the black wins. The
remaining unclassified positions are drawn.
This was how that KBR vs KNN endgame was solved about a year ago.
andy
If no one has already done this already, could someone list
a book that demonstrates that chess is theoretically solvable
so we can stop wasting time on this subject due to all the
people who don't have enough common sense (or whatever it takes)
to figure it out for themselves. It's getting ridiculous
reading all those articles.
I don't mind discussions on the practical part (computer
limitations, speculations on how long it would take to
solve chess, etc.), but CHESS DOES HAVE A SOLUTION!!!!! Just
because it may take 10^100 years to find it, doesn't mean
there isn't one!
Maybe we should stop using the word "solvable," because some
people seem to use that term to basically say "If the universe
comes to an end before we can solve chess, it's not solvable."
-Andy
andy
For all intents and purposes, the three-fold repetition and 50-move
rules DO constitute and automatic draw. Consider the two scenarios:
1) Chess is a game where either white can force mate at move 1 OR
one where black can force mate at move 1.
As soon as one of the rules comes up, the side that cannot force mate
will immediately claim the draw to avoid mate. Of course this would
never occur in this case (scenario 1 in effect) unless the side that
can force mate lets it happen. Otherwise scenario 1 would not have
been true in the first place. Hmm. This was a little more
complicated to explain than I thought it would be.
2) Chess is a game where either side can force a draw.
The draw rules don't matter since if the two sides continue playing,
the game will still be a draw.
-Andy
Ralf Stephan
> >only a finite number of legal positions.
>
> These arguments do not prove to me that chess is solvable, because it seems
> obvious that even if a computer had a list containing every possible chess
> position, this would not, in and of itself, constitute a complete evaluation
> of all the nuances (ie, possible continuations and their evaluations) of each
> and every one of those positions. Nothing less than such a complete
> evaluation would constitute, to my mind, the "solution" to chess. The
> existence of such a list would not even, in and of itself, constitute
> any kind of evaluation at all (even in the crude sense of saying whether
> any one of the positions in the list is a win or a draw).
Completely wrong. You never heard about perfect endgames or retrograde
analysis.. If a computer has the power to manage all possible positions,
it can build a game tree up from the simplest endgames to the starting
position and thus decide if it is won/draw/lost.
Think of it: If position A (with black to move) is proven won for white,
then all positions where white can make a move that leads to position A
are won for white, and so on...
--ralf
sven hauptfeld
>
>In article 6997 Sven Hauptfeld chides me for my perspective as follows:
>
>Me: "Here are my thoughts on the matter, which come more from philosophy
> than game theory".
>
>Him: "Game theory also comes from philosophy, but one that works."
>
>Me: "I operate on the assumption that from the initial position neither
> side can force a win."
>
>Him: "No, no! That's not called philosophy, that's called religion. And
> what you call 'assumption' is called a dogma. Philosophy must start
> from much more general, abstract assumptions."
>
>Obviously, Sven has a very particular version of philosophy in mind here;
>certainly anyone versed in the history of philosophy will know that there
>are many other ways to approach it than deduction from abstract principles.
"Deduction from abstract principles" is quite different from what I said.
Anyway, starting from such a particular and arbitrary statement as "starting
position is a draw" is certainly contrary to the spirit of philosophy, math
or science.
> All I wish to do in
>working from the assumption that the initial position is dynamically
>balanced (a "draw" to those who wish to assign a discrete value to my
>concept of 'dynamic balance'), is to begin my chess philosophizing from
>an experiential starting point (drawing on my background as a chess master),
You failed. There is no experimental evidence that the initial position is
ballanced, on the contrary, tournament results favor white by almost 6-4,
so from the experimental point of view (of which I am far more qualified to
speak than of the philosophical), the assumption you based your whole
philosophy on has a very high likelihood of being false.
BTW, one doesn't have to be a master to see that the initial position is only
*statically* ballanced, while *dynamically* white is a tempo up.
>then one can also point to certain absurdities that a purely deductive
>approach can lead one to; in this instance, the idea that the initial
>position in chess may turn out to be a win for Black.
The theorem around which this discussion developed says *nothing* of the kind.
It says that possibilities *other than* forced win for white, forced draw and
forced win for black (in other words, the infamous 'undeternined value'
positions, which keep popping out in so many postings) are *not* possible.
> Logically this is
>true, but experientially it is a canard.
I've just shown that this is irrelevant, but even 'experimentally' it is well
justified. Many games of the same class actually favor black. While this is
highly unlikely to be true for chess, that is just a particular example.
>"Your dogma might well be shown true (I bet it is!), but it must be shown,
>not postulated",
>
>then how will the game theorist account for it? He can only say 'that's
>just how it turned out,' or something of the sort. For him, it must be
>shown (empirically, I suppose, since Sven says not postulated); experience
>cannot count because it might be an illusion.
This is nonsense. Postulated means 'not derived'. There is no dogma in game
theory nor is there a 'postulate' that chess is solvable. It is a theorem,
i.e. it is derived from more general statements. (Yes, eventually it is
derived from postulates. But not postulates like "initial position is
ballanced" but those like "one is greather than zero". See the difference?)
>I am not saying that the game theory approach to chess is not useful or
>valid, I only wish to claim it is not the only useful and valid approach.
For the issues it addresses, it is. If you disagree, don't bug me, but
construct a concurring theory. (Friendly advice: don't try.)
>Also, I disagree with some of its conclusions. I agree there are a finite
>number of legal positions. I disagree with the claim that a list of these
>positions constitutes a solution to chess. Two people responded to this:
You are really obnoxious. This is not a 'conclusion' of the game theory, nor
has anybody stated anything like that in this discussion.
>Sven wrote "All positions are either a completed win for one side (ie. mate)
>or draw by rules or on a path leading to one of the previous cases. Therefore
>a complete list of positions AND transitions (moves) from one position to
>another already contains all evaluation information." Well, a list of all
>games possible from the initial position will contain wins, losses, and draws.
>In order to separate the wheat from the chaff, you will have to make use of
>some type of evaluation process not contained in your list.
You only need 'evaluation' if you are not certain of the outcome. If you have
a graph of all paths among all positions, you can trivially evaluate every
path by inspection - does it end in 1, 1/2 or 0?
>but unless the
>machine can tell us everything there is to know about all the immortal
>games of chess it will not have "solved" chess in any complete sense.
First of all, you seem to impose an entirely different definition of "solved"
than the one being discussed (which had been clearly stated), which makes
your argument invalid. But even so, we *would* know everything there is to
know about all immortal games (as well as about not-so-immortal ones), i.e.
we would know exactly which moves were mistakes and which were exceptionally
good.
>Suppose (at the end of time) it finishes its analyses and tells us, Chess
>is a draw. Would that be the 'solution'? It would certainly answer the
>game theorist's question whether it is a win for white, black, or draw.
>For myself and those like me who want to know something about that
>beautiful little world that stirs our emotions, it would be pale comfort.
What is your point? Let me use a loose - but illustrative - analogy: I *know*
that I'll die. Therefore, the final result of my life is 'solved'. Does that
make my life any less interesting?
Sven
Joe Mattis
>Joe Mattis (not Mathis!) responds:
>>Well, these arguments weren't talking about a *list* of positions, but
>>rather a *graph* that showed how positions were connected to each other
>
True, explicit connections aren't being maintained, but connections *are*
being derived "on the fly" (and then forgotten) as part of the steps:
>...[if white] can make a move that would result in one of the [+1] positions
and
>...If ALL black's moves result in [+1] positions...
So mathematically, you're still working with a graph. I thought it was
important to emphasize these implicit links between the evaluated positions.
Anyway, thanks for providing a concise description of "retrograde analysis".
I'd been wondered exactly how it worked!
edward.m.hummel
>Keep doing these cycles until an entire cycle is performed during which
>no new evaluations were determined. The remaining unevaluated positions
>represent positions where, due to repetition or lack of material, neither
>side can force checkmate or stalemate. Evaluate all such positions as:
> Neither side can force checkmate or stalemate: 0
You have to make an assumption in order to assign this a value. The
method you are using is searching for "best play" by looking for
the best possible value for downstream (one ply hence) positions.
When that turns out to depend upon the value of the node itself
you are ARBITRARILY assigning the value zero. This does not
consistitute a proof that the best play leads to a value of
+1, 0. or -1 for the initial position.
Consider the following trivial graph tree. It has two nodes
A and B. B is a final position and has value zero. The linkages
are two arcs. The first goes from A to B. The second goes from
A to A. So, what value do we give to node A? It should have the best
of the two possibilities (A or B). We know B is zero, but we
don't know A. According to your argument, we must assign
the value zero, because there can be no other outcome. I think
this is using an additional assumption.
(Note that when A is life and B is death, we find a way to choose
life -- and are comfortable with the evaluation that it is better
than death.)
Anyway, I'm awaiting a proof.
Donald A. Varvel
many times and neither player claims a draw leave me puzzled.
A min-max algorithm considering a line in which either player can
claim a draw will assign it the value "draw". Why? Because neither
player can force a better result. The value of the position is a
draw. The best White can do against best play is a draw and the
best Black can do against best play is a draw.
Only by changing the rules of chess and giving a continuing game
a value greater than a draw can this be avoided, and there is no
such rule. Even in that case, the value of the unfinished game
would have to be greater than a draw *for both players*. And finally,
assuming "unfinished" has a value greater than "draw", even in
positions where neither player can force a win (which can be
identified by min-max) the value is "unfinished" and analysis may
stop. There wouldn't be a lot of drawn games under that strange
assumption, though. Most draws are "I don't have winning chances
so let's stop playing".
Is all of this really so hard to understand?
-- Don Varvel (var...@cs.utexas.edu)
Joe Mattis
>In article <Bv3t3K...@cs.cmu.edu> ja...@cs.cmu.edu (Joe Mattis) writes:
>>represent positions where, due to repetition or lack of material, neither
>>side can force checkmate or stalemate. Evaluate all such positions as:
>> Neither side can force checkmate or stalemate: 0
>
>You have to make an assumption in order to assign this a value.
Not at all. This evaluation, which seems so capricious to you, is *only*
applied to positions where (with best play) neither player can forcibly reach
+1 or -1...that's why these positions remained unassigned! Now, a completed
chess game must end with a White win (+1), a Black win (-1), or a draw (0).
Since it's impossible to reach +1 or -1, the only possible completion (with
best play) is 0. Therefore, IF THE GAME EVER ENDS from one of these
positions (with best play), it must end in a draw.
Note that I haven't proved that such games must end...indeed, they might not.
But I *have* proved that the only possible result from such positions (with
best play) is a draw. If it turns out that the initial position is such a
position, that would be enough (in and of itself) to "solve" chess. After
all, if we determined that neither White nor Black could forcibly checkmate
the other (with best play), that would certainly answer the question that
started this whole discussion, the intent of which was (paraphrasing):
Which is correct? (a) White can forcibly win.
(b) Black can forcibly win.
(c) Neither can forcibly win.
>When [a downstream value] turns out to depend upon the value of the node
>itself you are ARBITRARILY assigning the value zero.
Untrue! After all, *most* positions "depend" on the value of the node
itself, since most positions can lead to back to themselves (e.g. players can
usually shuffle their kings endlessly). Yet many such positions get +1 or -1
evaluations. For example, the potential for king-shuffling in
K(a1)Q(a2) vs K(h1) doesn't alter the fact that the position is +1 (a win
for White). Furthermore, there is no chance that Black could forcibly
enter a "loop" from a +1 position. Positions are only assigned +1
if White can forcibly avoid all loops (as in the KQvsK example).
The only positions that get evaluated as 0 by the passage you quoted above
are those where no +1 or -1 positions can be forcibly reached (with best
play). (Note that this handles all of the "drawn by fiat" positions (KvsK,
KvsKNN, etc) without resorting to special rules.)
>Consider the following trivial graph tree. It has two nodes
>A and B. B is a final position and has value zero. The linkages
>are two arcs. The first goes from A to B. The second goes from
>A to A. So, what value do we give to node A? It should have the best
>of the two possibilities (A or B). We know B is zero, but we
>don't know A.
But we do know *something* about A...we know that neither player can forcibly
reach +1 or -1! Therefore, we know that from this position (with best play)
IF THE GAME EVER ENDS, it must end in a draw.
>According to your argument, we must assign
>the value zero, because there can be no other outcome. I think
>this is using an additional assumption.
Not if "0" means "Neither can forcibly win."
So, I've proved that it's theoretically possible to answer the question
above as (a) (b) or (c). The fact that (c) implies that a game might
never end (with best play) is just as uninteresting and irrelevant from the
initial position as it is from KQvsKQ...either way, it's a drawn position
(with best play).
If you can't understand the proof or its consequences, you'll have to ask
someone else for help.
edward.m.hummel
>Note that I haven't proved that such games must end...indeed, they
>might not. But I *have* proved that the only possible result from
>such positions (with best play) is a draw. If it turns out that
>the initial position is such a position, that would be enough (in
>and of itself) to "solve" chess. After all, if we determined that
>neither White nor Black could forcibly checkmate
>the other (with best play), that would certainly answer the question that
>started this whole discussion, the intent of which was (paraphrasing):
> Which is correct? (a) White can forcibly win.
> (b) Black can forcibly win.
> (c) Neither can forcibly win.
Joe, you missed the turn. I have never been challenging Z's result.
Instead, I have been adressing the question of "What is the outcome
(if any) of a game which proceeds with "best play" by both sides?"
The answer could be: (a) White wins,
(b) Black wins,
(c) The game is drawn, or
(d) None of the above, i.e., "best play"
leads to a game with no outcome.
The rules assign values for wins (1), losses (0) and draws (.5).
The analysis to answer this question is very similar to the
analysis to answer the question you mention, BUT it turns out
to require some additional information. To many people, this is
somewhat bothersome.
>If you can't understand the proof or its consequences, you'll have
>to ask someone else for help.
I understand the proof you have laid out (I always did). If you
don't understand the issue I have raised, please feel free to post
a followup or contact me by email. I'll try to explain it more
clearly.
Ed Hummel
Joe Mattis
In article <cek8TIW2A...@pitt.edu> tas...@pitt.edu (Teri A Meyers) writes
:
>Here are my thoughts on this matter, which come more from philosophy than
>from game theory.
Don't be put off by the term "game theory"...that's just an intimidating
phrase for some ideas that follow from common-sense reasoning.
>I operate on the assumption that from the initial position
>neither side can force a win.
Well, that assumption might be wrong (that's why you called it an
Keep doing these cycles until an entire cycle is performed during which
no new evaluations were determined. The remaining unevaluated positions
represent positions where, due to repetition or lack of material, neither
side can force checkmate or stalemate. Evaluate all such positions as:
Neither side can force checkmate or stalemate: 0
Now, every possible chess position, including the initial position, has
an evaluation:
Black is checkmated, or White can force checkmate: +1
Neither side can force checkmate, thus both sides
can force a draw: 0
White is checkmated, or Black can force checkmate: -1
Theoretically, this evaluated graph can be constructed, so theoretically,
chess is solvable! But, practically, I'm confident that it will never
actually be solved.
>[...] However, when can the machine stop its analysis and declare the
>position conclusively a draw? [...] how does it know it will not find the
>win by searching one ply further? [...]
This is rather insightful for somebody who (apparently) doesn't know anything
about game theory and searching. What you've described is a serious concern
for computerized theorem provers...such programs never can be sure when to
give up and declare a theorem "unprovable", since applying "reduction" just
one more time might yield a completed proof.
But since chess positions are finite in number (unlike proofs), this concern
does not apply to chess.
-Joe Mattis ARPA: j...@isl1.ri.cmu.edu
UUCP: ...!ucbvax!isl1.ri.cmu.edu!j...@ucbvax.berkeley.edu
* Origin: The Electronic Mailbox (1:348/7.0)
Tom Truscott
Tom Truscott
* Origin: The Electronic Mailbox (1:348/7.0)
edward.m.hummel
* Origin: The Electronic Mailbox (1:348/7.0)
Andrew Koenig
Reply-To: a...@alice.UUCP ()
In article <1992Sep24....@galois.mit.edu> tyc...@riesz.mit.edu (Timothy Y. Chow) writes:
> For the record, threefold repetition and the fifty-move rule do not result
> in an automatic draw---the draw must be CLAIMED (at least under USCF rules).
> Hence technically a chess game can go on forever, so the theorem that either
> chess is a draw or one side can force a win does not apply.
... except that there is only a finite number of possible positions anyway.
--
--Andrew Koenig
a...@europa.att.com
* Origin: The Electronic Mailbox (1:348/7.0)
Jim Gillogly
>If no one has already done this already, could someone list
>a book that demonstrates that chess is theoretically solvable
>so we can stop wasting time on this subject due to all the
Good idea! Go to the source:
Zermelo, Ernst, U"ber eine Anwendung der Mengenlehre auf die Theorie des
Schachspiels, Proc. Fifth International Congress of Mathematicians,
(Cambridge, 1912), 501-504.
Enough already!
--
Jim Gillogly
j...@rand.org
-Broadband Network Maintenance
Ok, the last word on chess solvabilty.
1. IF chess is solvable it would have been solved.
2. Chess has not been solved.
3. Therefore to date chess is not solvable.
Only the solution will prove this wrong, so if you don't agree please post
the solution to chess for all to read. ;-)
Don Schiewer
>
> of possible variants). A machine which conducts a search for a win X number
> of ply (whether 10 ply or a zillion) will never find it if the game is a
> draw from the position where it begins its analysis (such as before move
> one). However, when can the machine stop its analysis and declare the
> position conclusively a draw? However many ply it goes, it finds the
> position a draw, but how does it know it will not find the win by searching
> one ply further? It will have to search to infinity. If it ever did
> get to infinity (which by definition is impossible), could it then supply
This cannot happen because there are theoretical limits on the number of
moves which can be made in chess (ie. 50 move rule, redundant moves, etc.)
When (IF!) a computer follows ALL moves to a draw condition (easily tested)
then it will pick a move at random.
It will continue to do this hoping an error is made on the other side.
--
Don Schiewer | Internet schi...@pa881a.inland.com | Onward Great
Inland Steel | UUCP: !uucp!pa881a.inland!schiewer | Stream...
sven hauptfeld
Same logical pattern (albeit without the same bad grammar):
1. If I were mortal, I would be dead.
2. I am not dead.
3. Therefore to date I am not mortal.
There are two mistakes. One is logical, but not too relevant: a new condition
("to date"), not in the premises, appears in the conclusion. The other is
logically fine, but factually wrong: the premise 1. is false.
Sven