Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move ordering?

Author: Ulrich Tuerke

Date: 02:41:36 04/30/00

Go up one level in this thread


On April 28, 2000 at 19:55:01, Dann Corbit wrote:

>On April 28, 2000 at 19:15:59, Josť Carlos wrote:
>
>>On April 28, 2000 at 17:22:24, Dann Corbit wrote:
>>
>>>On April 28, 2000 at 17:01:20, Severi Salminen wrote:
>>>
>>>>Hi!
>>>>
>>>>My program finally has AB search, searches some 70 KN/S and it almost knows
>>>>every rule (no underpromotion, 50 move rule and position repetition :-). Now I
>>>>would like to add some move ordering. I have two simple ideas: at root I sort
>>>>the moves by scores from previous iteration and at other nodes maybe by
>>>>captures, checks and then others. Does this sound reasonable? Where could I find
>>>>more information on move ordering methods or what do you use?
>>>
>>>Sort them by time it takes to emerge from alpha-beta.
>>>The ones that take the longest get checked first.  Resort after each new level.
>>
>>  I don't get the idea. First, when using PVS, PV move will always take more
>>time than the rest (if not fail high). But, omitting PVS, I don't still
>>understand why a move that takes longer should be searched first.
>>
>>  What I do right now is:
>>  1.- in the first iteration, I sort the root moves exactly the same as the rest
>>of the moves (captures first, etc.).
>>  2.- after every fh, I assess that move a value greater that the others, so it
>>will be searched the first in the next iteration.
>>  3.- as new fh occur, the moves remain ordered as last_failed_high_first. And
>>the moves that never failed high, remain ordered by normal ordering heuristics.
>>
>>  This method seems to work fine for my program.
>
>The reason the slowest positions might get searched first is because they are
>promising.  It took a long, hard look to decide that the other one was better.
>
>If we returned instantly, then it's not worth looking at.

I agree that this is certainly a reasonably working move order heuristics.
Often, the new best move had been searched long in the previous iteration.

However, there are 2 points which I consider as serious drawbacks:
1. you will have the heavily extended root moves (checks, sacs and so on) coming
early because these will be nodes-consuming; i do not think that it is justified
to search these first.
2. you do not have an estimate for the score of the non-pv root moves. How to do
an easy move algo in this case ?

So, I do something different (but probably not better).

Uli



This page took 0.02 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.