Author: Vincent Vega
Date: 23:23:29 12/23/00
Go up one level in this thread
On December 23, 2000 at 23:40:29, Robert Hyatt wrote: >On December 23, 2000 at 21:42:55, Vincent Vega wrote: > >>On December 23, 2000 at 17:56:23, Robert Hyatt wrote: >> >>>On December 23, 2000 at 14:41:37, Uri Blass wrote: >>> >>>>On December 23, 2000 at 12:44:52, Robert Hyatt wrote: >>>> >>>>>On December 23, 2000 at 12:25:18, Uri Blass wrote: >>>>> >>>>>>On December 23, 2000 at 09:01:29, Joshua Lee wrote: >>>>>> >>>>>>>this is over a google and even if your program could search at 5 trillion nodes >>>>>>>per second it wouldn't solve chess in your lifetime. >>>>>>> >>>>>>> 64^64 is one number that comes to mind 3.9402006196394479212279040100144e+115 >>>>>> >>>>>>The number of leagl positions is clearly smaller than 64^64. >>>>>> >>>>>>I do not understand why do you think about 64^64. >>>>>> >>>>>>Uri >>>>> >>>>> >>>>>I still think 10^120 is a reasonable estimate, because a position is not just >>>>>made up of the pieces on the board. >>>> >>>>In order to find if chess is a win for one side or a draw you need only >>>>tablebases for all the positions in the board when the position is made only of >>>>the pieces on the board. >>>> >>> >>> >>>That isn't true. If you do that, you will draw won positions, because >>>you will follow a path that is a mate in N, but it repeats the position >>>for the third time before you get to move N. Ditto for 50 move draws >>>on deep mates. To do this _right_ the history has to be included. >>> >> >>This is clearly wrong. Chess has a well defined starting position, so you don't >>need to be able to figure out the best move in every possible position with its >>associated history to find out if chess is 1-0, 0-1, or 1/2-1/2. > >If you are doing a tablebase, you are right. But that isn't the question being >asked. It was "how many positions are there?" And for that, my answer is >correct. Because a position X that was reached one way is _not_ the same as >the same position X reached via another sequence of moves. All according to >the normal rules of chess. > > Note that in the part you replied to, Uri said, "In order to find if chess is a win for one side or a draw..." So his statement was clearly true and your reply "That isn't true" was incorrect. >> >>Adding 50-move and 3-fold repetition conditions has no effect whatsoever on >>whether computer will be able to play perfect chess. If you play the game >>perfectly from the beginning, and there is a win for one side, there won't ever >>be any repetitions of positions. > > >You are aware that tablebases do _not_ handle this case at present? Distance >to mate is going to fail when the mate can't be done with the 50 move rule. >Distance to conversion isn't any better at present, as the 50 move rule isn't >considered a "conversion" and they fail in the same way... Whether current tablebases include this information is irrelevant, since we are talking theory for now anyway. All that matters is that this info can be added and utilized. > >It is _essential_ to include this information or any tablebase with 32 pieces >will simply be useless unless the rules of chess are changed from their present >state. > > And if you follow the algorithm that chooses >>the next move by finding the minimum distance to resetting the 50-move counter >>among all moves that lower the distance to mate, you won't need to know the game >>history at all. > >That won't work for reasons that are well-known and often discussed. There is >no "resetting the 50-move-counter" factored in to current tablebases. And >unless a new 'standard' is created (using both DTM _and_ DTC) the problem is >insolvable. (and of course, conversion has to include 50 moves as a factor.) How is that a problem? These file formats aren't written in stone. I don't see how altering them or creating a program that relies on modified formats is any significant obstacle. It's not like we have to hurry because somebody is ready to create a 32-piece tablebase tomorrow and Crafty needs to use it (actually a 31 or a 30-piece tablebase would be bigger). > > >> >>I don't find figuring out when computer will be able to play perfectly from any >>possible position nearly as important as knowing when a computer will play >>perfectly from the only position that really counts - starting position. > > >First, that will _never_ happen. Unless you consider a time-span long enough >for the sun to burn out, for starters. But as to the number of different >positions in the game, it is _far_ larger than most realize... due to the >rules we have to play under. Never is a very long time. I am not going to even try to predict what advances may happen in the future. The number of positions that can be reached when one side plays perfect chess from the start is certainly many orders of magnitude smaller than the total number of positions. Some patterns in some types of positions may be found and exploited, reducing generation time or reducing the storage needs. We know that Grover's quantum search algorithm makes a classical O(N) problem into an O(N^(1/2)) problem and of course there is Shor's quantum factor finding algorithm. Very small quantum computers were proved possible. Real breakthroughs are rarely foreseen and many people were stunned when these two algorithms were announced. Will a practical quantum computer ever exist and will quantum algorithms apply to solving chess? I don't know. We can make guesses but that's all they are.
This page took 0 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.