Computer Chess Club Archives




Subject: Dynamic move ordering for capture/promotions?

Author: Scott Gasch

Date: 17:52:47 04/02/01

Hi all,

In an effort to tune my chess engine I've been paying close attention to first
move beta cut percentage rates (which, in my engine, are consistently slightly
lower than in other engines I test).  I've added a debug mode where my code
actually dumps the node position and moves in the order it considered them
(along with their score) up to and including the move that caused a beta cutoff
when that beta cutoff move was not the first move considered at node.

Wading through this data I've seen a pattern that I wanted to ask the list
about.  Presently I search moves in the order that many others do: winning
captures/promotions (by SEE), even captures, killer moves (which are explicitly
non capturing / promoting), other non-captures ordered by history heuristic, and
losing captures.  Now, imagine a position where N takes (defended)p exposes the
enemy q or k to discovered attack.  Nxp is "losing" according to the SEE so it
doesn't get considered until way down in the move list.  However it's actually a
really good move at this point and causes a beta cut.

The problem is I do not use dynamic move ordering at all with captures /
promotions.  Only non-captures use history and killer heuristic.  So with our
hypothetical Nxp position we search a ton of recursive lines before seeing this
one... which is ok because it's the exception not the rule.  But later on in the
search at the same tree depth we'll come to a position that is almost exactly
the same.  Again, Nxp is a great response... and again it's not searched until
dead last because the SEE says its "losing".

So the solution, I think, is to allow captures into the killer list.  Maybe only
if they are losing captures(?).  Unfortunately because of the way my generator
works this is a pain in the butt to do.  Does anyone else have any thoughts on
this matter?  Has anyone else experimented with this stuff in reasonable detail?

As always, thanks to all.  I'm grateful for any advice.

This page took 0.15 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.