Author: Robert Hyatt
Date: 10:50:01 11/26/02
Go up one level in this thread
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 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 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 That is fine until you try to compare that number with different programs. Or until you try a parallel search...
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.