Author: Dann Corbit
Date: 21:56:40 05/11/01
Go up one level in this thread
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. 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. 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.
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.