Author: Robert Hyatt
Date: 22:52:05 05/11/01
Go up one level in this thread
On May 12, 2001 at 01:39:57, Angrim wrote: >On May 12, 2001 at 00:56:40, Dann Corbit wrote: > >>On May 12, 2001 at 00:48:17, Angrim wrote: >> >>>On May 11, 2001 at 22:24:21, Robert Hyatt wrote: >>> >>>>On May 11, 2001 at 15:49:19, Angrim wrote: >>>> >>>>>On May 11, 2001 at 03:29:43, Dann Corbit wrote: >>>>> >>>>>>On May 11, 2001 at 01:49:03, Angrim wrote: >>>>><snip> >>>>>>>If your goal is to determine how hard it is to solve chess, then yes. >>>>>>>Rather then go into a lengthy rant here, let me give an example. >>>>>>>The following position has pawns advanced a total of 4 squares, so >>>>>>>subtract 4*50 from the max depth, and your math suggests that there are >>>>>>>38^(5900 -200) total games of chess that can result from this position. >>>>>>>However, the position is trivial. No need for sqrt(38^(5900 -200)) >>>>>>>positions to be searched or stored... >>>>>>> >>>>>>>[D]rnbqkbnr/pppp1ppp/4p3/8/6P1/5P2/PPPPP2P/RNBQKBNR b KQkq g3 0 2 >>>>>> >>>>>>Yet there are many quintillions of quintillions of qintillions of games that can >>>>>>sprout from here. >>>>>> >>>>>My point being that if your goal is to solve this position, then all >>>>>but 1 of those games is totally irrelevant.\\\\\ >>>> >>>> >>>> >>>>Unfortunately they are _not_. Because you have to _prove_ that the best >>>>move is best. And to the best of my knowledge, there is no "oracle" that >>>>will give us perfect move ordering so it is not just likely, it is highly >>>>probable that the winning move won't be searched first. Maybe it will be >>>>searched by the 1/2 way mark at this play, maybe it will be last. But >>>>if it isn't first, you have a HUGE tree to search first... >>>> >>>>That's the way alpha/beta works... not best-first but alpha/beta... >>>> >>>> >>> >>>did you happen to look at the position? >>>You need to look at exactly 1 line to prove that it is the best line. >>>If you are unlucky you might need to look at 30 or so other lines first >>>to find this line, >>>but my point was that the "many quintillions of quintillions of >>>qintillions of games" that can result from this position are irrelevant. >>>The fact that with worst play games thousands of moves long could result >>>from this line is also irrelevant. >>>Yet, much of the discussion of this subject to this point has been >>>about how many legal games there are, and the max depth of such games. >> >>Well, the fool's mate is a pretty rare condition. You must remember that it >>won't be a human looking at the line, but a computer. It is possible for the >>computer to get move ordering wrong. Now, in a simple case like this, even if >>you screw it up completely, you will still find the answer after only one ply. >> > >I picked the fools mate because it is easy for a human to understand the >position. > >>So, the real question seems to be: >>What percentage of random board positions are one move away from checkmate? >>We could expand the question to ask: >>What percentage of random board positions are <n> moves away from checkmate? >>for various values of n. > >Well, that wasn't the question that I was discussing, but it could >be an interesting one in its own right. > >> >>Obviously, once you have killed a branch, you don't need to analyze it any more. >> >>Who knows, maybe there's only a few trillion sensible moves in the whole game >>tree. >> >>I still think finding them (even if that's all there were) is out of reach >>forever, but maybe I'm wrong. > >I think that if you only store values for positions that can not be >solved with 1 second of cpu search, and only for positions where white >has not made any mistakes, then there may be less than a trillion >positions whose values need to be stored. This is feasible with current >tech, however(of course) finding which positions those are and what >their values are is difficult. I expect that it will be possible within >my lifetime, but probably not in the next ten years. > >Angrim Sorry, but that "one trillion" is simply impossible. I don't have any difficulty seeing that many 'quiet' (non-lost/non-won) positions with just 6 pieces on the board. If the game were only that simple, it would already be solved.
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.