Author: Angrim
Date: 22:39:57 05/11/01
Go up one level in this thread
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
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.