Author: Robert Hyatt
Date: 09:55:28 12/24/00
Go up one level in this thread
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: >>> >>>>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. Correct in that context... sorry... > >>> >>>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. >> >>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... >> >> >>> >>>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.
This page took 0.01 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.