Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move Ordering at the Root

Author: Dan Homan

Date: 04:54:41 09/16/99

Go up one level in this thread


On September 15, 1999 at 22:56:34, Robert Hyatt wrote:

>On September 15, 1999 at 17:12:16, Dan Homan wrote:
>
>>I was reading the crafty source again the other day and noticed that
>>Bob has a special function to improve the move ordering at the root
>>of the search.
>>
>>I really didn't feel like writing such a function last night, but I
>>thought instead to use the values returned by the search itself to
>>improve the move ordering at the root.  I know that I only get an
>>accurate value for the best move, but I thought that my fail-soft
>>search might return useful numbers for the other moves as well....
>>
>>Implementing this was pretty quick and easy: there were a couple
>>of pit falls, but the total changes were about 5 lines of code.
>>Previously I simply used the same move ordering at the root that I
>>use at all other nodes.
>>
>>The improvement was amazing!  I got a full ply in many positions and
>>about a half-ply in many more.   It improved my solution times on WAC
>>noticably and seems even better in quiet positions.
>>
>>I know that my solution was a quick kludge, so I am wondering what
>>other people do for move ordering at the root of the search.
>>
>> - Dan
>
>
>Are you sure you didn't introduce a bug?  Root ordering is only important
>in positions where you change your mind a lot.  If you lock on to one move
>and stick with it, it won't do anything to improve the ordering...

I noticed (before the change) that about half of my search time (in some
positions quite a bit more) was spent on moves other than the hash (best)
move.  I thought this was high and was looking at crafty for hints.

That's when I noticed the special ordering at the root of the search, so I
tried this quick solution of using the fail-soft values of the search to
sort the list at the root.  I don't think I introduced a bug, but I may
well have covered-up a bug - I am going to look into this further, both
to test how large the improvement really is and to see if I had any bugs
that were limiting my performance before.

>
>a ply sounds really odd as a gain...

I thought about this and realized that it is possible that the speed up was
'only' 10-20%, but because I count a ply as searched when it is completed and
a half-ply as searched when the first move is completed, that I noticed many
positions that seemed to get an extra half-ply or ply.

 - Dan



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.