Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old February 5th 08, 10:46 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2004
Posts: 834
Default 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/


  #2   Report Post  
Old February 5th 08, 11:51 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default 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!
  #3   Report Post  
Old February 5th 08, 12:14 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Feb 2008
Posts: 36
Default 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..



  #4   Report Post  
Old February 5th 08, 12:59 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2004
Posts: 834
Default 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/

  #5   Report Post  
Old February 5th 08, 01:42 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Feb 2008
Posts: 36
Default 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

Summarizing/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)


  #6   Report Post  
Old February 5th 08, 02:01 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default 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!
  #7   Report Post  
Old February 5th 08, 02:42 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Jul 2006
Posts: 1,015
Default Solving Chess -Guy macon

In message , Guy Macon
writes

Sanny wrote:

In Chess after every move new 30-40 moves are generated.


Which is roughly true during the middlegame.

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.


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.

Rough timings for Shredder10 & Fritz8 starting from the initial position
a
Shredder10 Fritz 8
ply time Nodes time Nodes
10 7s 2M 9s 7M
12 23s 8M 60s 48M
13 60s 15M 2m 110M
14 2m 30M 6m 500M
15 4m 60M 18m 1.5G

Shredder considers many fewer nodes than Fritz but spends more time at
each one (and it is even more so for Rybka). Pure alpha-beta can only
cut the branching factor to 8-10x per ply so additional tricks are being
used.

And in a proof of the game theoretic outcome for chess you could not use
any of the speculative pruning techniques.

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.


UK Trillion was declared equal to the US usage by the government of
Harold Wilson in about 1962.

Say Each Move Generation needs 1000 Calculations.

So 10 depth search needs 590,000 Trillion Calculations.


69,000 Trillion Calculations.


Although a smart alpha-beta pruned search would only require detailed
analysis of something like 9,000,000 terminal nodes to get exactly the
same result to ply 10. Taking something roughly between 1-10s.

The best state-of-the-art chess engines run on domestic consumer
hardware at 3GHz can typically reach 24ply in 2 days to a week. Half
that time on a dual CPU machine and not quite a quarter on a quad CPU.

You might hope to reach ply 30 or so in about a year on a home PC.
(and that is not really enough to get out of the opening book databases)

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.


Unless there is some very odd forced move sequence it seems to me like
there will come a time when the endgame tablebases would be relevant for
perfect play - that does put some bounds on the shortest perfect game.

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.


Indeed and barring a quantum computer it will probably never be solved.

Regards,
--
Martin Brown

--
Posted via a free Usenet account from http://www.teranews.com

  #8   Report Post  
Old February 5th 08, 02:47 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Apr 2005
Posts: 2,598
Default Solving Chess

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

Summarizing/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!
  #9   Report Post  
Old February 5th 08, 03:25 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Oct 2006
Posts: 1,305
Default 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
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/
  #10   Report Post  
Old February 5th 08, 03:59 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Feb 2008
Posts: 36
Default 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 ..
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 February 19th 06 05:44 AM
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 November 18th 05 05:36 AM
rec.games.chess.misc FAQ [2/4] [email protected] rec.games.chess.misc (Chess General) 0 November 3rd 05 05:30 AM


All times are GMT +1. The time now is 12:52 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017