Author: Robert Hyatt
Date: 15:00:40 11/26/02
Go up one level in this thread
On November 26, 2002 at 14:22:48, Uri Blass wrote: >On November 26, 2002 at 13:50:01, Robert Hyatt wrote: > >>On November 26, 2002 at 12:08:37, Uri Blass wrote: >> >>>On November 26, 2002 at 11:38:21, Robert Hyatt wrote: >>> >>>>On November 26, 2002 at 11:00:28, Uri Blass wrote: >>>> >>>>>On November 26, 2002 at 10:54:07, Robert Hyatt wrote: >>>>> >>>>>>On November 26, 2002 at 08:24:43, Uri Blass wrote: >>>>>> >>>>>>>Here is my idea for testing the quality of order of moves. >>>>>>> >>>>>>>1)take test positions and calculate the number of nodes that you need to find >>>>>>>the solution. >>>>>>> >>>>>>>2)build a special function sort(d) that get as parameter the remaining depth and >>>>>>>return the best move based on searching to depth d. >>>>>>>sort(d) should change no global varaible that is used by the original >>>>>>>program(for example it should not change the number of nodes inspite of the fact >>>>>>>that it is doing search and if the original search rules are based on the number >>>>>>>of nodes it should use another varaible). >>>>>>> >>>>>>> >>>>>>>3)Do the same search except deciding that everytime that the remaining depth is >>>>>>>d you decide about the first move to search based on sort(d) >>>>>>> >>>>>>> >>>>>>>It may be interesting to know what is the efficiency of programs based on this >>>>>>>test. >>>>>>>positions that needs 500,000-1,000,000 nodes to solve with the search rules of >>>>>>>today may need less nodes with best first but how many nodes is an open >>>>>>>question. >>>>>>> >>>>>>>Of course best first is going to be slower but it may give us information about >>>>>>>the advantage that we can get from better order of moves. >>>>>>> >>>>>>>I could do the same exercise about the same depth but I suspect that positions >>>>>>>may be solved not at the same depth because the pruning decisions may be >>>>>>>function of the move that you search first. >>>>>>> >>>>>>>Uri >>>>>> >>>>>>A variation on this has already been done. I'm not sure whether it was >>>>>>Berliner, or Campbell, but I'm fairly sure it was someone at CMU. The >>>>>>basic finding was that current programs are searching within a factor of >>>>>>two of the "minimal" tree for most normal positions, which was surprising. >>>>>> >>>>>>The key point is that you don't always have to search the "best" move first, >>>>>>just a move good enough to cause a cutoff... >>>>> >>>>>The best move may produce smaller tree in most cases. >>>> >>>> >>>>Not at all. IN fact, for every case where the "best" move produces a smaller >>>>tree, there is a case where the "best" move produces a _larger_ tree. Size of >>>>the tree is not related only to the absolute score returned below a particular >>>>move. It is even more tied in to the kind of position that arises, since a >>>>check can drive the search deeper. >>> >>>I said in most cases and not in all cases. >>>I can explain reasons that the best move can give a smaller tree. >>> >>>I have a pruning based on evaluation and other factors. >>>The best move may lead to search to reduced depth because of this pruning. >>> >>>Even programs that only use null move pruning may have search to reduce depth >>>based on this reason because after the best move it is more common to have a >>>cutoff because of no threat for the opponent. >>> >>>> >>>>The alpha/beta algorithm is really not about searching the move that produces >>>>the smallest tree first, it is about searching a move that will cause a cutoff >>>>first, regardless of what move that is... We have broken this a bit by adding >>>>dynamic search extensions. But it is going to be _impossible_ to predict which >>>>move will produce the smallest tree, without actually searching all the moves >>>>to see. But finding a move that will cause a cutoff is within reason... >>> >>>My theory is that if you choose 2 moves that cause a cutoff then in most cases >>>the better move cause a smaller tree. >> >>You have to define "better". If you mean that when you search each of those >>moves to >>the same depth, the "better" move produces the best "score" then I disagree. > >I mean the better move is the move that produce the best score. >I do not say that the best move is going to produce the smallest tree but only >that I expect the average size of the tree to be smaller than the size of the >tree of today by the first move that generates cut off. > >An extreme example is when the best move generate checkmate. > A more common example is where the best move leads to a non-forced mate in 20 that takes forever to refute, while another move leads to "only" winning a pawn, which is enough to cause a cutoff. The "best move" might eventually win 2 pawns, and cause the cutoff, but only after a whole lot more work. This is based on serendipity however, and hoping for the best doesn't mean you always get it. The average has to be worse... >Uri > > I >>think the >>score is unrelated to complexity and what happens below that node. That is one >>reason >>for the ETC algorithm. It does _exactly_ what you are suggesting in a limited >>case... >> >> >>>> >>>> >>>> >>>> >>>>>There is a difference between different cutoffs. >>>>> >>>>>I think that the minimal tree is also dependent on the depth of the search and >>>>>at bigger depth the factor is bigger. >>>> >>>>I'm not sure what you mean by "the factor is bigger at bigger depths." I don't >>>>see anything that suggests this because the hash table moves will provide great >>>>accuracy near the root of the tree, and as the depth increases, the depth of >>>>this accuracy increases as well. The poor ordering is way out into the tree, >>>>in general. >>> >>>In general you are not going to get a factor of 2 in the size of the tree if you >>>search to depth 1 or depth 2 so it is clear that the factor is going to be >>>bigger when the size of the tree is bigger. >> >>I don't think it will matter. As the tree gets larger you have more >>opportunities to get >>the best or not-best move first. But the percentage should stay the same and, >>in fact, >>the deeper you go, the more accurate the ordering is near the root... > >I did not say that the order of moves is worse near the root. > >I only say that at big depth you can earn more from better order of moves so >upper bound of being 2 times faster is not correct because it can be 2 times >faster at depth 9 and 2.2 times faster at depth 10. > >Uri
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.