Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Move Ordering (Question, Fairly Long)

Author: John Hendrikx

Date: 10:27:45 12/25/99

Go up one level in this thread



>>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).

As it happens, I've started playing around with move-ordering as well,
and giving priority to captures increased the speed by a factor of 3
(I already made sure that the PV was the first move tried).

I also found that trying pawn-moves (not captures) after all other moves
gave me another nice speed up (about 30%).  Currently I have this order:

 1. PV
 2. Captures (ANY captures -- no SEE algorithm involved (yet))
 3. Piece moves
 4. Pawn moves

No killer/history heuristic yet.

I don't know if sorting Pawn Moves last will hold up in later stages of
the game (I only tested the beginning) -- I could give Pawn Moves scores
depending on how far up the board they are though...

I've tried adding null-moves as well, but haven't been very succesful.  I
need some more to go on before I can get it right, but I can't find good
examples or descriptions of them.  So far what I've tried is to try a
null-move before doing any real moves at a certain level of the tree, and
searching the null-move to the same depth as usual; my problem is that I
don't know what to do with the returned score.  From what I gathered one
should create a cut-off when the score is 'not so good' even while doing
two moves in a row.. it didn't work for me though.  It was far slower (1.5
times) with the same results, and only a few dozen null-move cutoffs at
6 plies orso.  When I increased the cut-off point by half a pawn in favor of
more null-move cut-offs all I got was a bunch of very bad moves.

What can one reasonably expect to win if one is allowed 2 moves in a row?
Should null-moves be tried for both black and white?

>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

Is that the same as the Principle Variation?

>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.

John.



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.