Author: Brian McKinley
Date: 15:39:02 09/24/98
Go up one level in this thread
On September 24, 1998 at 18:15:34, Bruce Moreland wrote: > >On September 24, 1998 at 16:11:54, John Coffey wrote: > >>It seems to me that there would come a point where attempts to order >>the moves at every branch of the tree would slow down the tree search. >>I could see doing this in the lower levels of the tree, but wouldn't >>there be a point of diminished returns? I.e. if you were searching >>N ply deep, maybe you would want to stop ordering at maybe N-3? > >Try it and see. But I predict that you will want to order all the way out, >since you will be messing around out near the frontier a huge percentage of the >time. > >Another idea is to stop ordering if the first few moves you try don't produce a >cutoff. If you don't cut off, you will probably have to search all of the moves >anyway, either that or you've proven that you have no idea how to order the >moves in this position, so why bother? Try this and see, too, if you would >like. > >>This brings up another issue: Crafty (and for all I know, other programs) >>will generate the entire move list at each branch before searching deeper. >>It might do some ordering too. But it might not be necessary to look at >>all these moves, so the time spent generating some of the moves could be wasted. > >You are suggesting an incremental move generator. Try it and see. > >>My plan, right or wrong, for my Mars engine was to have different search >>strategies at different levels of the tree. Probably most programs do this >>already. > >Mine doesn't, but this might be of value, and I've thought about doing it. I >will try it and see ;-) > >bruce I tried an incremental move generator when I first started. The nps were significantly faster, but I ended up searching more nodes. I eventually scrapped it in my losers chess program because move ordering was more important with so many branches extending 15 to 30 ply, I may try it again now that I am working on normal chess and the extensions are not as deep. Brian
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.