Author: Robert Hyatt
Date: 22:14:39 05/12/01
Go up one level in this thread
On May 13, 2001 at 00:13:33, Angrim wrote: >On May 12, 2001 at 01:49:19, Robert Hyatt 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, >> >> >>Do you understand how a tree search works in the "depth-first" world of >>alpha/beta and minimax? If you do, then you would realize your question >>is not sensible in that context. >> >> >> >>>but my point was that the "many quintillions of quintillions of >>>qintillions of games" that can result from this position are irrelevant. >> >> >>Not to alpha/beta minimax they are not. If we could assure "perfect" move >>ordering, then we would be able to find the instant mate and simply have to >>prove that no other move here can mate in a shorter distance than 1 which >>is impossible of course. But without perfect move ordering, we might not >>find the check/mate first, and then we do search zillions of games following >>_another_ move first... we will eventually find the mate, but only after we >>search one or more other moves first... >> >> >> >>>The fact that with worst play games thousands of moves long could result >>>from this line is also irrelevant. >> >> >>Again, no they aren't. That is not the way minimax works. >> > >Carefully forgetting about iterative deepening? >I lack the patience and stamina to continue this thread. Both sides of >the case have been clearly stated already, so anyone who cares who is >right can come to their own conclusions. > >Angrim Iterative deepening doesn't work without a hash table. You will _never_ have a hash table big enough to store the entire chess tree. End of story. The only hope is to simply do a depth-first search. If you don't have hashing, then your N ply search will discover the Queen check and mate move eventually. Then the N+1 ply search will have to discover it all over again, possibly after searching other moves first. Ditto for N+2, N+3, etc. And each time, those non-mate searches get harder and harder to do... As far as "who is right" the answer is pretty obvious when it comes to searching trees. I've been doing it _far_ too long... Computers do _not_ search like humans. And the depth-first approach has some interesting shortcomings. You only have to look at the trees for the old Bratko-Kopec test position #1...
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.