Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Dynamic move ordering for capture/promotions?

Author: Tony Werten

Date: 06:51:31 04/03/01

Go up one level in this thread


On April 02, 2001 at 20:52:47, Scott Gasch wrote:

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

SEE is less about trying the good captures first and more about trying the bad
captures later ( or not at all ). Robert Hyatt always says that his win with SEE
comes from this not trying.

If you postpone a bad capture, you might get a cutoff with your killers or
history. If you don't get a cutoff at all, it didn't matter anyway.
You accept the few times a "bad" capture is actually a good one, because most of
the time they're just bad.

Tony

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



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.