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.