Author: Michael Neish
Date: 19:53:49 12/23/99
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 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? If 1), how would you order the above in decreasing order of effectiveness? 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? 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? 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. 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.