Author: Vincent Vega
Date: 17:40:58 12/26/00
Go up one level in this thread
On December 24, 2000 at 12:55:28, Robert Hyatt wrote: >On December 24, 2000 at 02:23:29, Vincent Vega wrote: > >>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: >>>> >>>> >>>>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. >> > > >Not exactly. How are you going to use it? IE take a position from a game >you played and go ask the program "is this won, lost or drawn?" If so, then >your idea won't fly. Because there the game history would be critical. We >would need to know _how_ you reached that position, not just the position >itself. And databases don't store that. Nor is it possible to do so. To do >this for simple 5-piece endings would be a _huge_ collection of files. Perhaps >larger than all the disks on the planet combined. > > Sorry if I was unclear, I was still talking about the "simpler" problem of deciding the result of chess or making computer play perfectly from the starting position. Only the harder problem requires taking into account at least some of game's history. If I'm not mistaken, the solution of the simpler problem doesn't require this info. > > >>> >>>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). >> > >See above. 7.5 gigs for 5 piece files _without_ any information about >repetitions or 50 move counters. I would think that if you _cube_ that >number you won't be close to storing full information. And there is no way >to cube that number with any technology available today... > Again, I was talking about the simpler problem that doesn't require game history to be stored with the position in a tablebase. > > >>> >>> >>>> >>>>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. > > >I am certain that no matter how fast we travel, we won't ever reach the edge >of the universe, since there is no edge. Solving chess is just as difficult. > > > > >> >>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. > > >Yes... but I have a pretty good idea how big this tree is... and I don't care >if you can shrink it by any factor you want, it is still too big to think about >when the number will be larger than the number of atoms in the known universe. The number of positions needed to solve the simpler problem of making computer play perfectly from the starting position is definitely less than 1e47 and the numbers I've heard quoted for the number of atoms in the universe were over 1e78.
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.