Author: Robert Hyatt
Date: 07:41:15 02/14/04
Go up one level in this thread
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.
This page took 0.09 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.