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