Author: Robert Hyatt
Date: 11:41:39 08/03/99
Go up one level in this thread
On August 03, 1999 at 12:33:42, David Eppstein wrote: >On August 03, 1999 at 10:24:34, Robert Hyatt wrote: >>I can only speak for Crafty, but it spends more time on the move it is going >>to play than it does on all the other moves combined... > >Ok, so here is another stupid idea to try to speed up the obvious moves. > >The reason you spend so much more search time on the part of the tree coming >from the correct move is that you have to exactly resolve its search value, >while alpha-beta lets you quickly get inexact cutoffs on the other moves. BUT, >to play a good move, you don't really need to exactly resolve its value, you >just need to know that it's better than the other moves. > >So, suppose you have a move that looks obvious, in that a shallow search gives >it an evaluation of x while all other moves have an evaluation of y, y much >smaller than x. Then if you see this sitution, do some deeper searches with a >zero-width window at (x+y)/2. If the "obvious" move always fails high and the >nonobvious ones fail low, then that's the move you should make. If something >else happens, then you need to do a real alpha-beta search. > >Since all searches are zero-window with the window far away from the true >evaluation of the line, they should all be fast, so you should be able to spend >less time on them than you would with full alpha-beta to get to equal depth. > >One drawback of this approach, of course, is that you end up with no idea what >the PV should be, but who cares about that if it plays the right moves? Ken Thompson and I used a search approach similar to this many years ago. The idea is to play the best move, as you say. And if a move fails high (over the best move at the root) there is no need (yet) to resolve the score. Just note that you have a new best move candidate and keep going. If no other moves fail high, you are ok. But if another one does fail high, you have to re-search both to find the best. This last sentence is the problem. Right after the fail high, the hash table is seeded with good moves to re-search that move. If you want for many millions of nodes, you can lose all of that information and the re-search becomes much less efficient. I got rid of it for that reason, plus with null-move R=2, an occasional false fail-high happens and the research fails low letting me know that that fail-hi move is _not_ the one to play, so that I keep the original best instead...
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.