Author: Uri Blass
Date: 09:08:37 11/26/02
Go up one level in this thread
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. > > > > >>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 do not say that the order of moves is worse when the depth is bigger but that the result of the division of the size of the tree is bigger when the depth is bigger. > > > > >> >>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... I think to compare by nodes to solution because my thoery is that it is possible that different order of moves cause the solution to be found at different depth because of the pruning rules. 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.