| |
Main
Date: 05 Feb 2008 10:46:07
From: Guy Macon
Subject: Solving Chess -Guy macon
|
Sanny wrote:
>In Chess after every move new 30-40 moves are generated.
>
>So For 1 depth : 30
The correct number is 20. You should have been able
to look at a chess board and count this one yourself.
>2 depth : 900
400. The above number squared.
>3 depth: 27000
Nope. It's 8902.
>4 depth: 810000
..........197281
>5 depth: 24300000
...........4865617
>6 depth :729000000
..........119060679
>7 depth: 21870000000
...........3195913043
>8 depth: 656100000000
...........84999425906
>9 depth: 19683000000000
...........2439540533153
>10 depth: 590490000000000
............69353270203366
("11 depth" would be 2097660204806910)
Technical note: I am counting the number of possible chess
games at the end of the n-th ply plus number of games that
terminate with a checkmate in fewer than n plies.
0th ply: 1
1st ply: 20
2nd ply: 400
3rd ply: 8,902
4th ply: 197,281
5th ply: 4,865,617
6th ply: 119,060,679
7th ply: 3,195,913,043
8th ply: 84,999,425,906
9th ply: 2,439,540,533,153
10th ply: 69,353,270,203,366
11th ply: 2,097,660,204,806,910
>So just in 10 depth we reached 590 Trillion Moves.
69 Trillion.
Note: in the US a trillion is 1.0E+12 (1,000,000,000,000) -tera
while a UK trillion is 1.0E+18 (1,000,000,000,000,000,000) -exa
Sanny appears to be using the US trillion.
>Say Each Move Generation needs 1000 Calculations.
>
>So 10 depth search needs 590,000 Trillion Calculations.
69,000 Trillion Calculations.
>Fast Desktop works on 10 GFlops. So It will take 59,000,000 seconds on
>fast desktop to perform exhausted 10 depth search.
6935327.0203366 seconds
And you should be counting Ops, not Flops. Chess programs
don't as a rule use floating point.
>It will take 2 years to do 10 depth Checking of all moves.
1 year = 31,556,926 seconds
59000000 / 31556926 = 1.87 years
6935327.0203366 / 31556926 = 0.22 years
>10 depth means just 5 Moves. So for 5 Moves We need our desktops to
>think for 2 Years.
Less than 3 months. Going one ply deeper will take 6.65 years.
>To Solve Chess we need to search till at least 100 depth.
Evidence, please. You have no idea whether the above
claim is true. We do *not* know that there isn't a
forced win or draw by, say, move 64.
We can start to calculate the number of chess games that end
in checkmate after exactly n plies, though:
0th ply: 0
1st ply: 0
2nd ply: 0
3rd ply: 0
4th ply: 8
5th ply: 347
6th ply: 10,828
7th ply: 435,767
8th ply: 9,852,036
9th ply: 400,191,963
10th ply: 8,790,619,155
11th ply: 362,290,010,907
...and if there was a forced win or draw in the 1st 11 plies we
surely would have found it long ago.
>That will take even more than Billions of Billions of Billions
>of years on a Petaflop Super Computer.
Agreed. The size of an exhaustive search is much bigger than
a tiny number like a billion billion billion.
>Such a Computer can never be made at least in next 100,000
>years of Man Kind even him Moores Law is Followed.
Wrong. You have no clue how huge 2 to the 50,000th power is.
That's far larger than needed to solve chess. Alas, it also
requires more bits to store positions than there are particles
in the universe and it requires propagation delays far smaller
than the amount of time it takes light to cross a particle.
So Moore's law will *not* double the speed of computers every
two years for the next 100,000 years
******************************************************
That being said, your argument that chess cannot be
solved in next 100,000 years contains a basic and fatal
flaw. It assumes no new technologies. Imagine someone
in the Roman Empire calculating how long it would take
to do something using paper and ink, and then assuming
that nothing better than paper and ink will exist for
the next ten thousand years...
Assuming that solving chess can be done by searching
multiple positions in parallel for a solution (it is
not clear whether this is true or false), a Quantum
Computer (if one is ever invented) with enough qbits
to solve chess will be able to search for a solution
among 2^N possible solutions in N time.
Thus, a quantum computer that can evaluate one
position in five milliseconds (my $29.99 LCD
handheld can evaluate one position in one
millisecond) would be able to:
Evaluate 1 position in 5 milliseconds
Evaluate 2 positions in 10 milliseconds
Evaluate 4 positions in 30 milliseconds
Evaluate 8 positions in 40 milliseconds
Evaluate 16 positions in 50 milliseconds
Evaluate 32 positions in 60 milliseconds
Evaluate 64 positions in 70 milliseconds
Evaluate 128 positions in 80 milliseconds
Evaluate 256 positions in 90 milliseconds
Evaluate 512 positions in 100 milliseconds (0.1 second)
...
Evaluate a million (10^6) positions in 0.2 seconds
Evaluate a billion (10^9) positions in 0.3 seconds
Evaluate a trillion (10^12) positions in 0.4 seconds
Evaluate (10^15) positions in 0.8 seconds
Evaluate (10^18) positions in 1.6 seconds
...
Evaluate (10^30) positions in 25 seconds
...
Evaluate (10^36) positions in 100 seconds
...
Evaluate (10^72) positions in 200 seconds
...
Evaluate (10^108) positions in 5 minutes
...and so on.
Given the assumptions above (which have not been
proven right or proven wrong), you could start with
a quantum computer that can only evaluate one position
in one second and still solve the game of chess in less
than a day.
--
Guy Macon <http://www.guymacon.com/ > Guy Macon <http://www.guymacon.com/>
Guy Macon <http://www.guymacon.com/ > Guy Macon <http://www.guymacon.com/>
Guy Macon <http://www.guymacon.com/ > Guy Macon <http://www.guymacon.com/>
Guy Macon <http://www.guymacon.com/ > Guy Macon <http://www.guymacon.com/>
|
|
| |
Date: 05 Feb 2008 23:25:00
From: Guy Macon
Subject: Re: Solving Chess -Guy Macon
|
tin Brown wrote:
>Guy Macon <http://www.guymacon.com/> writes
>
>>I don't think you can use *any* pruning technique and be 100% sure.
>
>Yes you can. If at a node if you find a winning move you do not need to
>evaluate any other moves there assuming best play. The player to move is
>assumed to always go for his best possible game outcome in the shortest
>number of moves.
>
>And vice versa if all the moves from a node evaluate to a loss with best
>play then the player on the move will avoid it.
Upon reflection, my conclusion is that you (and Andy Walker, who
pointed out the same thing) are right and I was wrong. Thanks
for correcting the error; that's how we learn. :)
--
Guy Macon
<http://www.guymacon.com/ >
|
| |
Date: 05 Feb 2008 23:15:39
From: Guy Macon
Subject: Re: Solving Chess/endgame rules/theory
|
tin Brown wrote:
>Endgame theory is a lot more tractable and formal proof there is
>possible 7-men endgame tables will be fully computable before too long.
>But 8-men may be some way off. And there is a heck of a gap between
>there and the opening position with 32men (and all the permutations).
Here are some size figures/estimates I have for Nalimov Tablebases
using standard compression:
Complete 3 man Nalimov Tablebase.................80 kB (measured)
Complete 3+4 man Nalimov Tablebase...............30 MB (measured)
Complete 3+4+5 man Nalimov Tablebase............7.5 GB (measured)
"Complete" 3+4+5+6 man Nalimov Tablebase........1.146 TB (measured)[1]
Complete 3+4+5+6+7 man Nalimov Tablebase....200-600 TB (estimated)
Complete 3+4+5+6+7+8 man Nalimov Tablebase...40-180 PB (estimated)
[...]
Complete 3+4+5+6+[...]+30+31+32 man Nalimov tablebase...[UNKNOWN]
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 [UNKNOWN] above. I would also very much
like some data on how long it takes/took to generate each set.
Note 1: As of the last time I checked, nobody has bothered making
tablesbases for positions where a single king faces five pieces.
It's hard to imagine a non-stalemated 5 vs. 1 position where a
computer can't find a quick win without consulting a tablebase,
so those may never get calculated.
--
Guy Macon
<http://www.guymacon.com/ >
|
| | |
Date: 08 Feb 2008 12:35:46
From: David Richerby
Subject: Re: Solving Chess/endgame rules/theory
|
Guy Macon <http://www.guymacon.com/ > wrote:
> As of the last time I checked, nobody has bothered making
> tablesbases for positions where a single king faces five pieces.
> It's hard to imagine a non-stalemated 5 vs. 1 position where a
> computer can't find a quick win without consulting a tablebase, so
> those may never get calculated.
King plus four bishops on the same coloured squares is drawn -- no
checkmate is possible. Any other KXXXX-K setup with at most one pawn
(apart from KBBBP-K with all three bishops on the same colour) must
contain
1) at least one queen;
2) or at least one rook;
3) or at least one bishop on each colour;
4) or a bishop and a knight;
5) or three knights.
All of these are won for the side with the material advantage, apart
from pathological cases. So, if there is at most one pawn on the
board, the strategy `sacrifice a piece to end up in a winning KXXX-K
endgame' will suffice. (Indeed, in most cases,sacrificing *any* piece
will suffice.)
I think KBBBP-K with all three bishops the same colour is won for the
side with the pawn in most cases, though I can imagine there being a
fortress against a well-advanced rook's pawn that promotes on the
wrong coloured square.
If there are at least two pawns on the board, I'm going to handwave
and say that essentially everything should still be won and that this
should be findable by fairly shallow search with evaluation from the
tablebases at the leaves to work out which man to sac to get into the
KXXX-K tablebase.
So the KXXXX-K tablebases sound mostly redundant, to me.
Dave.
--
David Richerby Radioactive Nuclear Tree (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a tree that's made of atoms but
it'll make you glow in the dark!
|
| | |
Date: 06 Feb 2008 17:30:40
From: Tony M
Subject: Re: Solving Chess/endgame rules/theory
|
On Tue, 05 Feb 2008 23:15:39 +0000, Guy Macon
<http://www.guymacon.com/ > wrote:
>Note 1: As of the last time I checked, nobody has bothered making
>tablesbases for positions where a single king faces five pieces.
>It's hard to imagine a non-stalemated 5 vs. 1 position where a
>computer can't find a quick win without consulting a tablebase,
>so those may never get calculated.
The King vs. 5 piece tablebases were not created in Nalimov format
because TBGEN is incapable of creating 5 vs. 1 tablebases. They have
been generated in Chessmaster's FEG format, which unfortunately is
proprietary to Chessmaster.
Tony
|
| |
Date:
From: Martin Brown
Subject: Re: Solving Chess -Guy Macon
|
|
| |
Date:
From: Martin Brown
Subject: Re: Solving Chess/endgame rules/theory
|
|
| |
Date:
From: Martin Brown
Subject: Re: Solving Chess -Guy macon
|
|
| | |
Date: 05 Feb 2008 17:27:14
From: Guy Macon
Subject: Re: Solving Chess -Guy Macon
|
tin Brown wrote:
>It is worth pointing out that no computer program ever needs to look at
>all the terminal nodes to find the best move. Alpha-beta pruning alone
>gets the search done in O(sqrt(69,000,000,000,000)) ~ 9,000,000 nodes
>(an altogether much more tractable proposition) if moves were perfectly
>sorted and a bit slower in real life. Razoring and killer move
>heuristics get another order of magnitude speed gain overall and
>singular extensions slow it down slightly when they occur but give a
>more robust standard of play.
In the context of solving chess, I think you you *do* need to look
at all of the terminal nodes. Pruning might get you to where you
are 99.999% sure, but you haven't *proved* that some stupid line
that throws away a queen and a rook doesn't lead to a win 40 moves
later unless you look at all of the terminal nodes. There are a
few lines in the tablebases that appear to me (~1900 player) to
make no sense during the first few moves. Maybe there are more
as the tablebases grow.
>And in a proof of the game theoretic outcome for chess you could not use
>any of the speculative pruning techniques.
I don't think you can use *any* pruning technique and be 100% sure.
>barring a quantum computer it will probably never be solved.
Yup. Even assuming infinite clock speed, the universe isn't big
enough to hold the list of positions/moves already evaluated,
even at one bit per subatomic particle.
--
Guy Macon
<http://www.guymacon.com/ >
|
| | | |
Date: 05 Feb 2008 18:43:35
From: Andy Walker
Subject: Re: Solving Chess -Guy Macon
|
In article <[email protected] >,
Guy Macon <http://www.guymacon.com/ > wrote:
>tin Brown wrote:
>>It is worth pointing out that no computer program ever needs to look at
>>all the terminal nodes to find the best move. Alpha-beta pruning alone
>>gets the search done in O(sqrt(69,000,000,000,000)) [...]
>In the context of solving chess, I think you you *do* need to look
>at all of the terminal nodes. Pruning might get you to where you
>are 99.999% sure, but you haven't *proved* that some stupid line
>that throws away a queen and a rook doesn't lead to a win 40 moves
>later unless you look at all of the terminal nodes. [...]
This seems to contain a fundamental misunderstanding of
what alpha-beta pruning does. It does not throw away any line
which could [however implausibly] affect the evaluation. The
example I usually give is that after 1 e4 e5 2 Ba6, suppose we
have found that 2 ... Nxa6 wins for Black. *Then* we can safely
prune 2 ... bxa6, 2 ... Qf6 and so on; no matter how good they
are, they are not going to affect the verdict that 2 Ba6 loses.
In your example, to prove that your "stupid" line that
throws away a Q&R is bad, we don't need to find *all* refutations
of it; just one will do. If in fact it leads to a win 40 moves
later, then there won't be even one refutation, so no pruning
will lose this fact; but if it is indeed just a blunder, then
then chances are that any plausible moves for the other side just
win, and only one line needs to be analysed.
>>And in a proof of the game theoretic outcome for chess you could not use
>>any of the speculative pruning techniques.
Actually, if you are using "iterative deepening", then
speculative pruning could help the efficiency of the search,
so that the next depth runs faster. All that is necessary is
that all depths are *eventually* searched without speculation.
It's OK if, say, the search to depth 100 searches some lines
only to depth 50, as long as by the time we get to depth 200,
all lines have been searched to depth 100 [etc].
>Yup. Even assuming infinite clock speed, the universe isn't big
>enough to hold the list of positions/moves already evaluated,
>even at one bit per subatomic particle.
With "infinite clock speed", then you don't need a big
universe to hold anything much. In "infinitesimal" time, a depth-
first search evaluates any position well within the storage capacity
of any modern computer [you only need a few Kbytes]. You can just
re-calculate any values you need during actual play.
--
Andy Walker
Nottingham
|
| | |
Date: 05 Feb 2008 17:47:25
From: jefk
Subject: Re: Solving Chess - infinite series
|
tin Brown wrote:
>> Agreed. The size of an exhaustive search is much bigger than
>> a tiny number like a billion billion billion.
>
well who cares ?
you know, many infinite series still have a solution,
ie can be solved in mathematics, if there is convergence.
eg. 1/2 + 1/4 + 1/8 + 1/16
no need to use supercomputers, its converging to
a solution. many other examples, btw.
now in chess, if you make a graph depicting
the average Elo vs draw percentage,
you'll see the draw percentage increasing,
until, yep,100 %, at about an Elo of approx 3500-3700
(rough estimate). My claim is we are almost there,
chess is draw, and computer chess will become
boring, unles we change the rules,
or switch to Fischer random.
yep, correspondence chess also will become boring,
in a few more years, provided i can afford a reasonable
fast Quad IntelExtreme or so, i don't think that even
a world champion like van Oostrom could beat me
with white, given enough time, eg not an intensive
simultaneous tournament.
the proof of the pudding is inthe eating,
even if i would play the whole community of
rec.games.chess.analysis in correspondence chess,
whereby they would discuss for weeks about a
best move for white, and then eg. vote with
either majority, or weighing votes by Elo,
its my belief that i would hold such a game
with black, ie, maintain a draw.
conclusion
---------
there's imho only one outcome for a weak solution
of chess, maybe achievalbe in a few decades,
and that's a dead *draw*..
regards,
jef
|
| | | |
Date: 06 Feb 2008 12:47:27
From: David Richerby
Subject: Re: Solving Chess - infinite series
|
jefk <[email protected] > wrote:
> tin Brown wrote:
>>> Agreed. The size of an exhaustive search is much bigger than
>>> a tiny number like a billion billion billion.
No, he didn't. Guy Macon wrote that text.
> you know, many infinite series still have a solution,
Irrelevant: nobody is proposing summing any infinite series. Chess is
a finite game and it requires only a finite amount of work to solve
it.
> now in chess, if you make a graph depicting the average Elo vs draw
> percentage, you'll see the draw percentage increasing, until,
> yep,100 %, at about an Elo of approx 3500-3700 (rough estimate).
I call bullshit. Top-level chess is running at, what, 60-70% draws at
average rating, say, 2700. Data should be fairly easy to find down
to, say, 2200. So you're trying to extrapolate 1000 points beyond a
500-point range. The curve could go anywhere.
> the proof of the pudding is inthe eating, even if i would play the
> whole community of rec.games.chess.analysis in correspondence chess
Even if you did that, it would prove absolutely nothing.
Dave.
--
David Richerby Swiss Disgusting Hi-Fi (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a music system but it'll turn your
stomach and it's made in Switzerland!
|
| |
Date: 05 Feb 2008 14:01:52
From: David Richerby
Subject: Re: Solving Chess
|
Guy Macon <http://www.guymacon.com/ > wrote:
> Given the assumptions above (which have not been proven right or
> proven wrong), you could start with a quantum computer that can only
> evaluate one position in one second and still solve the game of
> chess in less than a day.
Dude, if it can evaluate one position in one second, I choose for it
to evaluate the initial position. Why wait a whole day evaluating
other positions that nobody cares about? ;-)
Dave.
--
David Richerby Indelible Unholy Atlas (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a map of the world but it's also
a crime against nature and it can't
be erased!
|
| | |
Date: 05 Feb 2008 16:55:05
From: Guy Macon
Subject: Re: Solving Chess
|
David Richerby wrote:
>
>Guy Macon <http://www.guymacon.com/> wrote:
>
>> Given the assumptions above (which have not been proven right or
>> proven wrong), you could start with a quantum computer that can only
>> evaluate one position in one second and still solve the game of
>> chess in less than a day.
>
>Dude, if it can evaluate one position in one second, I choose for it
>to evaluate the initial position. Why wait a whole day evaluating
>other positions that nobody cares about? ;-)
In the context of solving chess through an exhaustive search
of the move tree (which *is* what we were talking about) the
evaluation function is rather simple. Either
[A] White is in checkmate
[B] Black is in checkmate
[C] No legal move is possible
[D] The computer needs to look deeper until all branches
(and I do mean all) end in A, B, or C.
The initial position evaluates to D.
The point is that the move tree grows exponentially and
thus will outrun the abilities of any linear computer
that is constrained to be no bigger or older than the
universe. Assuming in the year 2008 that computers
will always be linear is like assuming in the year
1008 that computation will always be done by humans
with quill pens and parchment.
If solving chess can be done by searching multiple
positions in parallel for a solution (it is not
clear whether this is true or false), and assuming
that a Quantum Computer with enough qbits to complete
that search will ever be invented (again it is not
clear whether this is true or false) the Quantum
Computer will be able to search for a solution
among 2^N possible solutions in N time. Such a
quantum computer that can perform the simple
evaluation function above in five milliseconds
(a $29.99 LCD handheld does a far more complex
evaluation function in one millisecond) would
be able to evaluate a million (10^6) positions
in 0.2 seconds, a trillion (10^12) positions in
0.4 seconds, and 10^108 positions in 5 minutes.
Given the assumptions above (which have not been
proven right or proven wrong), you could start
with a quantum computer that can only evaluate
one position in one second and still solve the
game of chess in less than a day.
Who here has proof that such a computer will
*never* be invented?
--
Guy Macon
<http://www.guymacon.com/ >
|
| |
Date: 05 Feb 2008 13:14:34
From: jefk
Subject: Re: Solving Chess -Guy macon
|
Guy Macon wrote:
> a quantum computer that can only evaluate one position
> in one second and still solve the game of chess in less
> than a day.
>
>
well spoken, they are doing research a/o at Delft Technical University
in the field of quantum computering, and slow progress is made;
commercial applications of course will still take decades or more.
anyway, chess doesn't have to be solved in a day,
it's already 'solved', since it's a draw..
:)
|
| | |
Date: 05 Feb 2008 12:59:54
From: Guy Macon
Subject: Re: Solving Chess -Guy macon
|
jefk wrote:
>anyway, chess doesn't have to be solved in a day,
>it's already 'solved', since it's a draw..
Evidence, please.
--
Guy Macon
<http://www.guymacon.com/ >
|
| | | |
Date: 05 Feb 2008 14:42:22
From: jefk
Subject: Re: Solving Chess -Guy macon
|
Guy Macon wrote:
>> anyway, chess doesn't have to be solved in a day,
>> it's already 'solved', since it's a draw..
>>
> Evidence, please.
>
>
ok, to start the 'evidence', i first claim from experience that
every erroneous book for black can be corrected
but that white also can try to accumulate small
advantages in middlegame/endgame, leading to
a win (Richerby was partly right, but not entirely);
now secondly, with Rybka analysis i claim that most
positional mistakes by black in the middlegame can be
replaced by better moves, wherey gradually the theory
of opening theory/databases will extend far into the
middle game.(it already does, in lots of variations)
third, when playing with white against a strong
engine as Rybka, it is clear that accumulating
such small advantages will consist of very small/
minimal positional advantages, worth say 0.05 pawn/move
(maybe not recognized by Rybak, but then
by the strongest player with white, eg Hydra or so)
but then leading such advantages to a *win*
will extend far into the endgame, leading to
games of eg. 200/300 or more moves,
and using positional endgame strategies,
in 'practical' ( >7 piece) endgames
the drawing strategy for black then can be simple,
eg. advancing one or more pawns as far as possible
to the first line (threatening promotion), simultaneously
of course preventing white pawn promotion,
and then defending his pawns as strong as possible,
eg. on the third line.
But.. this will lead to serious problems for white
because of the 50 move drawing rule in the endgame,
and thus the game will end in a draw, even if
white would have accumulated some small advantage.
So this is a another 'proof'/evidence -besides the arguments i
gave to confirm that the 'weak solution' of chess is a draw-
using the technique of reduction ad absurdum; see eg:
http://en.wikipedia.org/wiki/Reductio_ad_absurdum:
NB of course we now enter in the area of slow/correspondence
chess, aided by strong computers/engines and endgame theory,
but i still challenge anyone in trying to beat me with white in
such a slow (correspondence) game; maybe i'll later offer
a reward if someone would succeed.. (but i'll might
need a month for every response by black or so, so
initially i would prefer just to supply me with some apparently
winning lines for white, preferably on rec.games.chess.analysis
Sumizing/conclusion:
------------------------
*IF* white could accumulate his advantages in such
a way that he would win with perfect play, than
it only can be in very long endgames.
But.. according to the 50 move endgame draw rule,
this is *not* possible. Ergo, chess is a draw. QED
:)
best regards,
Jef
PS most strong (or super-)GM's, and probably also the
strongest correspondence players probably would confirm
my opinion, although they might disagree on
a few points whether my arguments might
be called real 'evidence' (or even a 'weak proof)
|
| | | | |
Date: 05 Feb 2008 17:15:13
From: Guy Macon
Subject: Re: Solving Chess -Guy macon
|
jefk wrote:
>
>
>Guy Macon wrote:
>>> anyway, chess doesn't have to be solved in a day,
>>> it's already 'solved', since it's a draw..
>>>
>> Evidence, please.
>
>ok, to start the 'evidence', i first claim from experience that
>every erroneous book for black can be corrected
>but that white also can try to accumulate small
>advantages in middlegame/endgame, leading to
>a win (Richerby was partly right, but not entirely);
That is not evidence that chess is already solved.
>now secondly, with Rybka analysis i claim that most
>positional mistakes by black in the middlegame can be
>replaced by better moves, wherey gradually the theory
>of opening theory/databases will extend far into the
>middle game.(it already does, in lots of variations)
That is not evidence that chess is already solved.
>third, when playing with white against a strong
>engine as Rybka, it is clear that accumulating
>such small advantages will consist of very small/
>minimal positional advantages, worth say 0.05 pawn/move
>(maybe not recognized by Rybak, but then
>by the strongest player with white, eg Hydra or so)
That is not evidence that chess is already solved.
>but then leading such advantages to a *win*
>will extend far into the endgame, leading to
>games of eg. 200/300 or more moves,
>and using positional endgame strategies,
>in 'practical' (>7 piece) endgames
That is not evidence that chess is already solved.
>the drawing strategy for black then can be simple,
>eg. advancing one or more pawns as far as possible
>to the first line (threatening promotion), simultaneously
>of course preventing white pawn promotion,
>and then defending his pawns as strong as possible,
>eg. on the third line.
That is not evidence that chess is already solved.
(It *could* be, if you were to produce such an
unbeatable strategy, but simply asserting that one
exists without proving it is not evidence that chess
is already solved.
>But.. this will lead to serious problems for white
>because of the 50 move drawing rule in the endgame,
>and thus the game will end in a draw, even if
>white would have accumulated some small advantage.
>
>So this is a another 'proof'/evidence -besides the arguments i
>gave to confirm that the 'weak solution' of chess is a draw-
>using the technique of reduction ad absurdum; see eg:
>http://en.wikipedia.org/wiki/Reductio_ad_absurdum:
You have not formulated a valid reduction ad absurdum argument.
>NB of course we now enter in the area of slow/correspondence
>chess, aided by strong computers/engines and endgame theory,
>but i still challenge anyone in trying to beat me with white in
>such a slow (correspondence) game; maybe i'll later offer
>a reward if someone would succeed.. (but i'll might
>need a month for every response by black or so, so
>initially i would prefer just to supply me with some apparently
>winning lines for white, preferably on rec.games.chess.analysis
No game that you play is evidence that chess is already solved.
>Sumizing/conclusion:
>------------------------
>*IF* white could accumulate his advantages in such
>a way that he would win with perfect play, than
>it only can be in very long endgames.
>But.. according to the 50 move endgame draw rule,
>this is *not* possible.
Evidence, please.
>Ergo, chess is a draw. QED
You have not shown it to be a draw
>PS most strong (or super-)GM's, and probably also the
>strongest correspondence players probably would confirm
>my opinion, although they might disagree on
>a few points whether my arguments might
>be called real 'evidence' (or even a 'weak proof)
Opinions and arguments are not evidence or proof.
--
Guy Macon
<http://www.guymacon.com/ >
|
| | | | | |
Date: 06 Feb 2008 12:07:12
From: David Richerby
Subject: Re: Solving Chess -Guy macon
|
Guy Macon <http://www.guymacon.com/ > wrote:
> jefk wrote:
> >http://en.wikipedia.org/wiki/Reductio_ad_absurdum:
>
> You have not formulated a valid reduction ad absurdum argument.
Though he has successfully reduced himself to absurdity.
Dave.
--
David Richerby Expensive Generic.com (TM): it's like
www.chiark.greenend.org.uk/~davidr/ an E-commerce portal but it's just
like all the others and it'll break
the bank!
|
| | | | |
Date: 05 Feb 2008 09:25:48
From: Kenneth Sloan
Subject: Re: Solving Chess -Guy macon
|
jefk wrote:
> Guy Macon wrote:
>>> anyway, chess doesn't have to be solved in a day,
>>> it's already 'solved', since it's a draw..
>>>
>> Evidence, please.
>>
>>
>
> ok, to start the 'evidence', i first claim
He asked for "evidence", not "claims".
--
Kenneth Sloan [email protected]
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
|
| | | | |
Date: 05 Feb 2008 14:47:10
From: David Richerby
Subject: Re: Solving Chess
|
jefk <[email protected] > wrote:
> with Rybka analysis i claim that most positional mistakes by black
> in the middlegame can be replaced by better moves, wherey gradually
> the theory of opening theory/databases will extend far into the
> middle game.(it already does, in lots of variations)
You're begging the question again. A move is only a `mistake' if
there is a better move available so, by calling them `mistakes', you
are presupposing that your drawing strategy exists. However, if chess
actually is a win for White, there's no such thing as a `mistake' by
Black because every move leads to a forced loss.
> third, when playing with white against a strong engine as Rybka, it
> is clear that accumulating such small advantages will consist of
> very small/ minimal positional advantages, worth say 0.05 pawn/move
> (maybe not recognized by Rybak, but then by the strongest player
> with white, eg Hydra or so)
>
> but then leading such advantages to a *win* will extend far into the
> endgame, leading to games of eg. 200/300 or more moves, and using
> positional endgame strategies, in 'practical' (>7 piece) endgames
If chess is a win for white, these `small' advantages do not exist.
There is only one advantage: `White wins the game'. Again, you're
putting the cart before the horse.
> the drawing strategy for black then can be simple, eg. advancing one
> or more pawns as far as possible to the first line (threatening
> promotion), simultaneously of course preventing white pawn
> promotion, and then defending his pawns as strong as possible,
> eg. on the third line.
If chess is that simple, I really suggest you go become World Champion
and make some money out of the game. If you can always manage to get
a couple of pawns onto the sixth rank, there's a very high chance that
your opponent will blunder and lose the game, even if he has a
theoretical draw.
> So this is a another 'proof'/evidence -besides the arguments i gave
> to confirm that the 'weak solution' of chess is a draw-
You made no such argument. If you believe you did, then either you do
not understand your argument or you do not understand what `weak
solution' means.
> Sumizing/conclusion:
> ------------------------
> *IF* white could accumulate his advantages in such a way that he
> would win with perfect play, than it only can be in very long
> endgames.
But these `small advantages' do not exist in game theory. To say `I
have a small advantage' is to say that the position appears to be
unbalanced in a way that gives you a higher probability of making a
mistake. But in `perfect play', there is no probability and there are
no mistakes.
> PS most strong (or super-)GM's, and probably also the strongest
> correspondence players probably would confirm my opinion
Yes, most strong players will probably agree that chess is a draw.
> although they might disagree on a few points whether my arguments
> might be called real 'evidence' (or even a 'weak proof)
There's no such thing as a `weak proof', any more than there's such a
thing as being `slightly pregnant'. A proof is a proof.
Dave.
--
David Richerby Sumerian Projector (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ 16mm film projector that's really old!
|
| | | | | |
Date: 05 Feb 2008 17:04:59
From: Guy Macon
Subject: Re: Solving Chess
|
David Richerby wrote:
>There's no such thing as a `weak proof', any more than there's such a
>thing as being `slightly pregnant'. A proof is a proof.
Not to take away from the rest of your post, which was one of the
clearest explanations of the difference between a computer playing
well and a computersolving chess, take a look at
[ http://en.wikipedia.org/wiki/Solved_game ]:
A two player game can be "solved" on several levels:
Ultra-weak
In the weakest sense, solving a game means proving whether the first
player will win, lose, or draw from the initial position, given
perfect play on both sides. This can be a non-constructive proof
(possibly involving a strategy stealing argument) that may not
actually help determine this perfect play.
Weak
More typically, solving a game means providing an algorithm that
secures a win for one player, or a draw for either, against any
possible moves by the opponent, from the beginning of the game.
Strong
The strongest sense of solution requires an algorithm which can
produce perfect play from any position, i.e. even if mistakes have
already been made on one or both sides.
Given the rules of any two-person game with a finite number of
positions, one can always trivially construct a minimax algorithm that
would exhaustively traverse the game tree. However, since for many
non-trivial games such an algorithm would require an infeasible amount
of time to generate a move in a given position, a game is not
considered to be solved weakly or strongly unless the algorithm can be
run by existing hardware in a reasonable time.
Also see: V. Allis, _Searching for Solutions in Games and
Artificial Intelligence_ (Department of Computer Science,
University of Limburg, 1994.)
--
Guy Macon
<http://www.guymacon.com/ >
|
| | | | | | |
Date: 05 Feb 2008 17:38:25
From: David Richerby
Subject: Re: Solving Chess
|
Guy Macon <http://www.guymacon.com/ > wrote:
> David Richerby wrote:
>> There's no such thing as a `weak proof', any more than there's such
>> a thing as being `slightly pregnant'. A proof is a proof.
>
> Not to take away from the rest of your post, which was one of the
> clearest explanations of the difference between a computer playing
> well and a computersolving chess
Thank you.
> take a look at
> [ http://en.wikipedia.org/wiki/Solved_game ]:
>
> [definitions of Ultra-weak, weak and strong solution of a game
> snipped.]
You misunderstand, slightly. The solution may be ultra-weak, weak or
strong. However, the *proof* of the solution is a proof. It must be
fully rigorous or it is not a proof. One can have a proof that a game
is weakly solved but one can't have a `weak proof' of anything.
Dave.
--
David Richerby Addictive Surprise Newspaper (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a daily broadsheet but not
like you'd expect and you can never
put it down!
|
| | | | | | | |
Date: 05 Feb 2008 23:06:39
From: Guy Macon
Subject: Re: Solving Chess
|
David Richerby wrote:
>
>Guy Macon <http://www.guymacon.com/> wrote:
>
>> David Richerby wrote:
>
>>> There's no such thing as a `weak proof', any more than there's such
>>> a thing as being `slightly pregnant'. A proof is a proof.
>>
>> Not to take away from the rest of your post, which was one of the
>> clearest explanations of the difference between a computer playing
>> well and a computersolving chess
>
>Thank you.
>
>> take a look at
>> [ http://en.wikipedia.org/wiki/Solved_game ]:
>>
>> [definitions of Ultra-weak, weak and strong solution of a game
>> snipped.]
>
>You misunderstand, slightly. The solution may be ultra-weak, weak or
>strong. However, the *proof* of the solution is a proof. It must be
>fully rigorous or it is not a proof. One can have a proof that a game
>is weakly solved but one can't have a `weak proof' of anything.
You are entirely correct. Thanks for clarifying my error. <big smile >
--
Guy Macon
<http://www.guymacon.com/ >
|
| | | | | |
Date: 05 Feb 2008 16:59:36
From: jefk
Subject: Re: Solving Chess/endgame rules/theory
|
David Richerby wrote:
> by calling them `mistakes', you are presupposing that your drawing strategy exists.
not only me, it's common knowledge: quoting from:
http://en.wikipedia.org/wiki/Draw_(chess)
'its *generally* believed that a perfectly played game of
chess will always result in a draw' (GM Joel Benjamin)
> However, if chess actually is a win for White,
impossible because of the 50 move endgame rule,
see the above article, where some history about
this Fide rule is discussed (first they extended it,
but not now anymore)
> If chess is a win for white, these `small' advantages do not exist.
>
impossible, proven with the 'reduction ad absurdum argument'
and verified by my research.
but you may try to falsify it by starting a correspondence game
with me if you like; i bet 1000 dollars you can't beat me
:)
> If chess is that simple, I really suggest you go become World Champion
>
i'm not claiming i'm such a good player myself, i claim that
the top engine Rybka, a programming work of genius,
is approaching perfect chess and as a result we
are becoming aware that chess indeed is a draw
(at least i became aware of that fact..; you may dispute
my reasoning, but its a simple matter of common sense)
> and make some money out of the game.
well i dont even expect to make money out of my (revsied) book
(soon to be published); at best it will sell like 'one jump ahead'
about checkers/Chinook program
> of pawns onto the sixth rank, there's a very high chance that
> your opponent will blunder
that was just an example, there are many drawing strategies,
eg. building a fortress, exploiting unequal bishops, etc.
(see Dvoretzky, endgame manual)
> you do not understand what `weak solution' means.
>
well i can read and have seen that for checkers they claim
that a weak solution (with the program Chinook) indicates\
a draw; in chess, we haven't achieved such a method yet,
but if we will, then a draw will be the outcome.
> `small advantages' do not exist in game theory.
ok, there's either an advantage which results in a win,
eg. losing a knight, bishop or >3 pawns by black,
or it's a draw, no big deal.
> Yes, most strong players will probably agree that chess is a draw.
>
and not for nothing; they have practical experience,
also with endgames, and know that the likelyhood of
a very long (eg 20 moves) winning combination is very small;
and if it would exist, than in a next game black simply
could prevent it by playing another move just before
that combination.... (another sort of 'proof' by contradiction..)
> There's no such thing as a `weak proof',
ok, weak *solution*, see above, anyway, our discussion
is leading to nowhere, except a discussions about
scientific methods in game theory. instead i rather
would be interested if chess could be solved
it the 50 draw move would be abolished for
computer chess. Or if there exist variants in
Fischer random chess which *could* be solved..
but anyway, David R, if you like to solve the game
for whie, which move you like to start your game
against me, a bookbuilding rybka/jefk centaur ?
e4, d4 or Nf3 maybe ? (just curious)
good luck anyway,
jef
PS you are suggesting that i'm reversing logic in my
'proof' whereas i just claim it's evident, using some other
type of logic, eg. using this reduction ad aburdum argument;
similar as eg. an argument in philosophy/astrophysics
*why* do we (humans) exist ?
well, becoz of the antropomorphic argument,
if we wouldnt exist, we couldt pose such a
question anyway .. :)
|
| | | | | | |
Date: 08 Feb 2008 18:18:05
From: johnny_t
Subject: Re: Solving Chess/endgame rules/theory
|
jefk wrote:
>>
> i'm not claiming i'm such a good player myself, i claim that
> the top engine Rybka, a programming work of genius,
> is approaching perfect chess and as a result we
> are becoming aware that chess indeed is a draw
> (at least i became aware of that fact..; you may dispute
> my reasoning, but its a simple matter of common sense)
This in particular is a poor argument. Against other computers, but
even against other "the same" Rybkas, many many games under test, black
and white have been decisive. Nowhere EVEN CLOSE to being able to be
usable as anecdotal evidence of the drawing nature of the game.
|
| | | | | | |
Date: 05 Feb 2008 17:35:35
From: David Richerby
Subject: Re: Solving Chess/endgame rules/theory
|
jefk <[email protected] > wrote:
> David Richerby wrote:
>> by calling them `mistakes', you are presupposing that your drawing
>> strategy exists.
>
> not only me, it's common knowledge: quoting from:
> http://en.wikipedia.org/wiki/Draw_(chess)
>
> 'its *generally* believed that a perfectly played game of
> chess will always result in a draw' (GM Joel Benjamin)
I would emphasize the word `believed' rather than `generally.' A
general belief in some statement is by no means the same thing as
that statement being `common knowledge'.
The Wikipedia article (in the most recent version at time of posting:
22:03 on 23rd January 2008) does *not* attribute that quote to GM
Benjamin.
>> However, if chess actually is a win for White,
>
> impossible because of the 50 move endgame rule, see the above
> article, where some history about this Fide rule is discussed (first
> they extended it, but not now anymore)
Thank you. I'm well aware of the fifty-move rule and it's history.
However, you have done nothing to establish that the fifty-move rule
prevents White from winning against any defence Black has to offer.
>> If chess is a win for white, these `small' advantages do not exist.
>
> impossible, proven with the 'reduction ad absurdum argument' and
> verified by my research.
No, really. If chess is a forced win, there is no such thing as a
`small advantage'. Every position reachable according to White's
winning strategy gives White an overwhelming advatage: specifically,
that he has a strategy to win the game from that position from any
such position against any possible counterplay.
> but you may try to falsify it by starting a correspondence game
> with me if you like; i bet 1000 dollars you can't beat me :)
I decline. The game-theoretic outcome of chess depends neither on my
skill at the game, your skill at the game nor on the willingness of
either of us to gamble.
>> you do not understand what `weak solution' means.
>
> well i can read and have seen that for checkers they claim that a
> weak solution (with the program Chinook) indicates a draw; in chess,
> we haven't achieved such a method yet, but if we will, then a draw
> will be the outcome.
To be clear, to have a `weak solution' means that the outcome of the
game from the initial position is known and a strategy is known to
achieve that result from the initial position (and, of course, from
any position that can arise according to the strategy).
(For reference, `ultra-weak solution' means that the outcome is known
but no strategy is known. `Strong solution' means that the outcome is
known from every possible position, with corresponding strategies.)
>> `small advantages' do not exist in game theory.
>
> ok, there's either an advantage which results in a win, eg. losing a
> knight, bishop or >3 pawns by black, or it's a draw, no big deal.
You do not know that the loss of a minor piece or three pawns
guarantees a loss. It is overwhelmingly likely that it does in most
positions but it is conceivable that there is a winning strategy and
that some lines of that strategy involve sacrificing everything but a
knight, which delivers smothered mate.
>> Yes, most strong players will probably agree that chess is a draw.
>>
> and not for nothing; they have practical experience, also with
> endgames, and know that the likelyhood of a very long (eg 20 moves)
> winning combination is very small; and if it would exist, than in a
> next game black simply could prevent it by playing another move just
> before that combination.... (another sort of 'proof' by
> contradiction..)
It is no sort of a proof by anything! A winning strategy means a
strategy that wins against any possible counterplay. If Black plays a
different move before the combination, a winning strategy will give
White a different combination to play to win.
>> There's no such thing as a `weak proof',
>
> ok, weak *solution*, see above, anyway, our discussion is leading to
> nowhere, except a discussions about scientific methods in game
> theory.
Well, what on earth did you expect a discussion on the solution of
chess to be about? The question itself is a question of game theory.
> Or if there exist variants in Fischer random chess which *could* be
> solved..
Solving any individual opening set up of FRC is, in principle, no
harder than solving FIDE chess. (Well, it's exactly 960 times harder
but that's not really significant.)
> but anyway, David R, if you like to solve the game for whie, which
> move you like to start your game against me, a bookbuilding
> rybka/jefk centaur ?
We've been through this several times.
> PS you are suggesting that i'm reversing logic in my 'proof' whereas
> i just claim it's evident, using some other type of logic, eg. using
> this reduction ad aburdum argument;
You are making two arguments. The first one, that evidence from
strong players *suggests* that chess is a draw, I agree with
completely. The second one is a bunch of hocus pocus in which you
attempt to claim, via every logical fallacy under the sun, some sort
of proof that just isn't there.
> similar as eg. an argument in philosophy/astrophysics *why* do we
> (humans) exist ? well, becoz of the antropomorphic argument, if we
> wouldnt exist, we couldt pose such a question anyway .. :)
You mean the anthropic argument.
Dave.
--
David Richerby Portable Poetic Atom Bomb (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a weapon of mass destruction
but it's in verse and you can take
it anywhere!
|
| |
Date: 05 Feb 2008 11:51:20
From: David Richerby
Subject: Re: Solving Chess
|
Guy Macon <http://www.guymacon.com/ > wrote:
> Note: in the US a trillion is 1.0E+12 (1,000,000,000,000) -tera
> while a UK trillion is 1.0E+18 (1,000,000,000,000,000,000) -exa
I don't think that's true any more -- UK usage on this matter
converged with the US years ago.
Dave.
--
David Richerby Swiss Beer (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ refreshing lager but it's made in
Switzerland!
|
|
