Author: Robert Hyatt
Date: 08:38:21 11/26/02
Go up one level in this thread
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. 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... >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. > >Searching for fixed depth may give wrong results because programs may use >different pruning when you change the order of moves and find the same move at >different depth. If you don't search to a fixed depth, you have absolutely no way to compare two different algorithms... > >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.