Author: Dan Homan
Date: 13:11:55 06/25/98
Go up one level in this thread
On June 25, 1998 at 15:01:54, Don Dailey wrote:
>On June 25, 1998 at 09:43:45, Dan Homan wrote:
>
>>I'm not sure the right place to jump into this thread,
>>but here will work...
>>
>>Is the speed-up from incremental move generation the
>>only reason to use killers over the history heuristic?
>>
>>I've runs some quick 'n dirty tests on my program (which
>>does not use incremental move generation... rather I
>>generate all the moves at once and score them for sorting
>>as I generate them), and the history heuristic by
>>itself seems superior (in essentially all the positions I
>>tested) to killers alone or killer+history.
>>
>>Perhaps my testing was flawed (it was very quick) or my
>>implementation, but I was wondering if anyone else had
>>a similar experience.
>>
>>For programs that do incremental move generation (like
>>crafty), killers are surely a win because they don't
>>need to do a full move generation if they get a cutoff.
>>But what about programs that don't use this approach?
>>
>> - Dan
>
>My experience with history heuristic is a wash. My older
>programs used to benefit a lot, but maybe too many move
>ordering heuristics get in the way? I dutifully implement
>this with each new program just looking for any small
>advantage I can get and then always have to disable it.
>
>Are you saying history heuristic worked better when you
>did not use the killers at all?
Yes. My move scoring for ordering purposes is very simple
though. With complicated heuristics, I imagine it would be
quite difficult to decide how to use the history score.
Basically, I have no special heuristics beyond
hash move = 10,000,000 + history;
captures = 5,000,000 + 10*captured_piece - capturing_piece + history;
promotions = 5,000,900 + history;
rest = history;
I could eliminate the history part from the first 3 cases as it
doesn't really do anything except break some ties between equal
or nearly equal captures. In some positions breaking the ties
helps ~ 1%, in others it hurts ~ 1%, in most it makes no
difference.
Also I found that instead of updating the history score for a
move after it gives me a cutoff, a slight improvement was to
increase the history score each time I updated the PV.
So something like...
score = -search(-beta,-alpha,depth-1);
if(score > alpha) {
alpha = score;
pv_update(move,ply);
history[move.from][move.to] += depth;
}
- Dan
>
>- Don
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.