Author: Robert Hyatt
Date: 06:46:30 05/11/01
Go up one level in this thread
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... >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.