Author: J. Wesley Cleveland
Date: 13:50:28 05/11/01
Go up one level in this thread
On May 11, 2001 at 09:46:30, Robert Hyatt wrote: >On May 10, 2001 at 10:10:59, Uri Blass wrote: > >> >>I did not talk about chess but about chess without the 50 move rule that is not >>exactly the same game. >> >>I claimed that even chess without the 50 move rule can be solved in finite time. >>The finite time is of course not practical with today's hardware. >> > >The finite time is not practical for _any_ hardware that will ever exist. >Without the 50 move rule, the size of the chess tree is so incredibly large >that it can't be stored _or_ computed. > > > >>With the 50 move rule things are even more easy because searching 5000 plies >>forward is enough. > >I assume you mean 10,000+ plies. or 5000+ moves. 49 moves, then a pawn push, >which gives 24 * 50, then 8 more cycles each followed by a pawn takes pawn >capture, then 40 more cycles each followed by a pawn push, and now we have >24 pieces on the board so we get 22 more cycles followed by captures. that is >24 + 8 + 40 + 22 is 94 if I did that right. There is probably a way to extend >this a little. Which means maybe 100 * 50 or 5000 moves or 10,000 plies. > >That makes a _big_ tree. 38^10000 I don't think you will find any possible >way to store that. Even assuming 10^90 atoms in the universe. That number >is bigger. Even if you assume you can store a gigabyte per atom... Or 10 >gigs per quark. > > > >> >> That is getting very >>>close to the number of atoms in the universe. How are you going to store that >>>information? >>> >>>and I am not convinced 10^50 is the right number. There are positions and there >>>are positions... the history (or move path) to a position is just as important >>>to its identity as is the location of each of the pieces. Because without this, >>>repetitions and 50-move rule won't work at all. >> >>Repetitions are irrelevant for solving chess and you can ignore them because if >>white can win the game with repetition then white can win the game also without >>repetition. >> >>It is relevant for analysing games when the sides did mistakes but not for >>finding if chess is a draw or a win for white. >> > > >Find the flaw in my math above... Okay. With exact results, you only need the number of plies to the next capture or pawn move stored with each position to solve the 50 move rule problem. Repititions are a non-problem, i.e. if from position A, you know that position B is a forced win, *but* the win leads back through A, you would never choose to move to B, because you would already know there is a shorter win from A. > > >>With the 50 move rule it is enough to search 12600 plies forward in order to >>find if chess is a draw or not after the right moves because if you find no >>forced mate after 12600 plies then you can find no forced mate in more plies >>because in every line of more than 12600 plies the loser can claim a draw by the >>50 move rule. >> >>I get the number 12600 by the fact that there are at most 96 pawns moves and >>there are at most 30 captures. >> >>In every 100 plies there must be at least 1 capture or 1 pawn move otherwise the >>result is a draw from theoretical point of view and the case when both sides do >>not want a draw is not relevant because it is clear that at least one of the >>sides cannot get more than it and the search algorithm of programs do not >>continue to analyze positions after 100 quiet moves. > > >I know of plenty of programs that continue to search after 100 moves. You >+must+ do this or you will die due to lag problems on a server... > > > > > >> >>It means that in 12600 plies there must be 30 captures and it means that it is a >>draw because only kings are in the board. >> >>Practically the number is even smaller than it because if you assume 96 pawn >>moves at least 4 of the pawn moves are captures and it is possible to prove that >>even 12200 is enough. >> >>Uri > > >I don't disagree with that analysis. But it doesn't change a thing about >whether chess is O(1) or not... I have patiently waited for someone to cite >a reference that says an algorithm is exponential in D if and only if D is >unbounded. Exponential behavior predicts how the algorithm will behave for >all time. Using the nonsensical definition of O(1) I could easily claim that >_all_ algorithms are O(1) because of several reasons: > >1. No useful algorithm will work on infinite input. > >2. Every useful algorithm has finite input. I have previously given >examples of weather forecasting, CFD, sorting, etc. > >3. Every algorithm has a bounded run-time, because the universe won't last >forever. > >But until then, I want a methodology to determine how much more computation >I have to do when I increase the size of the data.
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.