Author: Robert Hyatt
Date: 21:57:31 12/23/99
Go up one level in this thread
On December 23, 1999 at 22:53:49, Michael Neish wrote: > >Hi, > >I'd like to ask a question about move ordering. At the >moment my program is searching about ten moves per ply >(well, on average each successive ply involves about >ten times more nodes than the previous one), which I >think is woefully inefficient compared to what others >have said. I think simple alpha-beta should give a >value of about six for good move ordering. So, my >program needs to search about a million nodes to reach >ply six compared to under 100,000 for HIARCS 7.0 >(which indeed comes to about six moves per ply). > >At the moment my only attempt to order the moves is >the fairly standard history table which I've >implemented for White and Black separately, >which increments a counter every time a move causes >a cut-off, and erases the whole table at the start of >the next search. I've tried different counting >systems, e.g., one that depends on depth, or a >multiple of depth, or an inverse multiple of depth, >but all have either a negligible or a negative effect. > >Now, I can think of the following four standard >enhancements to a search function (there are >probably some more): > >null move >killer move >extensions >hash tables > I don't see 'capture moves'. They are _critical_ and have to be done before any other move (except hash table move). >My question is, if I implemented some or all of >the above, would it 1) automatically take care of >the move ordering, or 2) will I have to work on move >ordering separately? killers and history moves are similar. history is a more global concept, while killers are more local to specific parts of the tree. I use both as with killers you can try them before generating all the non-capture moves. > >If 1), how would you order the above in decreasing >order of effectiveness? I do the following: 1. hash table move 2. captures with expected material gain >= 0 (using the classic SEE approach to determine expected material gain). moves are sorted by expected gain. 3. killer moves 4. 4 history moves 5. remainder of move list. > >If 2), then what sort of magic does one need to >weave in order to go from ten moves searched per ply >down to six? the above will probably do the trick. > >I see that Crafty eliminates captures that lose >material. I don't understand how this is done since >to know whether a capture loses material I suppose >one would have to search it, and a capture that >loses material at the present ply might not do so >a couple of ply down the road. Could someone please >explain? It uses a SEE algorithm (Static Exchange Evaluator, see swap.c in the crafty source for an idea of how it works). It only considers captures on a single square, but gives a fairly accurate idea of whether such a capture sequence is good or bad. > >Would it help to carry out a shallow search first, >say depth 4 and order the moves in terms of the >static evaluation at the end of the tree? If so, >then I don't know how one could keep the ordering >up to date as one searches deeper. No. Hash moves do this for you automatically, as does history moves from iteration to iteration. > >Thanks for your time. I hope to get some discussion >going on this so that others will benefit from these >questions. > >A very Merry Christmas to everyone here. > >Cheers, > >Mike.
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.