Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: not using nullmove? [generalized null move]

Author: Uri Blass

Date: 08:24:14 02/14/04

Go up one level in this thread


On February 14, 2004 at 10:41:15, Robert Hyatt wrote:

>On February 14, 2004 at 01:05:46, Dann Corbit wrote:
>
>>I think the interesting thing about null move is that it is easy to figure out
>>if a move is really bad -- which is the main reason why it causes a benefit.  A
>>tempo advantage is easily calculated by just switching sides.
>>
>>But the idea can be generalized nicely.
>>
>>Suppose that you have a seven ply search performed and it is time to do an 8 ply
>>search.  Suppose (further) that from the root node only you never analyze the
>>root itself but instead analyze all of the child nodes of the root and save the
>>values.
>>
>>Now, you have some sort of estimate for the "goodness" of each move. Things
>>might get reversed on the next ply, but it isn't terribly likely.  After all, we
>>look at crappy moves and search them less deeply with the null move heuristic.
>>
>>Now, suppose that we have 10 moves available:
>>
>>move 0 has an evaluation of +100 centipawns
>>move 1 has an evaluation of +80 centipawns
>>move 2 has an evaluation of +77 centipawns
>>move 3 has an evaluation of +60 centipawns
>>move 4 has an evaluation of +53 centipawns
>>move 5 has an evaluation of +19 centipawns
>>move 6 has an evaluation of +5 centipawns
>>move 7 has an evaluation of -10 centipawns
>>move 8 has an evaluation of -110 centipawns
>>move 9 has an evaluation of -910 centipawns
>>
>>Will we (knowing this) want to search them all the same?
>>
>>Why not use a logarithmic scale based on the difference between the best
>>possible move and the move under consideration?
>>
>>Another advantage:
>>Zugzwang sorts itself out.
>>
>>We can also add refinements like increasing the shear with mobility increase
>>(greater reductions if I have 90 choices than if I have 12).
>>
>>Using estimates from a database also works nicely.  Unfortunately, hash table
>>estimates have not worked out well for me (for attempts using other than the
>>root).
>
>There is one other major flaw.  You just made the search _many_
> times slower.
>
>:)
>
>The math:
>
>Doing an 8 ply search.  Assume a branching factor of 38.
>
>the 8 ply search will search
>
>N1 = 38^4 + 38^4 + 1 leaf nodes.
>
>the 38 x 7 ply search will search
>
>N2 = 38 * (38^4 + 38^3 + 1) nodes
>
>N1 = 4,170,273
>
>N2 = 81,320,342
>
>N2 / N1 = 19.5 times slower.  Not a good thing.

This math is correct only when you calculate exact score to the same depth
but I assume that Dann means to calculate exact score to reduced depth and if
the depth is reduced enough you get information that can be used later for
search decision when the price even without using it for search decisions may be
only being 10% slower.

Uri



This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.