| |
Main
Date: 09 Sep 2005 22:54:34
From: entropy
Subject: solve for chess
|
In Matiyasevich's book on Hilbert's 10th problem, there was a passage on
how it was undecidable for a result of a game to be determined from an
arbitrary game. Is it still possible for a unavoidable algorithm/gambit
for a win/loss/stalemat for either black or white to be determined. If
so, what is computational complexity of solving chess?
--
entropy
| Free Avlerchess Glass Chess Set - Find out how you can get a free glass chess set from us.
|
| |
Date: 09 Sep 2005 22:25:23
From:
Subject: Re: solve for chess
|
Of course, strictly speaking chess can be solved. It is a finite game,
with a specific starting point and a limited set of moves that can be
made from any position. Therefore, it is POSSIBLE to determine best
play for any position by analyzing the tree of all possible moves for
that position all the way out to their game-ending state, exactly like
endgame databases do now.
However, EGDBs are at this time only created for up to 6 pieces on the
board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
It's taken about 6-8 years just to go from 5 to 6 pieces as being the
"state of the art", because of the necessary computation time and
storage requirements.
How long will it take to get to 32 pieces? Even if progress is linear
(and it won't be), at best it's going to take close to 200 years before
chess is solved!
jm
|
| | |
Date: 10 Sep 2005 10:23:58
From: Guy Macon
Subject: Re: solve for chess
|
Content-Transfer-Encoding: 8Bit
[email protected] wrote:
>However, EGDBs are at this time only created for up to 6 pieces on the
>board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
>It's taken about 6-8 years just to go from 5 to 6 pieces as being the
>"state of the art", because of the necessary computation time and
>storage requirements.
I wasn't aware of the entire 6 man Nalimov tablebases being completed.
Do you have a source and a hard figure for how many bytes it takes
to hold all of the 3-man, 4-man, 5-man and 6-man Nalimov tablebases?
>How long will it take to get to 32 pieces? Even if progress is linear
>(and it won't be), at best it's going to take close to 200 years before
>chess is solved!
Complete 3 man Nalimov Tablebase...80 kB (measured)
Complete 3+4 man Nalimov Tablebases...30 MB (measured)
Complete 3+4+5 man Nalimov Tablebases...7.5 GB (measured)
Complete 3+4+5+6 man Nalimov Tablebases...1-2 TB (estimated)
Complete 3+4+5+6+7 man Nalimov Tablebases...200-600 TB (estimated)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180 PB (estimated)
...
Complete 3+4+5+...+30+31+32 man Nalimov Tatablebases...????
I welcome any estimates that are better than the ones above,
and I especially welcome anyone who has the courage to give me
an estimate to replace the ??? above. I would also very much
like some data on how long it takes/took to generate each set.
--
Guy Macon <http://www.guymacon.com/ >
------------------------------------------------------------
BTW, Here is a handy reference for expressing large numbers:
*************************************************************
SHORT VERSION:
k kilo- 1.0E+3 x1,000 Thousand(US,UK)
M mega- 1.0E+6 x1,000,000 Million (US,UK)
G giga- 1.0E+9 x1,000,000,000 Billion(US)
T tera- 1.0E+12 x1,000,000,000,000 Trillion(US), Billion(UK)
P peta- 1.0E+15 x1,000,000,000,000,000 Quadrillion(US)
E exa- 1.0E+18 x1,000,000,000,000,000,000 Quintillion(US), Trillion(UK)
Z zetta- 1.0E+21 x1,000,000,000,000,000,000,000 Sextillion(US)
Y yotta- 1.0E+24 x1,000,000,000,000,000,000,000,000 Septillion(US), Quadrillion(UK)
Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[ http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answer/culture.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]
LONG VERSION:
*************************************************************
NAMED POWERS OF TEN - US VERSION
--------------------------------
- N/A 1.0E+36 N/A 1 000 000 000 000 000 000 000 000000 000 000 000
- N/A 1.0E+33 decillion 1 000 000 000 000 000 000 000 000000 000 000
- N/A 1.0E+30 N/A 1 000 000 000 000 000 000 000 000000 000
- N/A 1.0E+27 illion 1 000 000 000 000 000 000 000 000000
Y yotta- 1.0E+24 septillion 1 000 000 000 000 000 000 000 000
Z zetta- 1.0E+21 sextillion 1 000 000 000 000 000 000 000
E exa- 1.0E+18 quintillion 1 000 000 000 000 000 000
P peta- 1.0E+15 quadrillion 1 000 000 000 000 000
T tera- 1.0E+12 trillion 1 000 000 000 000
G giga- 1.0E+9 billion 1 000 000 000
M mega- 1.0E+6 million 1 000 000
k kilo- 1.0E+3 thousand 1 000
h hecto- 1.0E+2 hundred 100
da deca- 1.0E+1 ten 10
d deci- 1.0E-1 tenth 0.1
c centi- 1.0E-2 hundredth 0.01
m milli- 1.0E-3 thousandth 0.001
� micro- 1.0E-6 millionth 0.000 001
n nano- 1.0E-9 billionth 0.000 000 001
p pico- 1.0E-12 trillionth 0.000 000 000 001
f femto- 1.0E-15 quadrillionth 0.000 000 000 000 001
a atto- 1.0E-18 quintillionth 0.000 000 000 000 000 001
z zepto- 1.0E-21 sextillionth 0.000 000 000 000 000 000 001
y yo- 1.0E-24 septillionth 0.000 000 000 000 000 000 000 001
- N/A 1.0E-27 illionth 0.000 000 000 000 000 000 000 000 001
- N/A 1.0E-30 N/A 0.000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-33 decillionth 0.000 000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-36 N/A 0.000 000 000 000 000 000 000 000 000 000 000 001
Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[ http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answer/culture.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]
*************************************************************
NAMED POWERS OF TEN - UK VERSION
--------------------------------
- N/A 1.0E+36 sextillion 1 000 000 000 000 000 000 000 000000 000 000 000
- N/A 1.0E+33 N/A 1 000 000 000 000 000 000 000 000000 000 000
- N/A 1.0E+30 quintillion 1 000 000 000 000 000 000 000 000000 000
- N/A 1.0E+27 N/A 1 000 000 000 000 000 000 000 000000
Y yotta- 1.0E+24 quadrillion 1 000 000 000 000 000 000 000 000
Z zetta- 1.0E+21 N/A 1 000 000 000 000 000 000 000
E exa- 1.0E+18 trillion 1 000 000 000 000 000 000
P peta- 1.0E+15 N/A 1 000 000 000 000 000
T tera- 1.0E+12 billion 1 000 000 000 000
G giga- 1.0E+9 milliard 1 000 000 000
M mega- 1.0E+6 million 1 000 000
k kilo- 1.0E+3 thousand 1 000
h hecto- 1.0E+2 hundred 100
da deca- 1.0E+1 ten 10
d deci- 1.0E-1 tenth 0.1
c centi- 1.0E-2 hundredth 0.01
m milli- 1.0E-3 thousandth 0.001
� micro- 1.0E-6 millionth 0.000 001
n nano- 1.0E-9 milliardh 0.000 000 001
p pico- 1.0E-12 billionthh 0.000 000 000 001
f femto- 1.0E-15 N/A 0.000 000 000 000 001
a atto- 1.0E-18 trillionth 0.000 000 000 000 000 001
z zepto- 1.0E-21 N/A 0.000 000 000 000 000 000 001
y yo- 1.0E-24 quadrillionth 0.000 000 000 000 000 000 000 001
- N/A 1.0E-27 N/A 0.000 000 000 000 000 000 000 000 001
- N/A 1.0E-30 quintillionth 0.000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-33 N/A 0.000 000 000 000 000 000 000 000 000 000 001
- N/A 1.0E-36 sextillionth 0.000 000 000 000 000 000 000 000 000 000 000 001
Note: vendeka, xenna, xenno, and vendeko are bogus.
Before you try using them, please read these pages:
[ http://home.att.net/~numericana/answer/units.htm#prefix ]
[ http://home.att.net/~numericana/answer/culture.htm#zillion ]
[ http://physics.nist.gov/cuu/Units/prefixes.html ]
[ http://physics.nist.gov/cuu/Units/binary.html ]
*************************************************************
--
Guy Macon <http://www.guymacon.com/ >
|
| | | |
Date: 12 Sep 2005 13:54:25
From: David Richerby
Subject: Re: solve for chess
|
Guy Macon <http://www.guymacon.com/ > wrote:
> T tera- 1.0E+12 billion 1 000 000 000 000
> G giga- 1.0E+9 milliard 1 000 000 000
In the UK, it's becoming much more common to use `billion' for 10^9, as in
the US.
Dave.
--
David Richerby Lead Sushi (TM): it's like a raw fish
www.chiark.greenend.org.uk/~davidr/ that weighs a ton!
|
| | |
Date: 12 Sep 2005 08:31:12
From: Simon Krahnke
Subject: Re: solve for chess
|
* <[email protected] > (04:55) schrieb:
> [email protected] wrote:
>
>> You're wrong, and it's very simple to prove.
>>
>> But, to start with the definition of "best play" that you asked for:
>> -- For any position that can be shown as won by the side to move, it is
>> the move(s) that result in the shortest mate.
>
> Can't you read? I'm not talking about forced mates.
But it's all about forced mates.
> What if the position can't be "shown as won"? Most positions in chess
> are open to win, loss, or draw, and many others are open to two of
> these:
No there aren't. Every position in chess is either a forced win for
white or for black, or a forced draw.
> Even in a position permitting forced mate, while it is true that any
> move leading to mate is good, there may be more than one move sequence
> which results in mate in a minimum number of moves. Which is the
> "best" and why?
Any is. This is silly. No one demands there is a single best move in
every position. Of course there may be many perfect games of chess. But
they all end the same.
> And you have yet to meaningfully define this even for forced mate
> positions, much less for arbitrary positions! To say that chess is
> "solved", incidentally, means that there is an algorithm for winning
> from the starting position.
No, it doesn't mean that.
> There is not, for either side.
There is none yet, and may never be. But theoretically it is possible.
mfg, simon .... l
|
| | |
Date: 13 Sep 2005 02:56:55
From: Simon Krahnke
Subject: Re: solve for chess
|
* <[email protected] > (18:38) schrieb:
> Simon Krahnke wrote:
>> * <[email protected]> (04:55) schrieb:
>>> What if the position can't be "shown as won"? Most positions in chess
>>> are open to win, loss, or draw, and many others are open to two of
>>> these:
>>
>> No there aren't. Every position in chess is either a forced win for
>> white or for black, or a forced draw.
>
> It isn't. Take a look at the very first position, the starting
> position. Is that a forced mate for White, a forced mate for Black, or
> a forced draw? (Answer, none of the above.)
It's a forced win for black. Yes, I can prove that, but won't.
> You don't seem to know what "forced mate" or "forced draw" means.
Well, let's check if you know.
> It doesn't mean that the game will eventually end in a mate for
> *someone* or else in a draw. If White has a forced mate, and Black is
> subject to forced mate, it means that, in the current position, every
> legal move possible to Black can be followed by a move by White which
> leads to Black being mated, and that this is true for every position
> subsequent to this. If, on the other hand, Black is free to choose, in
> a given position, from moves which do not satisfy these conditions, he
> is not subject to a forced mate.
Whoa, you not only know it, you dare to publish it.
> Never mind "best" moves -- it's easy to see that in most chess
> positions, there are not even provably good moves.
There are.
> There are two kinds of moves in chess commonly called "good":
>
> (1) Provably good moves. These include, for example, moves necessary
> to execute a forced mate.
And that includes at least one move in every position that is no forced
win for the opposite color.
> (2) Heuristically good moves.
These are irrelevant when talking about solving chess. Heuristics can
only help on solving chess faster.
> These are based on heuristic, or rule of thumb evaluations which use
> *relatively short term* algorithms weighing gains in material and/or
> position. By "relatively short term" I mean evaluations which end with
> some future position which is not end-of-game.
A Heuristic might as well be perfect.
> Most positions in chess are ambiguous in that they permit a win, loss,
> or draw; in these cases, knowledge of game outcome depends upon the
> future move sequence and is not strictly inherent to the current
> position;
Of course it is.
> and half of the future move-sequence is determined by your
> opponent. Thus, the data necessary to evaluate the position in any
> provable manner is missing; it is unknown and unknowable if your
> opponent is free to choose among alternatives that lead to *different*
> game outcomes.
That's just a finite number and I could look at all of them.
> In most chess positions, therefore, there are no provably good moves,
> but only heuristically good moves, which may not be objectively good
> moves.
What exactly are these magic unsolvable positions and how do identify
them?
>>> Even in a position permitting forced mate, while it is true that any
>>> move leading to mate is good, there may be more than one move sequence
>>> which results in mate in a minimum number of moves. Which is the
>>> "best" and why?
>>
>> Any is. This is silly. No one demands there is a single best move in
>> every position. Of course there may be many perfect games of chess. But
>> they all end the same.
>
> Evidently you don't know what the word "best" means. To say that there
> is "more than one best move" in a given position is an abuse of
> language. If there is a "best" move there is only one; otherwise,
> there are merely good moves or winning moves.
I said it's silly.
>>> And you have yet to meaningfully define this even for forced mate
>>> positions, much less for arbitrary positions! To say that chess is
>>> "solved", incidentally, means that there is an algorithm for winning
>>> from the starting position.
>>
>> No, it doesn't mean that.
>
> Certainly it does.
Since chess is a forced win for black, it's obvious there is no such
algorithm. None the less, proving this would solve chess.
> No, theoretically it is impossible, because the starting position of
> chess does not provide sufficient data, in and of itself, for such an
> algorithm; only after the future move sequence has caused the game to
> reach a point where provably good moves (e.g., a forced mate) exists,
> is an algorithm possible; and as long as the future move sequence is
> half-determined by the moves of an opponent which are unknown and
> unknowable in advance, that data is not available.
So there's data in solved positions that's not in the starting position?
mfg, simon .... l
|
| | |
Date: 18 Sep 2005 20:24:12
From: Martin Moller Pedersen
Subject: Re: solve for chess
|
In <[email protected] > [email protected] writes:
>Of course, strictly speaking chess can be solved. It is a finite game,
>with a specific starting point and a limited set of moves that can be
>made from any position. Therefore, it is POSSIBLE to determine best
>play for any position by analyzing the tree of all possible moves for
>that position all the way out to their game-ending state, exactly like
>endgame databases do now.
>However, EGDBs are at this time only created for up to 6 pieces on the
>board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
>It's taken about 6-8 years just to go from 5 to 6 pieces as being the
>"state of the art", because of the necessary computation time and
>storage requirements.
>How long will it take to get to 32 pieces? Even if progress is linear
>(and it won't be), at best it's going to take close to 200 years before
>chess is solved!
And I don't think it is possible to store the results without using all
atoms in the universe.
/Martin
|
| | | |
Date: 19 Sep 2005 07:28:19
From: Guy Macon
Subject: Re: solve for chess
|
Martin Moller Pedersen wrote:
>
>[email protected] writes:
>
>>Of course, strictly speaking chess can be solved. It is a finite game,
>>with a specific starting point and a limited set of moves that can be
>>made from any position. Therefore, it is POSSIBLE to determine best
>>play for any position by analyzing the tree of all possible moves for
>>that position all the way out to their game-ending state, exactly like
>>endgame databases do now.
>
>>However, EGDBs are at this time only created for up to 6 pieces on the
>>board. It's a VERY LONG WAY until we have the answer for all 32 pieces.
>>It's taken about 6-8 years just to go from 5 to 6 pieces as being the
>>"state of the art", because of the necessary computation time and
>>storage requirements.
>
>>How long will it take to get to 32 pieces? Even if progress is linear
>>(and it won't be), at best it's going to take close to 200 years before
>>chess is solved!
>
>And I don't think it is possible to store the results without using all
>atoms in the universe.
You appear to be assuming that one can only store one bit of information
per atom - a rather dubious assumption. A one kilogram storage unit
that occupies one liter of space can store a maximum of 2^1031 bits by
encoding information in the spin, speed and direction of the particles
inside the storage unit.
Or you can simply build a quaunntum computer with a couple of hundred
qubits of storage.
Do a web search on "Quantum Computing" and "Black Hole Computing"...
|
| | | | |
Date: 19 Sep 2005 09:19:06
From: David Richerby
Subject: Re: solve for chess
|
Guy Macon <http://www.guymacon.com/ > wrote:
> Martin Moller Pedersen wrote:
>> And I don't think it is possible to store the results without using all
>> atoms in the universe.
>
> You appear to be assuming that one can only store one bit of
> information per atom - a rather dubious assumption. A one kilogram
> storage unit that occupies one liter of space can store a maximum of
> 2^1031 bits by encoding information in the spin, speed and direction of
> the particles inside the storage unit.
The key word here may well be `maximum'...
> Or you can simply build a quaunntum computer with a couple of hundred
> qubits of storage.
This must be some strange new meaning of the word `simply' that I wasn't
previously aware of.
Dave.
--
David Richerby Swiss Homicidal Apple (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a tasty fruit but it wants to kill
you and it's made in Switzerland!
|
| | | | | |
Date: 19 Sep 2005 13:43:35
From: Guy Macon
Subject: Re: solve for chess
|
David Richerby wrote:
>
>Guy Macon <http://www.guymacon.com/> wrote:
>
>> Martin Moller Pedersen wrote:
>>> And I don't think it is possible to store the results without using all
>>> atoms in the universe.
>>
>> You appear to be assuming that one can only store one bit of
>> information per atom - a rather dubious assumption. A one kilogram
>> storage unit that occupies one liter of space can store a maximum of
>> 2^1031 bits by encoding information in the spin, speed and direction of
>> the particles inside the storage unit.
>
>The key word here may well be `maximum'...
>
>> Or you can simply build a quaunntum computer with a couple of hundred
>> qubits of storage.
>
>This must be some strange new meaning of the word `simply' that I wasn't
>previously aware of.
(Laughs)
I use the Dilbert Pointy-haired Boss definition of
"Simple"; If I don't know how to do it, it must be easy!
:)
|
| |
Date: 10 Sep 2005 09:57:15
From:
Subject: Re: solve for chess
|
> I wasn't aware of the entire 6 man Nalimov tablebases being completed.
> Do you have a source and a hard figure for how many bytes it takes
> to hold all of the 3-man, 4-man, 5-man and 6-man Nalimov tablebases?
IIRC, the entire 6-man tablebases in De Koning format were completed
quite some time ago (meaning, possibly as much as a year ago) by Marc
Bourzutschky. I do not know how much space they take up, but I have a
vague memory of somebody saying that it was around 1.7 TB. I don't even
know if he kept all of them, as his main goal was to produce the most
interesting ones to verify certain well-known studies.
I'm pretty sure that Nalimov has personally completed all of the TBs in
his format, but hasn't published them all yet.
Guy Haworth, who keeps abreast of these things, might know more of the
particulars.
jm
|
| |
Date: 12 Sep 2005 03:42:58
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>Tic-tac-toe is solved, unlike chess. There is a way
>to win, always, provided you make the first move.
Then you should have no problem beating me!
1 2 3
|
| |
Date: 11 Sep 2005 19:57:55
From:
Subject: Re: solve for chess
|
Guy Macon wrote:
> You are wrong. Chess can be solved, given enough computing power and
> storage. (The computing power and storage required might be to large
> to fit in the universe, but that's another discussion...)
>
> Here is a simple exercise that may help you to understand
> your error:
>
> Make a simple paper-and-pencil list that allows perfect play of the
> game of tic-tac-toe. You should easily be able to make a "if in
> this position make this move" list that results in perfect play.
> You will have to make two lists so you can play X or O.
<snip >
Guy Macon, you are a silly troll. Tic-tac-toe is solved, unlike chess.
There is a way to win, always, provided you make the first move.
Mark Adkins
[email protected]
|
| | |
Date: 12 Sep 2005 14:33:57
From: David Richerby
Subject: Re: solve for chess
|
<[email protected] > wrote:
> Guy Macon, you are a silly troll.
You're starting to look very silly yourself, Mark, but I'll be charitable
and assume you're not trolling yourself. Somebody once said that one can
afford to be obnoxious or wrong but not both at once.
> Tic-tac-toe is solved, unlike chess.
Correct. It sounds to me like you're trying to say that we can't solve
chess because we don't know how to play it perfectly. But `solving chess'
means exactly the same thing as `knowing how to play chess perfectly'!
(Unless we mean ultra-weakly solving chess, but the whole point of ultra-
weak solution is that you don't need to know how to play perfectly.)
> There is a way to win, always, provided you make the first move.
No, both players can force a draw after any initial move, though it is
possible to make a losing second move.
Dave.
--
David Richerby Carnivorous Whisky (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ single-malt whisky but it eats flesh!
|
| |
Date: 11 Sep 2005 19:55:47
From:
Subject: Re: solve for chess
|
[email protected] wrote:
> You're wrong, and it's very simple to prove.
>
> But, to start with the definition of "best play" that you asked for:
> -- For any position that can be shown as won by the side to move, it is
> the move(s) that result in the shortest mate.
Can't you read? I'm not talking about forced mates. What if the
position can't be "shown as won"? Most positions in chess are open to
win, loss, or draw, and many others are open to two of these: the
result in such cases depends upon the subsequent sequence of moves, not
upon the current position, and that sequence is unknowable since it
requires knowledge not only of your own plans but also of how the other
player will move.
Even in a position permitting forced mate, while it is true that any
move leading to mate is good, there may be more than one move sequence
which results in mate in a minimum number of moves. Which is the
"best" and why?
> Additionally, I never said that "solving chess" meant "finding a move
> that wins". Your clarification in your follow-up post seems to imply
> that this is something that I stated. But it is not true. I'm only
> talking about finding "best play" from the starting position -- not a
> WIN from the starting position.
And you have yet to meaningfully define this even for forced mate
positions, much less for arbitrary positions! To say that chess is
"solved", incidentally, means that there is an algorithm for winning
from the starting position. There is not, for either side.
Mark Adkins
[email protected]
|
| | |
Date: 12 Sep 2005 14:12:13
From: David Richerby
Subject: Re: solve for chess
|
<[email protected] > wrote:
>[email protected] wrote:
>> You're wrong, and it's very simple to prove.
>>
>> But, to start with the definition of "best play" that you asked for:
>> -- For any position that can be shown as won by the side to move, it is
>> the move(s) that result in the shortest mate.
>
> Can't you read? I'm not talking about forced mates. What if the
> position can't be "shown as won"?
Chess is a finite two-player game of perfect information. It follows that
every position is either a forced win for White, a forced win for Black or
is a draw with best play.
> Most positions in chess are open to win, loss, or draw, and many others
> are open to two of these: the result in such cases depends upon the
> subsequent sequence of moves, not upon the current position, and that
> sequence is unknowable since it requires knowledge not only of your own
> plans but also of how the other player will move.
But there are only finitely many such plans and sequences of moves so one
could, in principle, check each one of them and find the best.
> Even in a position permitting forced mate, while it is true that any
> move leading to mate is good, there may be more than one move sequence
> which results in mate in a minimum number of moves. Which is the
> "best" and why?
There is no requirement for a unique best move. If you had to choose
between them, you could always use some arbitrary criterion such as the
one with the alphabetically first notation.
> To say that chess is "solved", incidentally, means that there is an
> algorithm for winning from the starting position.
It means no such thing! There are several definitions of `solved'. A
game is `ultra-weakly solved' if we know the theoretical result from the
initial position (e.g., `chess is a win for White'), is `weakly solved' if
we know how to achieve the theoretical result from the initial position
and is `strongly solved' if we know how to achieve the theoretical result
from every legal position. When people talk about `solving chess', they
usually mean one of the last two.
Dave.
--
David Richerby Devil Watch (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ precision chronometer that's possessed
by Satan!
|
| | | |
Date: 17 Sep 2005 19:54:17
From: Simon Krahnke
Subject: Re: solve for chess
|
* <[email protected] > (03:50) schrieb:
> I am still waiting to see proof that chess is "solvable".
Well here it is: Do an standard Alpha-Beta search on the initial
position with unbounded depth and without any forward pruning.
Since in this configuration all values will be mate or draw, the final
result must also be mate or draw.
That will answer the question if it's a forced mate for white or black
or forced draw, and give an optimal move for white on the initial
position.
For a more complete solution just repeat the algorithm on other positions.
> Most of the participants in this thread who maintain that it is keep
> throwing out terms like "optimum move" even when I have clearly shown
> that in the general case, any partial game sequence is repeated in
> numerous total game sequences having different game outcomes.
Too bad you already confessed you know what �forced mate� means.
Any of the pre-final optimal moves in a forced mate tree do only
force a mate if I carry on doing only optimal moves.
mfg, simon .... l
|
| | | |
Date: 18 Sep 2005 12:25:05
From: Simon Krahnke
Subject: Re: solve for chess
|
* <[email protected] > (02:30) schrieb:
> Simon Krahnke wrote:
>> * <[email protected]> (03:50) schrieb:
>>
>> > I am still waiting to see proof that chess is "solvable".
>>
>> Well here it is: Do an standard Alpha-Beta search on the initial
>> position with unbounded depth and without any forward pruning.
>>
>> Since in this configuration all values will be mate or draw, the final
>> result must also be mate or draw.
>>
>> That will answer the question if it's a forced mate for white or black
>> or forced draw, and give an optimal move for white on the initial
>> position.
>>
>> For a more complete solution just repeat the algorithm on other positions.
>
> Sorry, but this strikes me as the most awful obfuscatory gobbledygook.
That is: You understand a word, or what?
> You haven't at all proven that one side or the other can, by his first
> move, guarantee one of these outcomes regardless of the moves of the
> other side.
Sure I haven't. You got to read the game theory stuff yourself.
> So far as I can see, you've merely stated (quite
> inaccurately) that any game of chess must either result in a win by one
> side OR the other, or in a draw. Well, so what?
Well, look above. It's all a conclusion from this simple fact. I know
games that can just go on forever, no matter how hard I try to win or
lose. But chess is finite given optimal play.
mfg, simon .... l
|
| | | |
Date: 18 Sep 2005 09:29:48
From: Guy Macon
Subject: Re: solve for chess
|
Simon Krahnke wrote:
>
>* <[email protected]> (03:50) schrieb:
>
>> I am still waiting to see proof that chess is "solvable".
>
>Well here it is: Do an standard Alpha-Beta search on the initial
>position with unbounded depth and without any forward pruning.
>
>Since in this configuration all values will be mate or draw, the final
>result must also be mate or draw.
>
>That will answer the question if it's a forced mate for white or black
>or forced draw, and give an optimal move for white on the initial
>position.
>
>For a more complete solution just repeat the algorithm on other positions.
That is one of the most brilliant bits of technical writing that
I have seen in quite a long time. Clear, concise, and quite simple.
To bad that the reply that you will get from the [email protected]
will consist of name-calling, with no attempt to understand what you
just wrote.
|
| |
Date: 12 Sep 2005 02:19:38
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>It isn't possible, for two reasons: first, because there is no
>meaningful definition of "best play" for *every* position; and second,
>because even deciding what a "good" move is, in any provable sense,
>requires full advance knowledge of the response of one's opponent under
>every possible variation from that position onward; this is not
>forthcoming from human players, and even chess engines may employ
>partial move randomization.
You are wrong. Chess can be solved, given enough computing power and
storage. (The computing power and storage required might be to large
to fit in the universe, but that's another discussion...)
Here is a simple exercise that may help you to understand
your error:
Make a simple paper-and-pencil list that allows perfect play of the
game of tic-tac-toe. You should easily be able to make a "if in
this position make this move" list that results in perfect play.
You will have to make two lists so you can play X or O.
Note that there is indeed a meaningful definition of "best play"
for every possible tic-tac-toe position.
Note that you do *not* need "full advance knowledge of the
response of one's opponent under every possible variation from
that position onward." All you need to know is the present
position of the tic-tac-toe board and what move to make in
that position.
Note that it doesn't matter whether your opponent makes random
moves, and it doesn't even matter whether he has his own list
that allows him to play perfectly. You aren't considering any
of his future moves. You are just looking up the current
position on the list and making the move it tells you to make.
Note that it doesn't even take any brains to generate your list.
It can be generated by a stupid brute-force program with ease.
This being Usenet, There is at least a 90% chance that you will
either withdraw without further comment or defend your position.
If you choose to defend it, please explain the difference between
tic-tac-toe and chess other than the size and complexity of the
move tree being much larger in chess.
Also, please consider the fact that there exists a list such as
I described above for every possible chess position having six or
fewer men on the board. Please explain why someone with enough
computing power and storage couldn't do the same for seven or eight
man positions. Then explain why someone with enough computing power
and storage couldn't do the same for one particular thirty-two man
position.
--
Guy Macon <http://www.guymacon.com/ >
|
| |
Date: 11 Sep 2005 16:51:38
From:
Subject: Re: solve for chess
|
[email protected] wrote:
> [email protected] wrote:
> > Of course, strictly speaking chess can be solved. It is a finite game,
> > with a specific starting point and a limited set of moves that can be
> > made from any position. Therefore, it is POSSIBLE to determine best
> > play for any position by analyzing the tree of all possible moves for
> > that position all the way out to their game-ending state, exactly like
> > endgame databases do now.
>
> It isn't possible, for two reasons: first, because there is no
> meaningful definition of "best play" for *every* position; and second,
> because even deciding what a "good" move is, in any provable sense,
> requires full advance knowledge of the response of one's opponent under
> every possible variation from that position onward; this is not
> forthcoming from human players, and even chess engines may employ
> partial move randomization. A move in chess is frequently only
> potentially good or bad, depending upon the subsequent sequence, and
> some moves that are bad in the short term may end up being good, or
> even decisive, in the long term, in ways that are unpredictable at the
> time they are made (because the subsequent move sequence is unknown and
> unknowable). Even the blunder of a piece may result in the
> repositioning of other pieces in a way that permits the blunderer to
> force mate in some future position, i.e., a blunder may inadvertently
> place the right piece in the right place at what (in a future position)
> will be the right time; this is equivalent to a very long range
> combination, except that it is inadvertent.
>
> Let the position to be analyzed be the opening of the game from the
> starting position, before White moves. There is no "best play" for
> White. What criterion does one use for "best"? To achieve checkmate
> in the shortest number of moves? The shortest mate possible is not a
> static figure because subsequent moves alter the position and thus the
> figure, and it is not generally possible ahead of time to know which
> moves will be made by one's opponent; therefore nothing can be proven
> except provisionally, and the conditions upon which this provisional
> proof are predicated may change with subsequent moves. Furthermore,
> there are many ways to checkmate in, say, 20 moves. Which of them is
> "best"? Even in the case where a forced mate exists from a given
> position, more than one forced mate of the same (shortest) number of
> moves may be possible from that position. Furthermore, not every
> position is guaranteed to result in a forced mate, and there may also
> be many ways to draw in cases where it is possible to force a draw --
> not to mention many ways to lose in cases where it is possible to lose!
>
> For all of these reasons, it is not possible to "solve" chess.
>
> Mark Adkins
> [email protected]
You're wrong, and it's very simple to prove.
But, to start with the definition of "best play" that you asked for:
-- For any position that can be shown as won by the side to move, it is
the move(s) that result in the shortest mate.
-- For any position that is drawn, it is any move that does not turn
the position into a lost game.
-- For any position that can as lost by the side to move, it is the
move(s) that result in forcing the opponent to take the longest path to
mate.
This is exactly how DTM endgame databases define it, and they work very
well for that purpose.
But your argument about requiring "full advance knowledge of the
response of one's opponent" is completely beside the point. If you have
a won position, it doesn't matter what your opponent plays as long as
you still have a won position after your move. The same is true for a
drawn position. You also say that "a move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence", but
if there are 6 pieces left on the board, and I have all 6-man EGDB
files, there is no "potential" about it -- the move is not only either
"good or bad", but is actually "best play or not best play". The entire
set of legal moves for every position involving 6 men HAS been
determined to be either "best play or not best play".
Additionally, I never said that "solving chess" meant "finding a move
that wins". Your clarification in your follow-up post seems to imply
that this is something that I stated. But it is not true. I'm only
talking about finding "best play" from the starting position -- not a
WIN from the starting position.
So, if it has been already done for 6 pieces, why not 7, or 8, or 16 or
32? The exact same mechanism that has SOLVED chess for 6 pieces can
solve it for a larger number of pieces. And once it is done for all 32
pieces, (and it "only" needs to be solved from the starting position),
chess will be solved.
Whether the final result of chess is that it is drawn or won for White
remains to be seen.
jm
p.s. And, yes, I'm aware of all the technical issues involving
computing and storing the necessary data to get to this solution.
That's not part of this discussion. In a mathematical sense, but not
necessarily in a practical sense, chess can be solved.
|
| |
Date: 11 Sep 2005 14:53:33
From:
Subject: Re: solve for chess
|
P.S. To further clarify what I have written below: It is not even
theoretically possible to solve chess, no matter what the computing
power involved. Until a position is reached where a forced mate is
guaranteed, there is no move sequence proven to win; and because such
positions are always in advance of the starting position, a computer
will never be able to determine whether it (or its opponent) can force
mate until *after* some unknown (and unknowable) future move of its
opponent places the board in such a position.
[email protected] wrote:
> [email protected] wrote:
> > Of course, strictly speaking chess can be solved. It is a finite game,
> > with a specific starting point and a limited set of moves that can be
> > made from any position. Therefore, it is POSSIBLE to determine best
> > play for any position by analyzing the tree of all possible moves for
> > that position all the way out to their game-ending state, exactly like
> > endgame databases do now.
>
> It isn't possible, for two reasons: first, because there is no
> meaningful definition of "best play" for *every* position; and second,
> because even deciding what a "good" move is, in any provable sense,
> requires full advance knowledge of the response of one's opponent under
> every possible variation from that position onward; this is not
> forthcoming from human players, and even chess engines may employ
> partial move randomization. A move in chess is frequently only
> potentially good or bad, depending upon the subsequent sequence, and
> some moves that are bad in the short term may end up being good, or
> even decisive, in the long term, in ways that are unpredictable at the
> time they are made (because the subsequent move sequence is unknown and
> unknowable). Even the blunder of a piece may result in the
> repositioning of other pieces in a way that permits the blunderer to
> force mate in some future position, i.e., a blunder may inadvertently
> place the right piece in the right place at what (in a future position)
> will be the right time; this is equivalent to a very long range
> combination, except that it is inadvertent.
>
> Let the position to be analyzed be the opening of the game from the
> starting position, before White moves. There is no "best play" for
> White. What criterion does one use for "best"? To achieve checkmate
> in the shortest number of moves? The shortest mate possible is not a
> static figure because subsequent moves alter the position and thus the
> figure, and it is not generally possible ahead of time to know which
> moves will be made by one's opponent; therefore nothing can be proven
> except provisionally, and the conditions upon which this provisional
> proof are predicated may change with subsequent moves. Furthermore,
> there are many ways to checkmate in, say, 20 moves. Which of them is
> "best"? Even in the case where a forced mate exists from a given
> position, more than one forced mate of the same (shortest) number of
> moves may be possible from that position. Furthermore, not every
> position is guaranteed to result in a forced mate, and there may also
> be many ways to draw in cases where it is possible to force a draw --
> not to mention many ways to lose in cases where it is possible to lose!
>
> For all of these reasons, it is not possible to "solve" chess.
>
> Mark Adkins
> [email protected]
|
| |
Date: 11 Sep 2005 14:32:26
From:
Subject: Re: solve for chess
|
[email protected] wrote:
> Of course, strictly speaking chess can be solved. It is a finite game,
> with a specific starting point and a limited set of moves that can be
> made from any position. Therefore, it is POSSIBLE to determine best
> play for any position by analyzing the tree of all possible moves for
> that position all the way out to their game-ending state, exactly like
> endgame databases do now.
It isn't possible, for two reasons: first, because there is no
meaningful definition of "best play" for *every* position; and second,
because even deciding what a "good" move is, in any provable sense,
requires full advance knowledge of the response of one's opponent under
every possible variation from that position onward; this is not
forthcoming from human players, and even chess engines may employ
partial move randomization. A move in chess is frequently only
potentially good or bad, depending upon the subsequent sequence, and
some moves that are bad in the short term may end up being good, or
even decisive, in the long term, in ways that are unpredictable at the
time they are made (because the subsequent move sequence is unknown and
unknowable). Even the blunder of a piece may result in the
repositioning of other pieces in a way that permits the blunderer to
force mate in some future position, i.e., a blunder may inadvertently
place the right piece in the right place at what (in a future position)
will be the right time; this is equivalent to a very long range
combination, except that it is inadvertent.
Let the position to be analyzed be the opening of the game from the
starting position, before White moves. There is no "best play" for
White. What criterion does one use for "best"? To achieve checkmate
in the shortest number of moves? The shortest mate possible is not a
static figure because subsequent moves alter the position and thus the
figure, and it is not generally possible ahead of time to know which
moves will be made by one's opponent; therefore nothing can be proven
except provisionally, and the conditions upon which this provisional
proof are predicated may change with subsequent moves. Furthermore,
there are many ways to checkmate in, say, 20 moves. Which of them is
"best"? Even in the case where a forced mate exists from a given
position, more than one forced mate of the same (shortest) number of
moves may be possible from that position. Furthermore, not every
position is guaranteed to result in a forced mate, and there may also
be many ways to draw in cases where it is possible to force a draw --
not to mention many ways to lose in cases where it is possible to lose!
For all of these reasons, it is not possible to "solve" chess.
Mark Adkins
[email protected]
|
| |
Date: 12 Sep 2005 04:10:29
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>
>Guy Macon wrote:
>
>> You are wrong. Chess can be solved, given enough computing power and
>> storage. (The computing power and storage required might be to large
>> to fit in the universe, but that's another discussion...)
>
><snip>
>
>Guy Macon, you are a silly troll.
"When anyone resorts to personal attacks, it is almost always
because they are losing an argument." -The Happy Heretic
>Tic-tac-toe is solved, unlike chess. There is a way to win, always,
>provided you make the first move.
I suggest that, having gotten the *WRONG* answer for tic-tac-toe
("There is a way to win, always, provided you make the first move"
is wrong, wrong. wrong!), that you abandon all attempts to figure
out chess. See http://en.wikipedia.org/wiki/Tic-tac-toe
I note that you were unable to answer the simple question I asked.
Evasion noted. Here is that question that you cannot answer again:
There exists a "if in this position make this move" list that allows
perfect play for every possible chess position having six or fewer men
on the board. Again I ask you to please explain why someone with enough
computing power and storage couldn't do the same for all seven or eight
man positions. Again I ask you to then explain why someone with enough
computing power and storage couldn't do the same for one particular
thirty-two man position.
If you refuse to answer again, I will take that as an admission that you
cannot answer the question and as an admission that you are wrong.
Now, are you going to address the question I just asked (for the second
time) in a calm, rational manner, or are you going to engage in silly
name calling? My killfile is awaiting your answer. After you fail to
beat me a tic-tac-toe, of course. I predict that you will resign.
--
Guy Macon <http://www.guymacon.com/ >
|
| |
Date: 12 Sep 2005 22:26:02
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>
>David Richerby wrote:
>> Chess is a finite two-player game of perfect information. It follows that
>> every position is either a forced win for White, a forced win for Black or
>> is a draw with best play.
>
>It isn't a game of perfect information.
Learn what "a game of perfect information" is and then we can talk.
|
| |
Date: 12 Sep 2005 12:20:09
From:
Subject: Re: solve for chess
|
> It isn't even a finite game.
Ok, you're clearly delusional, extremely bad at math, or (most likely)
just a troll.
To say that chess is not a finite game is so laughably and
fundamentally wrong means that there is absolutely no point in arguing
with you any more.
*plonk*
jm
|
| |
Date: 12 Sep 2005 18:39:18
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>I have never been a Tic-Tac-Toe afficionado, but I do recall, with
>reasonable certainty, reading and (and discussing with others) a way to
>win at the game provided one moves first. Now, all evidence of such an
>algorithm seems to have vanished. This does not surprise me very much,
>considering the fact that this is a pseudo-reality which seems to
>undergo a variety of fundamental "editing" so that (for example) events
>which occurred in the past vanish from record; also, I am used to
>dealing with pseudo-sentients like yourself, who lie compulsively and
>habitually, from a pathological contrarianism. My recollections of the
>Tic-Tac-Toe algorithm are from school days, many decades ago, and it
>might, possibly, have been erroneous: I do not recall exhaustively
>analyzing it, but it made sense to me at the time; now, however, there
>seems to be no recoverable record of it -- the closest thing being the
>assertion of a winning algorithm for 3-D Tic-Tac-Toe. I routinely see
>advertisements for "new release" movies which I KNOW, with absolute
>rather than merely reasonable certainty, have been out before, years
>ago, though all archival evidence of this disappears by the time the
>events reoccur. The same is true for many newspaper stories, magazine
>covers, and obituaries. As for Tic-Tac-Toe, I really don't care enough
>to try to reconstruct what was once widely published as a winning
>method. Perhaps it never was what it claimed to be: but something
>claiming to be this certainly held nearly universal circulation.
So you refuse to admit that there is no winning method for tic-tac-toe,
and you prefer to believe that somehow archival evidence of something
as well-publicized as a movie release disappears than to believe the
obvious - that you are delusional. Alas, you aren't one of those nice
delusional people who are charming and fiendly, but are instead one of
those nasty delusional people who engage in unprovoked personal attacks
on anyone who questions your version of "reality."
Here are some definitions that you should be aware of:
-----------------------------------------------------------------------
Kook
[Usenet; originally and more formally, `net.kook'] Term used to
describe a regular poster who continually posts messages with
no apparent grounding in reality. Different from a troll, which
implies a sort of sly wink on the part of a poster who knows
better, kooks really believe what they write, to the extent that
they believe anything.
The kook trademark is paranoia and grandiosity. Kooks will often
build up elaborate imaginary support structures, fake corporations
and the like, and continue to act as if those things are real even
after their falsity has been documented in public.
While they may appear harmless, and are usually filtered out by
the other regular participants in a newsgroup of mailing list,
they can still cause problems because the necessity for these
measures is not immediately apparent to newcomers; there are
several instances on record, for example, of journalists writing
stories with quotes from kooks who caught them unaware.
See also Troll
-----------------------------------------------------------------------
Troll
1. v.,n. [From the Usenet group alt.folklore.urban] To utter a posting
on Usenet designed to attract predictable responses or flames; or, the
post itself. Derives from the phrase "trolling for newbies" which in
turn comes from mainstream "trolling", a style of fishing in which one
trails bait through a likely spot hoping for a bite.
The well-constructed troll is a post that induces lots of newbies and
flamers to make themselves look even more clueless than they already do,
while subtly conveying to the more savvy and experienced that it is in
fact a deliberate troll. If you don't fall for the joke, you get to be
in on it. See also YHBT.
2. n. An individual who chronically trolls in sense 1; regularly posts
specious arguments, flames or personal attacks to a newsgroup,
discussion list, or in email for no other purpose than to annoy someone
or disrupt a discussion. Trolls are recognizable by the fact that they
have no real interest in learning about the topic at hand - they simply
want to utter flame bait. Like the ugly creatures they are named after,
they exhibit no redeeming characteristics, and as such, they are
recognized as a lower form of life on the net, as in, "Oh, ignore him,
he's just a troll."
Some people claim that the troll (sense 1) is properly a narrower
category than flame bait, that a troll is categorized by containing
some assertion that is wrong but not overtly controversial.
The use of `troll' in either sense is a live metaphor that readily
produces elaborations and combining forms. For example, one not
infrequently sees the warning "Do not feed the troll" as part of
a followup to troll postings.
See also Kook.
-----------------------------------------------------------------------
Killfile
[Usenet; very common] (alt. `KILL file') Per-user file(s) used by some
Usenet reading programs (originally Larry Wall's rn(1)) to discard
summarily (without presenting for reading) articles matching some
particularly uninteresting (or unwanted) patterns of subject, author,
or other header lines. Thus to add a person (or subject) to one's kill
file is to arrange for that person to be ignored by one's newsreader in
future. By extension, it may be used for a decision to ignore the
person or subject in other media.
See also plonk.
-----------------------------------------------------------------------
Plonk
[Usenet: possibly influenced by British slang `plonk' for cheap booze,
or `plonker' for someone behaving stupidly (latter is lit. equivalent
to Yiddish `schmuck')] The sound a newbie makes as he falls to the
bottom of a kill file. While it originated in the newsgroup talk.bizarre,
this term (usually written "*plonk*") is now (1994) widespread on Usenet.
See also killfile.
-----------------------------------------------------------------------
|
| |
Date: 12 Sep 2005 18:07:04
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>It isn't. Take a look at the very first position, the starting
>position. Is that a forced mate for White, a forced mate for Black, or
>a forced draw? (Answer, none of the above.)
CORRECT answer: *one* of the above (we don't know which one,
but we know for sure that it is one of those three.)
I am still waiting for your tic-tac-toe move... Do you resign?
|
| |
Date: 12 Sep 2005 11:01:59
From:
Subject: Re: solve for chess
|
David Richerby wrote:
> <[email protected]> wrote:
> > Tic-tac-toe is solved, unlike chess.
>
> Correct. It sounds to me like you're trying to say that we can't solve
> chess because we don't know how to play it perfectly. But `solving chess'
> means exactly the same thing as `knowing how to play chess perfectly'!
You're presuming, in defiance of logic, that there IS such a thing as
"perfect chess play". I've tried to demonstrate that it is precisely
the theoretical absence of such play which renders chess unsolvable.
>
> > There is a way to win [Tic-Tac-Toe], always, provided you make the first
> > move.
>
> No, both players can force a draw after any initial move, though it is
> possible to make a losing second move.
>
I have never been a Tic-Tac-Toe afficionado, but I do recall, with
reasonable certainty, reading and (and discussing with others) a way to
win at the game provided one moves first. Now, all evidence of such an
algorithm seems to have vanished. This does not surprise me very much,
considering the fact that this is a pseudo-reality which seems to
undergo a variety of fundamental "editing" so that (for example) events
which occurred in the past vanish from record; also, I am used to
dealing with pseudo-sentients like yourself, who lie compulsively and
habitually, from a pathological contrarianism. My recollections of the
Tic-Tac-Toe algorithm are from school days, many decades ago, and it
might, possibly, have been erroneous: I do not recall exhaustively
analyzing it, but it made sense to me at the time; now, however, there
seems to be no recoverable record of it -- the closest thing being the
assertion of a winning algorithm for 3-D Tic-Tac-Toe. I routinely see
advertisements for "new release" movies which I KNOW, with absolute
rather than merely reasonable certainty, have been out before, years
ago, though all archival evidence of this disappears by the time the
events reoccur. The same is true for many newspaper stories, magazine
covers, and obituaries. As for Tic-Tac-Toe, I really don't care enough
to try to reconstruct what was once widely published as a winning
method. Perhaps it never was what it claimed to be: but something
claiming to be this certainly held nearly universal circulation.
Mark Adkins
[email protected]
|
| |
Date: 12 Sep 2005 10:29:31
From:
Subject: Re: solve for chess
|
David Richerby wrote:
> Chess is a finite two-player game of perfect information. It follows that
> every position is either a forced win for White, a forced win for Black or
> is a draw with best play.
It isn't a game of perfect information. A game of perfect information
is one where, at every move, the current game position contains all
data necessary to determine game outcome. That isn't true for chess:
take a look at the starting position. What is additionally necessary,
from that position, and from most subsequent positions, is the future
move sequence; and that is unknown and unknowable when playing an
opponent whose moves in every possible position aren't known or
knowable in advance.
It isn't even a finite game. It doesn't follow, from the basic rules
of chess and from the fact that there are a finite number of
theoretically possible arrangements of pieces on the board, that the
number of moves in the game must be finite. That requires the
imposition of additional rules (e.g., ending a game automatically if a
position is repeated (not merely consecutively repeated) a finite
number of times.
>
>
> > Most positions in chess are open to win, loss, or draw, and many others
> > are open to two of these: the result in such cases depends upon the
> > subsequent sequence of moves, not upon the current position, and that
> > sequence is unknowable since it requires knowledge not only of your own
> > plans but also of how the other player will move.
>
> But there are only finitely many such plans and sequences of moves so one
> could, in principle, check each one of them and find the best.
No, because there is no "best" move, in every position, independent of
all possible future moves (including those of one's opponent); there
are in most cases moves that are only provisionally good or bad,
conditional upon the future move sequence. Since that has yet to
occur, the data is not available. This is *imperfect* or incomplete
knowledge.
>
>
> > Even in a position permitting forced mate, while it is true that any
> > move leading to mate is good, there may be more than one move sequence
> > which results in mate in a minimum number of moves. Which is the
> > "best" and why?
>
> There is no requirement for a unique best move. If you had to choose
> between them, you could always use some arbitrary criterion such as the
> one with the alphabetically first notation.
OF COURSE there is such a requirement, because the word "best" requires
it, semantically! In some position where it can be demonstrated that
15 forced mates exist, each requiring the same provably minimum number
of moves, there is NO "best move": there are 15 winning moves. They
are all equally good, at least on the basis of length.
>
>
> > To say that chess is "solved", incidentally, means that there is an
> > algorithm for winning from the starting position.
>
> It means no such thing!
Yes it does.
> There are several definitions of `solved'. A
> game is `ultra-weakly solved' if we know the theoretical result from the
> initial position (e.g., `chess is a win for White'), is `weakly solved' if
> we know how to achieve the theoretical result from the initial position
> and is `strongly solved' if we know how to achieve the theoretical result
> from every legal position. When people talk about `solving chess', they
> usually mean one of the last two.
The term used was "solved" (without weakening qualifier). Note that
"knowing how to achieve the theoretical result from every legal
position" implies knowing how to achieve it from the starting position.
That is, solving chess means discovering an algorithm for reaching the
theoretical result from the starting position. Now, what is "the
theoretical solution" where the game of chess is concerned? The
theoretical problem isn't how to lose, or how to tie: the theoretical
problem is how to win. The theoretical solution to the game of chess
is therefore an algorithm guaranteeing a win from the starting
position. THAT is what is usually meant by "to solve chess".
Mark Adkins
[email protected]
|
| | |
Date: 13 Sep 2005 11:56:45
From: David Richerby
Subject: Re: solve for chess
|
[email protected] wrote:
> David Richerby wrote:
>> Chess is a finite two-player game of perfect information. It follows
>> that every position is either a forced win for White, a forced win for
>> Black or is a draw with best play.
>
> It isn't a game of perfect information. A game of perfect information
> is one where, at every move, the current game position contains all
> data necessary to determine game outcome. That isn't true for chess:
It's absolutely true for chess. It's just that we don't know how to
determine the game outcome from most positions.
> take a look at the starting position. What is additionally necessary,
> from that position, and from most subsequent positions, is the future
> move sequence; and that is unknown and unknowable when playing an
> opponent whose moves in every possible position aren't known or
> knowable in advance.
A good move is good against any reply.
> It isn't even a finite game. It doesn't follow, from the basic rules
> of chess and from the fact that there are a finite number of
> theoretically possible arrangements of pieces on the board, that the
> number of moves in the game must be finite. That requires the
> imposition of additional rules (e.g., ending a game automatically if a
> position is repeated (not merely consecutively repeated) a finite
> number of times.
You're right that the game doesn't end automatically by either the fifty
move rule or threefold repetition. However, we're assuming that the
players make optimal moves and, if one player has a way to win the game,
making a move that allows the opponent to claim a draw cannot be
optimal. Likewise, not claiming that draw cannot be optimal. So we may
assume that the game terminates as soon as a draw claim could be made.
>> But there are only finitely many such plans and sequences of moves so
>> one could, in principle, check each one of them and find the best.
>
> No, because there is no "best" move, in every position, independent of
> all possible future moves (including those of one's opponent); there
> are in most cases moves that are only provisionally good or bad,
> conditional upon the future move sequence.
No. The quality of a move does not depend on what reply is played. If I
play a move which allows you to checkmate me in one, it's still a bad
move, even if you don't spot it. If you don't spot it, you've played a
bad move, too.
> Since that has yet to occur, the data is not available. This is
> *imperfect* or incomplete knowledge.
That's not what imperfect information means. In principle, knowing just
the position, I could mull over all your possible plans so I could work
out all the relevant information. In contrast, if we're playing some sort
of card game, I cannot possibly work out what cards you have in your hand
(in most circumstances) so I do not have perfect information.
>> There is no requirement for a unique best move. If you had to choose
>> between them, you could always use some arbitrary criterion such as the
>> one with the alphabetically first notation.
>
> OF COURSE there is such a requirement, because the word "best" requires
> it, semantically! In some position where it can be demonstrated that
> 15 forced mates exist, each requiring the same provably minimum number
> of moves, there is NO "best move": there are 15 winning moves. They
> are all equally good, at least on the basis of length.
You are obviously unfamiliar with the mathematical use of words such as
`best' or `optimal'. A move is best if there is no move that is strictly
better than it. This means that there might be more than one best move in
this sense. This differs slightly from general usage but it's hardly very
important, is it? After all, I've explained how to generate a single best
move.
>>> To say that chess is "solved", incidentally, means that there is an
>>> algorithm for winning from the starting position.
>>
>> It means no such thing!
>
> Yes it does.
Oh no it doesn't! Trust me: I'm a dor.
>> There are several definitions of `solved'. A game is `ultra-weakly
>> solved' if we know the theoretical result from the initial position
>> (e.g., `chess is a win for White'), is `weakly solved' if we know how
>> to achieve the theoretical result from the initial position and is
>> `strongly solved' if we know how to achieve the theoretical result
>> from every legal position. When people talk about `solving chess',
>> they usually mean one of the last two.
>
> The term used was "solved" (without weakening qualifier).
The term `solved' is rather informal -- I was trying to add a little
precision to the discussion.
> Note that "knowing how to achieve the theoretical result from every
> legal position" implies knowing how to achieve it from the starting
> position.
Note that I'm not stupid and had worked that out myself. Perhaps that's
why the term `strongly solved' has a name that makes it sound better than
`weakly solved'?
> That is, solving chess means discovering an algorithm for reaching the
> theoretical result from the starting position. Now, what is "the
> theoretical solution" where the game of chess is concerned? The
> theoretical problem isn't how to lose, or how to tie: the theoretical
> problem is how to win.
What if that's not possible?
> The theoretical solution to the game of chess is therefore an algorithm
> guaranteeing a win from the starting position. THAT is what is usually
> meant by "to solve chess".
It might be what you understand by the term...
Dave.
--
David Richerby Mentholated Cat (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ cuddly pet but it's invigorating!
|
| | |
Date: 15 Sep 2005 01:22:45
From:
Subject: Re: solve for chess
|
[email protected] wrote:
> take a look at the starting position. What is additionally necessary,
> from that position, and from most subsequent positions, is the future
> move sequence; and that is unknown and unknowable
well that doesn't matter (that the move sequence is
unknown). At the starting point opening theory rules.
let's say that if you start with 1.d4, then your
opponent can either follow theory, e.g. aiming
for Kings Indian, with a position with d6/Nf6/Bg7,
or deviate from theory, in which case he/black
probably will end up with an inferior position.
Conversely, if white will deviate from theory,
black might get better chances, if he/computer/alien/
zombie/GM or whatever would be a good player.
Now interestingly enough, i believe that if both
sides follow main line theory, they end with a draw.
With 1.e4 white imho has slightly better chances,
but fundamentally black can still defend well
enough to keep a drawish position, resulting in
a drawish endgame, e.g. as indicated by egtb's.
Ergo, chess is solved, and it is a draw.
So.. i propose to change the rules of chess,
abolish the 50 move endgame rule, and then
white might still have a slight chance to win.
And..
it will keep us busy for some 200 yrs more :)
best regards
http://superchess.com
|
| | | |
Date: 15 Sep 2005 09:09:07
From: David Richerby
Subject: Re: solve for chess
|
[email protected] wrote:
> let's say that if you start with 1.d4, then your opponent can either
> follow theory, e.g. aiming for Kings Indian, with a position with
> d6/Nf6/Bg7, or deviate from theory, in which case he/black probably will
> end up with an inferior position.
>
> Conversely, if white will deviate from theory, black might get better
> chances, if he/computer/alien/zombie/GM or whatever would be a good
> player.
>
> Now interestingly enough, i believe that if both sides follow main line
> theory, they end with a draw.
That's not so interesting. It's probably fair to say that most people
think this.
> With 1.e4 white imho has slightly better chances, but fundamentally
> black can still defend well enough to keep a drawish position, resulting
> in a drawish endgame, e.g. as indicated by egtb's.
>
> Ergo, chess is solved, and it is a draw.
Er... no. Waving one's hands and saying that Black can probably hold a
draw after following current opening theory in no way counts as `solving
chess'.
> So.. i propose to change the rules of chess, abolish the 50 move endgame
> rule, and then white might still have a slight chance to win.
Makes no difference. The 50 move rule was extended from, as I recall,
1984 to 1992. Almost no games got into positions where the extended rule
applied so it reverted to 50 moves in all positions. Also, I defy any
human being to play out these 200-move forced mates. The first 150 moves
look completely random.
Dave.
--
David Richerby Flammable Dish (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a fine ceramic dish but it burns
really easily!
|
| | | | |
Date: 15 Sep 2005 18:19:01
From:
Subject: Re: solve for chess
|
David Richerby wrote:
>>Ergo, chess is solved, and it is a draw.
>
> Er... no.
ok, there's no proof for this, that's true.
there's also no proof that if you flip a coin
ten billion times, that the number of heads
or tails will be between 49 and 51 %.
But statistically speaking, the more often
you flip a coin, the more nearby the percentage
will go to 50 %.
The more perfectly chess players, or computers
are playing, the more likely it becomes the
game ends in a draw.
>>So.. i propose to change the rules of chess, abolish the 50 move endgame
>>rule, and then white might still have a slight chance to win.
> Makes no difference. The 50 move rule was extended from, as I recall,
> 1984 to 1992.
ok, interesting info, but then we didn't have such good/large
computerized endgame tables as nowdays, you know.
> Also, I defy any > human being to play out these 200-move forced mates.
well a computer program can easily do it.
whether it would make a difference for the drawing chances of
the game, i don't know. my statement was a bit joking
(after all it would be just another chess variant,
and not official chess), and indeed a speculative statement
ok, if we would like white to win, let's think about one other
chess variant, where stalemate would mean a full point (i.e. a win)
for white. This obviously would increase white's chances.
Could such a variant be 'solved' (in the sense that it
would be always a win for white) ?
And if 1.e4 would be the best move in such a variant,
would that mean that 1.e4 would also be the best move
in 'normal/official' (Fide) chess ?
My answer is yes,
But you of course would disagree again
:)
|
| | | | | |
Date: 18 Sep 2005 14:27:38
From: David Richerby
Subject: Re: solve for chess
|
[email protected] wrote:
> David Richerby wrote:
>> [email protected] wrote:
>>> Ergo, chess is solved, and it is a draw.
>>
>> Er... no.
>
> ok, there's no proof for this, that's true.
And to say that chess is solved means that there is a proof.
> there's also no proof that if you flip a coin ten billion times, that
> the number of heads or tails will be between 49 and 51 %.
That's an entirely different scenario. Tossing a coin ten billion times
is an experiment and, for every n in the range 0-10^10, there is a
non-zero probability that you'll get n heads. Chess is either a win for
White, a win for Black or a draw. We don't know which and no amount of
experimentation will demonstrate it because the only way to prove that a
position is a forced win for one side is to investigate every possible
sequence of moves from the losing side.
> The more perfectly chess players, or computers are playing, the more
> likely it becomes the game ends in a draw.
So you (and many other people, myself probably included) believe. But
until there's a proof, chess isn't solved.
>>> So.. i propose to change the rules of chess, abolish the 50 move
>>> endgame rule, and then white might still have a slight chance to win.
>>
>> Makes no difference. The 50 move rule was extended from, as I recall,
>> 1984 to 1992.
>
> ok, interesting info, but then we didn't have such good/large
> computerized endgame tables as nowdays, you know.
The rule was changed precisely because computer analysis indicated that
there were forced wins that would be chopped off because of the 50 move
rule. Tablebases without pawns aren't all that hard, as I recall.
> ok, if we would like white to win, let's think about one other chess
> variant, where stalemate would mean a full point (i.e. a win) for
> white. This obviously would increase white's chances. Could such a
> variant be 'solved' (in the sense that it would be always a win for
> white) ?
That's not what solved means! Solved means that we know the outcome (and
possibly how to get there). Chess with stalemate being a win for White
(let's call it stalemate-chess) would be no easier to solve than ordinary
chess, though it would be more likely to be a win for White for the simple
reason that a non-zero proportion of chess games end in stalemates. But
why do we want to make the game easier for White to win by adding
artificial rule-changes? (Surely, if you think stalemate shouldn't be a
draw, it should be a loss for the side whose king is stuck?)
> And if 1.e4 would be the best move in such a variant, would that mean
> that 1.e4 would also be the best move in 'normal/official' (Fide) chess?
> My answer is yes, But you of course would disagree again
If 1.e4 forces a win in stalemate-chess, it forces at least a draw in
ordinary chess. On the other hand, it's possible that there is another
move that forces a win in ordinary chess, such as 1.d4.
Dave.
--
David Richerby Unholy Cat (TM): it's like a cuddly
www.chiark.greenend.org.uk/~davidr/ pet but it's also a crime against
nature!
|
| |
Date: 12 Sep 2005 09:38:08
From:
Subject: Re: solve for chess
|
Simon Krahnke wrote:
> * <[email protected]> (04:55) schrieb:
> > What if the position can't be "shown as won"? Most positions in chess
> > are open to win, loss, or draw, and many others are open to two of
> > these:
>
> No there aren't. Every position in chess is either a forced win for
> white or for black, or a forced draw.
It isn't. Take a look at the very first position, the starting
position. Is that a forced mate for White, a forced mate for Black, or
a forced draw? (Answer, none of the above.) You don't seem to know
what "forced mate" or "forced draw" means. It doesn't mean that the
game will eventually end in a mate for *someone* or else in a draw. If
White has a forced mate, and Black is subject to forced mate, it means
that, in the current position, every legal move possible to Black can
be followed by a move by White which leads to Black being mated, and
that this is true for every position subsequent to this. If, on the
other hand, Black is free to choose, in a given position, from moves
which do not satisfy these conditions, he is not subject to a forced
mate.
Never mind "best" moves -- it's easy to see that in most chess
positions, there are not even provably good moves. There are two kinds
of moves in chess commonly called "good":
(1) Provably good moves. These include, for example, moves necessary
to execute a forced mate.
(2) Heuristically good moves. These are based on heuristic, or rule of
thumb evaluations which use *relatively short term* algorithms weighing
gains in material and/or position. By "relatively short term" I mean
evaluations which end with some future position which is not
end-of-game.
Heuristically good moves are not always objectively good moves, because
even when they are exhaustive with respect to their evaluation depth
(and most of them aren't), they may lead to inferior positions over
move-sequences which are deeper than this. That is, they may lead to
short-term gain but longer-term loss, where the latter outweighs the
former (e.g., leading to positions where forced mate is possible
against one) even though they initially gain material and/or positional
advantage and thus look good at the time they are made. Similarly,
heuristically bad moves may lead to winning positions over a move-frame
longer than their evaluation frame.
Most positions in chess are ambiguous in that they permit a win, loss,
or draw; in these cases, knowledge of game outcome depends upon the
future move sequence and is not strictly inherent to the current
position; and half of the future move-sequence is determined by your
opponent. Thus, the data necessary to evaluate the position in any
provable manner is missing; it is unknown and unknowable if your
opponent is free to choose among alternatives that lead to *different*
game outcomes.
In most chess positions, therefore, there are no provably good moves,
but only heuristically good moves, which may not be objectively good
moves.
>
> > Even in a position permitting forced mate, while it is true that any
> > move leading to mate is good, there may be more than one move sequence
> > which results in mate in a minimum number of moves. Which is the
> > "best" and why?
>
> Any is. This is silly. No one demands there is a single best move in
> every position. Of course there may be many perfect games of chess. But
> they all end the same.
Evidently you don't know what the word "best" means. To say that there
is "more than one best move" in a given position is an abuse of
language. If there is a "best" move there is only one; otherwise,
there are merely good moves or winning moves.
>
> > And you have yet to meaningfully define this even for forced mate
> > positions, much less for arbitrary positions! To say that chess is
> > "solved", incidentally, means that there is an algorithm for winning
> > from the starting position.
>
> No, it doesn't mean that.
Certainly it does. This reminds me of that awful troll, Guy Macon, who
asserted in another thread that the semantic content of algebraic chess
notation is "the game of chess" rather than the moves described by the
symbols.
>
> > There is not, for either side.
>
> There is none yet, and may never be. But theoretically it is possible.
>
No, theoretically it is impossible, because the starting position of
chess does not provide sufficient data, in and of itself, for such an
algorithm; only after the future move sequence has caused the game to
reach a point where provably good moves (e.g., a forced mate) exists,
is an algorithm possible; and as long as the future move sequence is
half-determined by the moves of an opponent which are unknown and
unknowable in advance, that data is not available.
The simple fact is that in most chess positions, a move is good or bad
depending in part on how your opponent moves subsequently. A
particular move might be good if your opponent then moves one way, and
bad if your opponent moves another way; in such cases there are no
objectively good moves independent of his future move seqeuence, much
less a "best" move independent of this.
Mark Adkins
[email protected]
|
| |
Date: 15 Sep 2005 20:29:07
From:
Subject: Re: solve for chess
|
David Richerby wrote:
>
> A good move is good against any reply.
And if there is no move that is good against any reply, it being
understood that a "reply" may last an arbitrary number of moves? Do
you disagree that it is possible for a move to be good against some
replies, and not good against others, and that it may be possible in
some positions, or even in most of them, that every possible move is
ambiguous in this fashion? I'm not talking about ambiguous with
respect to the short term, necessarily, but ambiguous with respect to a
total game sequence of moves.
> [email protected] wrote:
>
> > It isn't even a finite game. It doesn't follow, from the basic rules
> > of chess and from the fact that there are a finite number of
> > theoretically possible arrangements of pieces on the board, that the
> > number of moves in the game must be finite. That requires the
> > imposition of additional rules (e.g., ending a game automatically if a
> > position is repeated (not merely consecutively repeated) a finite
> > number of times.
>
> You're right that the game doesn't end automatically by either the fifty
> move rule or threefold repetition. However, we're assuming that the
> players make optimal moves and, if one player has a way to win the game,
> making a move that allows the opponent to claim a draw cannot be
> optimal. Likewise, not claiming that draw cannot be optimal. So we may
> assume that the game terminates as soon as a draw claim could be made.
OK, this is about the only thing in the latest batch of replies that
interests me. I will hopefully have more to say about this subject
(solving chess, or not) but in the meantime I would like to know a few
things about the current status of these rules. First, they are not
basic chess rules, so under what circumstances do they apply? My
understanding is that they are supplemental rules of chess.
Second, why do you assume that one player always has a way to win the
game prior to the intervention (whether automatic or claimed by a
player) of an anti-perpetual game rule? That is, even assuming that
your premise that "chess is a win for White" or "chess is a win for
Black" are theoretically possible until it is known otherwise, why does
this imply that a guaranteed win for one side must always be possible
prior to the intervention of an arbitrary anti-perpetual game rule?
Why couldn't it be the case, under your thesis, that, for example,
White is guaranteed a win from start of game, if he "plays perfectly",
but that in some cases this requires more moves than are possible under
these anti-perpetual game rules? Or perhaps more than are possible
under any anti-perpetual game rule? Why couldn't it be the case that
in the presence of some (any) anti-perpetual game rule, is it possible
under your thesis for Black, playing perfectly (as a theoretical loser)
to stretch a game out until the anti-perpetual rule kicks in, even
though if the game could go on arbitrarily long White would eventually
be guaranteed a win in all circumstances?
>
>
> >> But there are only finitely many such plans and sequences of moves so
> >> one could, in principle, check each one of them and find the best.
> >
> > No, because there is no "best" move, in every position, independent of
> > all possible future moves (including those of one's opponent); there
> > are in most cases moves that are only provisionally good or bad,
> > conditional upon the future move sequence.
>
> No. The quality of a move does not depend on what reply is played. If I
> play a move which allows you to checkmate me in one, it's still a bad
> move, even if you don't spot it. If you don't spot it, you've played a
> bad move, too.
This is specious. I didn't say that there were NO circumstances in
which a move is provably good, merely that in most cases there is no
provably good move.
Incidentally, I'd be interesting in getting your reply to the
following. It is scarcely unanswerable (as I phrase it below) but
since you seem to be the most informed/coherent/objective of those
taking your position in this thread, I'd be interested to see how you
reply.
At the start of game, each one of the legal moves available to White is
known to result in games in which White wins, as well as in games in
which Black wins, as well as in games which draw. More generally, for
any move sequence (W1B1W2B2...Wn) which results in a win for White, in
the general case there are numerous move sequences which, up through
the move Bn-1 (the next to last move), eventually result in each of
these outcomes. That is, at most points in a total game sequence of
moves, the partial sequence up through that point is indistinguishable
as a win, loss, or draw, since there are sequences of each kind
identical through that point. What is the selection criterion for
White to play a "perfect game"?
>
>Trust me: I'm a dor.
Har. Physician, heal thyself.
Mark Adkins
[email protected]
|
| |
Date: 16 Sep 2005 04:46:34
From: Guy Macon
Subject: Re: solve for chess
|
[email protected] wrote:
>David Richerby wrote:
>
>> A good move is good against any reply.
>
>And if there is no move that is good against any reply, it being
>understood that a "reply" may last an arbitrary number of moves? Do
>you disagree that it is possible for a move to be good against some
>replies, and not good against others, and that it may be possible in
>some positions, or even in most of them, that every possible move is
>ambiguous in this fashion? I'm not talking about ambiguous with
>respect to the short term, necessarily, but ambiguous with respect to a
>total game sequence of moves.
(SHOUTING)
YOU HAD THE ANSWER TO THIS QUESTION HANDED TO YOU ON A SILVER PLATTER,
AND YOU REFUSED TO EVEN CONSIDER IT! IT'S SIMPLE; JUST ASK THE SAME
QUESTIONS ABOUT TIC-TAC-TOE. ANALYSING TIC-TAC-TOE AND ANALYSING
CHESS IS THE *EXACT SAME TASK*!!! IN BOTH CASES YOU GENERATE A TREE
OF ALL POSSIBLE REPLIES, REPLIES TO REPLIES, ETC. THE *ONLY* DIFFERENCE
IS THE SIZE OF THE TREE. APPLY YOUR STATEMENT "it is possible for a
move to be good against some replies, and not good against others
... it may be possible in some positions ... that every possible move
is ambiguous in this fashion" TO A GAME OF TIC-TAC-TOE. YOU WILL
CLEARLY SEE THAT AT LEAST ONE BEST MOVE *ALWAYS* I REPEAT *ALWAYS*
EXISTS FOR *EVERY* I REPEAT *EVERY* POSITION. UNDERSTAND WHY THIS
IS TRUE FOR TIC-TAC-TOE AND YOU WILL UNDERSTAND WHY IT IS TRUE FOR
CHESS. OR BE WILLFULLY IGNORANT, PRETENDING THAT NOBODY GAVE YOU THE
SIMPLE ANSWER AND KEEP REPHRASING THE QUESTION -- YOUR CHOICE.
>OK, this is about the only thing in the latest batch of replies that
>interests me.
Too bad the answer to your oft-repeated question doesn't interest you.
Why do you keep asking if you aren't going to listen to the answer?
>I will hopefully have more to say about this subject
>(solving chess, or not) but in the meantime I would like to know a few
>things about the current status of these rules. First, they are not
>basic chess rules, so under what circumstances do they apply? My
>understanding is that they are supplemental rules of chess.
Read the rule book yourself. The URL has been posted a dozen times.
>This is specious. I didn't say that there were NO circumstances in
>which a move is provably good, merely that in most cases there is no
>provably good move.
Again the refutation is right in front of you. Prove to yourself
that there is always an optimal move in tic-tac-toe. Once you
understand that, do the same with six pawns on a 3x3 board with no
promotion allowed. Then prove it to yourself with a standard game
that has only two pawns and a king on each side. Then add pieces
and compexity, proving to yourself at ever step that there is always
an optimal move. Then perhaps you will understand where your
thinking has gone awry.
>Incidentally, I'd be interesting in getting your reply to the
>following. It is scarcely unanswerable (as I phrase it below) but
>since you seem to be the most informed/coherent/objective of those
>taking your position in this thread, I'd be interested to see how you
>reply.
>
>At the start of game, each one of the legal moves available to White is
>known to result in games in which White wins, as well as in games in
>which Black wins, as well as in games which draw. More generally, for
>any move sequence (W1B1W2B2...Wn) which results in a win for White, in
>the general case there are numerous move sequences which, up through
>the move Bn-1 (the next to last move), eventually result in each of
>these outcomes. That is, at most points in a total game sequence of
>moves, the partial sequence up through that point is indistinguishable
>as a win, loss, or draw, since there are sequences of each kind
>identical through that point. What is the selection criterion for
>White to play a "perfect game"?
Answer the question yourself for tic-tac-toe. The answer for chess is
exactly the same. The tree of moves is larger - to large for us - but
you can imagine a brain-damaged person for whom the tic-tac-toe tree
is too lrge to figure out. (This is the key point) just because he
can't figure out the optimal tic-tac-toe move does not mean that no
optimal tic-tac-toe move exists! I implore you to look at the answer
that is staring you in the face.
|
| | |
Date: 16 Sep 2005 14:38:27
From: none
Subject: Re: solve for chess
|
Guy Macon wrote:
snipped relevant parts.
Dude, you are doing what you tell others not to do. Engaging someone who
should have been kill filed along time ago. Although reading ignorant
opinions on the internet is somewhat amusing. His, not yours.
|
| | | |
Date: 17 Sep 2005 05:50:38
From: Guy Macon
Subject: Re: solve for chess
|
none wrote:
>Dude, you are doing what you tell others not to do. Engaging someone who
>should have been kill filed along time ago. Although reading ignorant
>opinions on the internet is somewhat amusing. His, not yours.
Point very well taken. I have failed to follow my own advice. :(
I appreciate you taking the time to correct me on this - it really
*is* best to not reply.
|
| |
Date: 16 Sep 2005 18:50:44
From:
Subject: Re: solve for chess
|
I am still waiting to see proof that chess is "solvable". Most of the
participants in this thread who maintain that it is keep throwing out
terms like "optimum move" even when I have clearly shown that in the
general case, any partial game sequence is repeated in numerous total
game sequences having different game outcomes. For example, in the
general case, if there are 14 moves in a game so far, and the 15th move
is not definitive in resolving the game, then moves 1 through 15 (no
matter what is chosen for 15) constitute a partial game sequence that
is present as the first 15 moves of numerous total game sequences of
various types (win for White, win for Black, forced draw, perpetual
game). How can move 15 be said to be "optimal" when the SAME move is
present in the same position of the same subsequence through the same
game point, in games with radically different outcomes? Again, I tell
you, it is total game sequences of moves which determine whether a
particular move is good, not the other way around. This is a little
like the so-called principle of survival of the fittest. The "fittest"
is not the smartest, the fastest, or the strongest; stupidity, slowness
and weakness survive everywhere; the "fit" are the survivors; ergo,
"survival of the fittest" means only that the survivors survive. It is
mere tautology.
Mark Adkins
[email protected]
|
| | |
Date: 18 Sep 2005 11:28:01
From: James
Subject: Re: solve for chess
|
Before talking nonsense, read the basic scientific litterature about games,
and game theory:
GM Adelson-Velsky, VL Arlazarov, MV Donskoy: Algorithms for games (Springer
ISBN 0387966293)
On the web, there is Aske Plaat's PhD
http://www.recherche.enac.fr/~alliot/ALGOS_JEU/thesis.ps
Or Victor Allis' Phd:
http://www.recherche.enac.fr/~alliot/allis.ps
And many other things.
Stop pestering people if you don't understand the very simple mathematics
behind game theory.
<[email protected] > a �crit dans le message de news:
[email protected]...
>I am still waiting to see proof that chess is "solvable". Most of the
> participants in this thread who maintain that it is keep throwing out
> terms like "optimum move" even when I have clearly shown that in the
> general case, any partial game sequence is repeated in numerous total
> game sequences having different game outcomes. For example, in the
> general case, if there are 14 moves in a game so far, and the 15th move
> is not definitive in resolving the game, then moves 1 through 15 (no
> matter what is chosen for 15) constitute a partial game sequence that
> is present as the first 15 moves of numerous total game sequences of
> various types (win for White, win for Black, forced draw, perpetual
> game). How can move 15 be said to be "optimal" when the SAME move is
> present in the same position of the same subsequence through the same
> game point, in games with radically different outcomes? Again, I tell
> you, it is total game sequences of moves which determine whether a
> particular move is good, not the other way around. This is a little
> like the so-called principle of survival of the fittest. The "fittest"
> is not the smartest, the fastest, or the strongest; stupidity, slowness
> and weakness survive everywhere; the "fit" are the survivors; ergo,
> "survival of the fittest" means only that the survivors survive. It is
> mere tautology.
>
> Mark Adkins
> [email protected]
>
|
| | |
Date: 18 Sep 2005 09:32:03
From: David Richerby
Subject: Re: solve for chess
|
<[email protected] > wrote:
> I am still waiting to see proof that chess is "solvable".
I and others have tried to explain to you why chess is solvable but you've
refused to accept any explanation (or, as far as I can recall, any part of
any explanation) that has been offered. I really can't see any other way
of trying to convince you.
The things that you claim to be blatantly false about chess (the existence
of optimal moves, the game-theoretic evaluation of a position depending
only on the position) are things that anyone with an undergraduate-level
education in mathematics should be able to understand and see to be true.
People have tried explaining all of this to you but you've rejected
everything.
> This is a little like the so-called principle of survival of the
> fittest. The "fittest" is not the smartest, the fastest, or the
> strongest; stupidity, slowness and weakness survive everywhere; the
> "fit" are the survivors; ergo, "survival of the fittest" means only
> that the survivors survive. It is mere tautology.
The `survival' is not survival of individuals but survival of physical
characteristics. Those characteristics that make individuals more likely
to survive are, in turn, more likely to be passed on to the next
generation. But if you want an argument about that, go to talk.origins.
Dave.
--
David Richerby Portable Mentholated Drink (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a refreshing juice beverage but
it's invigorating and you can take
it anywhere!
|
| |
Date: 16 Sep 2005 18:37:48
From:
Subject: Re: solve for chess
|
none wrote:
> Guy Macon wrote:
>
> snipped relevant parts.
>
> Dude, you are doing what you tell others not to do. Engaging someone who
> should have been kill filed along time ago. Although reading ignorant
> opinions on the internet is somewhat amusing. His, not yours.
Well, we agree on one point of the above: if the awful troll calling
itself "Guy Macon" had entered me in its killfile, as it has threatened
to do, then it need not even take up space in the reply tree of this
thread. I, on the other hand, though lacking a killfile, have early on
stopped reading his silly misrepresentations (of the facts and of my
description of them). So I cannot say that I fully understand your
reference, above, to his message content -- though it was quite obvious
that he was a silly hypocrite ("doing what you tell others not to do")
when he personally attacked me in claiming that personal attacks
indicate weakness on the part of the attacker.
I'm still waiting to hear back from David Richerby.
Really, I've seen NOTHING indicating that there can be such a
"solution" to chess, even theoretically. Believe me when I say that
this is a mare's nest.
Mark Adkins
[email protected]
|
| |
Date: 17 Sep 2005 02:22:32
From:
Subject: Re: solve for chess
|
[email protected] wrote:
>I am still waiting to see proof that chess is "solvable".
Asked for and provided. Several times. You simply refuse to
accept the answer provided, rejecting it without explaining why.
|
| |
Date: 17 Sep 2005 17:30:08
From:
Subject: Re: solve for chess
|
Simon Krahnke wrote:
> * <[email protected]> (03:50) schrieb:
>
> > I am still waiting to see proof that chess is "solvable".
>
> Well here it is: Do an standard Alpha-Beta search on the initial
> position with unbounded depth and without any forward pruning.
>
> Since in this configuration all values will be mate or draw, the final
> result must also be mate or draw.
>
> That will answer the question if it's a forced mate for white or black
> or forced draw, and give an optimal move for white on the initial
> position.
>
> For a more complete solution just repeat the algorithm on other positions.
>
Sorry, but this strikes me as the most awful obfuscatory gobbledygook.
You haven't at all proven that one side or the other can, by his first
move, guarantee one of these outcomes regardless of the moves of the
other side. So far as I can see, you've merely stated (quite
inaccurately) that any game of chess must either result in a win by one
side OR the other, or in a draw. Well, so what?
As for the other party which claimed, falsely, in another message, that
I've already seen such proofs "several times", but that I have rejected
them without stating why, I can only honestly repeat that I have seen
no such proof. I can also state that, in attempting to reply to that
party's message, my reply was directed automatically to a "newsgroup"
(non-existent, I believe) called "alt.dev.null". What follows are the
full headers of his message (or as full as I can get from Google Groups
(whether still called "Google Groups Beta" or not):
(start of headers)
Path:
g2news1.google.com!news3.google.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!sn-xit-02!sn-xit-06!sn-post-01!supernews.com!corp.supernews.com!not-for-mail
From: . =?ISO-8859-1?B?P g E g Au gPg==?=
Newsgroups: rec.games.chess.computer
Subject: Re: solve for chess
Followup-To: alt.dev.null
Date: Sat, 17 Sep 2005 02:22:32 +0000
Organization: .
Message-ID: <[email protected] >
References: <[email protected] >
<P8o*[email protected] >
<[email protected] >
<[email protected] >
<3Og*[email protected] >
<[email protected] >
<[email protected] >
X-Complaints-To: [email protected]
Lines: 9
(end of headers)
One wonders: why all the subterfuge? Just what processes was this
party attempting to evade in posting a message which made false
accusations against me, but to which a reply was automatically directed
to a newsgroup which, so far as I know, is non-existent and which in
any case is outside both the original newsgroup and any newsgroups
relevant to the topic at hand? Another way of putting it is: why are
my opponents here such deceitful cowards? What are they trying to
hide? These are not rhetorical questions. Answer them fully and
accurately and clearly, such that I am made aware of the answers
explicitly, without unnecessary delay(s). Why, for that matter, in
previewing this message, has the option (from the preview screen) of
posting it disappeared, instead offering only the options (from the
preview screen) of editing or canceling it?
Mark Adkins
[email protected]
|
|
