Author: Jesper Antonsson
Date: 15:36:18 11/03/02
Go up one level in this thread
On November 03, 2002 at 16:04:38, martin fierz wrote: >the number of positions (10^40) is much smaller than the number of games >(10^120) - i'll just assume these numbers are correct, i have no idea actually. >10^40 is the size of the "state space", while 10^120 is the size of the "search >space". now here comes the important part: if you want to solve chess by >searching deep, you need to beat the search space, and not the state space >(that's to counter your argument that you don't need to store many positions >because of alpha-beta. if you don't want to store anything, you will not >remember that you have already seen a certain position and have to go through >everything over and over again). >this looks completely unfeasible (10^120... even if a 10^21x speedup is true). >so the only reasonable alternative is to beat the state space. which means you >would have to build huge endgame databases. let's say, you can build huge >endgame databases, e.g. with 10^30 positions in them. Your argument is basically valid, but you are also a tad pessimistic. While I don't think we'll ever get farther than 7 or 8-men endgame databases, remember that alpha-beta not only hides a lot of the search space, it also hides a lot of the state space. With alpha-beta, we only have to search the square root of the number of moves we have to search without, and perhaps the same holds true for the state space. If so, a hash table of "merely" 10^20 positions may suffice to "beat the state space". With one atom per position, that hash table would weigh very little indeed. With that said, I agree that Moores law won't last long enough to enable us to solve chess. Perhaps with a new paradigm. (Also, I won't call chess "solved" if it's done with the aid of our standard hash algorithms that stores signatures and may get an undetected collision every once in a while. We have to store enough information in each entry to be sure we won't get errors, and that will demand some extra space.)
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.