Author: Uri Blass
Date: 11:22:48 11/26/02
Go up one level in this thread
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. 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.