Computer Chess Club Archives


Search

Terms

Messages

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

Author: J. Wesley Cleveland

Date: 12:22:36 02/15/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 is the penalty you pay if you want the ply=2 scores.  Alpha/beta only gives
>the best move / ply=1 score...  Additional information has huge additional cost.

Say you look at it this way instead:

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

This information you get for free from alpha-beta. Admittedly, moves 1-9 could
have (much) worse real scores, but this only means that you search some lines
you could have cut off, but alpha-beta would search these lines anyway.



This page took 0.16 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.