Home 
Search 
Today's Posts 
#1




Solving Chess Guy macon
Sanny wrote: In Chess after every move new 3040 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 nth 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




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




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




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




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




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




Solving Chess Guy macon
In message , Guy Macon
writes Sanny wrote: In Chess after every move new 3040 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 nth 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. Alphabeta 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 alphabeta can only cut the branching factor to 810x 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 alphabeta 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 110s. The best stateoftheart 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




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




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 +12059322213 University of Alabama at Birmingham FAX +12059345473 Birmingham, AL 352941170 http://KennethRSloan.com/ 
#10




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  


Similar Threads  
Thread  Forum  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General)  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General)  
rec.games.chess.misc FAQ [2/4]  rec.games.chess.misc (Chess General) 