Unusual killer heuristic behavior
Larry Craighead
suggested by several other programmers here. Some results surprised
me...
At each depth I am currently storing 1 killer. This may make a
difference, and I will soon test the results for 2. Killers are
prioritized below hash table moves and above any results achieved
through the history heuristic or by capture (MVV) ordering.
I first made the program store a killer whenever it reached the end of
the search and found the best move without achieving an a-b cutoff.
This actually increased the number of nodes searched. However, when I
added killers for a-b cutoffs as well, which I forgot the first time
around, my node count dropped about 5%, as I had expected.
This result intrigued me and suggested that maybe killers should
_never_ be stored except in the case of an a-b cutoff.
Matt Craighead
Thomas Kerrigan
Read David Levy's "How Computers Play Chess" page 172 for an example.
Cheers,
Tom
------------------------------------------------------------------------------
"You can bring any calculator you like to the midterm, as long as it
doesn't dim the lights when you turn it on." -Hepler, Systems Design 182
Thomas C. Kerrigan
'kerr...@alpha.pr1.k12.co.us'
SheppardCo
> difference, and I will soon test the results for 2.
Most implementations I have read about use two killers. In my
own tests, using 2 killers did out-perform using just 1. I presume
that most implementations use 2 killers because they ran the same
sort of tests that I did. (Either that, or they are blindly following
the orthodoxy. :-))
> Killers are
> prioritized below hash table moves and above any results achieved
> through the history heuristic or by capture (MVV) ordering.
Since Chess 4.5 (read Chess Skill In Man And Machine, Frey (editor)),
it has often been recommended that killers go after captures. Basically,
a killer is a non-capture that is likely to be a refutation.
> This result intrigued me and suggested that maybe killers should
> _never_ be stored except in the case of an a-b cutoff.
Of course! That is the whole point.
Your might wish to try two variations of killers:
a) "Level" killers are killers from sibling nodes.
b) "Move" killers are killers of the opponent's previous move.
Robert Hyatt
SheppardCo <shepp...@aol.com> wrote:
--->> This may make a
--->> difference, and I will soon test the results for 2.
--->
--->Most implementations I have read about use two killers. In my
--->own tests, using 2 killers did out-perform using just 1. I presume
--->that most implementations use 2 killers because they ran the same
--->sort of tests that I did. (Either that, or they are blindly following
--->the orthodoxy. :-))
--->
--->> Killers are
--->> prioritized below hash table moves and above any results achieved
--->> through the history heuristic or by capture (MVV) ordering.
--->
--->Since Chess 4.5 (read Chess Skill In Man And Machine, Frey (editor)),
--->it has often been recommended that killers go after captures. Basically,
--->a killer is a non-capture that is likely to be a refutation.
--->
--->> This result intrigued me and suggested that maybe killers should
--->> _never_ be stored except in the case of an a-b cutoff.
--->
--->Of course! That is the whole point.
I'm not sure about this. The whole point for killer moves are they are
moves that have been good in the past, and therefore might be good in
the future. This includes moves that caused cutoffs as well as moves
that were backed up normally. This is particularly effective, if you do
as we did in cray blitz, which is to try the two killers for current ply,
followed by killers at all other plies that are the same side to move.
I don't do this last part in crafty, but you can run this test by modifying
the "history.c" file which handles both history and killer moves. History
_refutation() stores killers for refutations (cutoffs) while history_best()
stores backed up moves (not refutations, such as the moves along the real PV).
I think you'll find that storing *both* is better.
--->
--->Your might wish to try two variations of killers:
--->
---> a) "Level" killers are killers from sibling nodes.
Sounds like the above idea of trying killers from plies other than the
current one?
--->
---> b) "Move" killers are killers of the opponent's previous move.
These are called refutation moves, and are a variation of the history
heuristic where instead of storing a count, you store a move instead.
I tried this a while back with poor results (tree actually got slightly
larger.)
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Peter Gillgasch
|> > This may make a
|> > difference, and I will soon test the results for 2.
|>
The reason why 2 killers are better than only one is fairly simple: if
you are using only one and the move currently stored in this slot refutes
a lot of moves but in an isolated case another non capture refutes a move
then this "good" killer is lost and replaced by one that has not been proved
to be of the same efficiency in achieving cutoffs.
This explanation is so simple that I decided to follow the common belief
without trying a lot of alternatives (^8. Another interesting question
wether you should try killers of different levels after both killers of
this level failed. From my experiments I conclude that it is useful if
you have no reasonable move ordering after the killers you should do
it, if you have the history heuristic it just adds a lot of complexity
and wasted cpu cycles to the program with only very little gain (if at all).
I would not draw the conclusion that more than 2 killer slots are a good
idea because they add more complexity to update the slots and are rarely
useful.
<snip>
|> > This result intrigued me and suggested that maybe killers should
|> > _never_ be stored except in the case of an a-b cutoff.
|>
|> Of course! That is the whole point.
How about skipping the killer store operation if the search failed
low and store it in all other cases - I don't see any reason why a
move that was best and has a "real" value shouldn't be useful in
other variations?
-- Peter
p.s.: my site has some serious net problems, if you have send
me email lately and I didn't respond then this indicates
that I have not received it yet...
------------------------------------------------------------
Peter W. Gillgasch
Klosterweg 28/I-113 email gil...@ira.uka.de
76131 Karlsruhe/Germany Phone ++49/(0)721/6904255
SheppardCo
> low and store it in all other cases - I don't see any reason why a
> move that was best and has a "real" value shouldn't be useful in
> other variations?
In my programs I very rarely have a "real" value because when
you use a zero-width window the search always "fails" somehow.
--->> This result intrigued me and suggested that maybe killers should
--->> _never_ be stored except in the case of an a-b cutoff.
--->
--->Of course! That is the whole point.
>
> I'm not sure about this. The whole point for killer moves are they are
> moves that have been good in the past, and therefore might be good in
> the future. This includes moves that caused cutoffs as well as moves
> that were backed up normally. This is particularly effective, if you do
> as we did in cray blitz, which is to try the two killers for current
ply,
> followed by killers at all other plies that are the same side to move.
My experience suggests that the history heuristic is the appropriate
means of providing "generally good" moves to the tree search. My
implementation technique for the history heuristic is very different
from killer moves, so I found that it was best to just store refutations.
My history implementation was to keep a heuristic score for every
move, which was added to the SEE score for move-ordering
purposes. This implementation makes the history heuristic integral
to the move generator, and therefore is unlike the killer heuristic,
which interjects moves out of their normal order in the search.
My suggestion that non-refutation moves should not be used as killers
is oriented towards those programmers who might be (inadvertently or
through misunderstanding) including moves that were produced at
cut-off nodes of the tree. (See Peter's comment, above: "How about
skipping the killer store operation if the search failed low and store
it in all other cases") Moves in fail-low positions have unknown value,
since they all return scores <= alpha, and alpha-beta does not
discriminate between such moves. (That is: if score of move1 is X
and score of move2 is Y and Y > X, this provides no evidence as
to the relative merits of move1 and move2 when Y <= alpha. Many
programmers are surprised to hear this.)
Warm Regards
Brian Sheppard
Robert Hyatt
---SheppardCo <shepp...@aol.com> wrote:
--->> How about skipping the killer store operation if the search failed
--->> low and store it in all other cases - I don't see any reason why a
--->> move that was best and has a "real" value shouldn't be useful in
--->> other variations?
--->
--->In my programs I very rarely have a "real" value because when
--->you use a zero-width window the search always "fails" somehow.
good point, one that I have't checked out, however, if all moves fail
low, you are basically going to return alpha, yet there is no move to
remember as a killer since there's no PV that has been backed up to this
node because each move was refuted at the next ply. (sorry for that incredibly
long sentence, sounds like a F. Lee Bailey statement...)
Intuition says that backed up scores and their respective moves are still
good killers, because along the PV, real scores are returned from all the
left-most branches, as alpha/beta requires. Storing these "good" PV nodes
will result in their being used in other branches, and since they are good
here, they might be good there too. Due to lack of computational cost,
it seems worthwhile to save 'em.
--->
--->--->> This result intrigued me and suggested that maybe killers should
--->--->> _never_ be stored except in the case of an a-b cutoff.
--->--->
--->--->Of course! That is the whole point.
--->>
--->> I'm not sure about this. The whole point for killer moves are they are
--->> moves that have been good in the past, and therefore might be good in
--->> the future. This includes moves that caused cutoffs as well as moves
--->> that were backed up normally. This is particularly effective, if you do
--->> as we did in cray blitz, which is to try the two killers for current
--->ply,
--->> followed by killers at all other plies that are the same side to move.
--->
--->My experience suggests that the history heuristic is the appropriate
--->means of providing "generally good" moves to the tree search. My
--->implementation technique for the history heuristic is very different
--->from killer moves, so I found that it was best to just store refutations.
--->
--->My history implementation was to keep a heuristic score for every
--->move, which was added to the SEE score for move-ordering
--->purposes. This implementation makes the history heuristic integral
--->to the move generator, and therefore is unlike the killer heuristic,
--->which interjects moves out of their normal order in the search.
--->
--->My suggestion that non-refutation moves should not be used as killers
--->is oriented towards those programmers who might be (inadvertently or
--->through misunderstanding) including moves that were produced at
--->cut-off nodes of the tree. (See Peter's comment, above: "How about
--->skipping the killer store operation if the search failed low and store
--->it in all other cases") Moves in fail-low positions have unknown value,
--->since they all return scores <= alpha, and alpha-beta does not
--->discriminate between such moves. (That is: if score of move1 is X
--->and score of move2 is Y and Y > X, this provides no evidence as
--->to the relative merits of move1 and move2 when Y <= alpha. Many
--->programmers are surprised to hear this.)
Right. without caution, you can store "garbage". You can bet this has
happened at some point in Crafty's evolution. :)
SheppardCo
still
> good killers, because along the PV, real scores are returned from all
the
> left-most branches, as alpha/beta requires.
Actually, my programs haven't used "alpha-beta" per se. They used a
variant called Negascout, which you are undoubtedly familiar with.
Negascout differs from a conventional alpha-beta in that the value of
the best move is not actually known. Negascout constructs a valid
proof that the selected move is better than the others, but does not
produce a value for that move.
Therefore, even in the left-hand branch there are apt to be failures
at virtually all nodes.
Warm Regards
Brian
(Note: it occurs to me that even a conventional alpha-beta has only
N nodes having "real" scores, where N is the depth of the PV. The
effect of saving such moves as killers must be minimal.)
Joe Stella
iken...@cix.compulink.co.uk ("Ian Kennedy") writes:
>I don't currently use a killer heuristic although I did in the past. All
>I do is sort on capture value. Does anyone have any *hard, statistical*
>evidence (as opposed to empirical or gut feeling) as to how often a
>killer heuristic is a capture, or even the best capture move?
Well I guess the first thing I can say is that you are not supposed to
put captures in the killer list. Killers are supposed to be *non* captures.
If I remember correctly, the killer h. can speed up a search by about
10%, and the history h. is about 15% to 20%. I remember these numbers from
papers in the ICCA journal; I *think* I am remembering correctly... :-)
>Also, in light of this info if available, do people who put the killer
>heuristic first before general captures exclude or include captures in
>picking the killer?
Captures and the hash table move are generally tried before killer moves.
Some people separate *winning* captures from *losing* captures (with the
help of an exchange resolver); in that case, losing captures are ordered last.
Joe S.
Robert Hyatt
Ian Kennedy <iken...@cix.compulink.co.uk> wrote:
--->I don't currently use a killer heuristic although I did in the past. All
--->I do is sort on capture value. Does anyone have any *hard, statistical*
--->evidence (as opposed to empirical or gut feeling) as to how often a
--->killer heuristic is a capture, or even the best capture move?
--->
--->Also, in light of this info if available, do people who put the killer
--->heuristic first before general captures exclude or include captures in
--->picking the killer?
--->
--->Thanks
First, I don't allow captures into the killer list. Testing a long while
back convinced me it was a bad idea, since a capture is a local refutation
most of the time (specific capture refutes specific blunder...)
I've since had second thoughts, and want to re-visit this question, but
not allow a capture that captures piece moved at previous ply to get into
killer list, but to allow other captures. The idea is that a killer can
be tried before generating or sorting regular move list, so how about
trying killer captures before generating or sorting capture move list.
No data as yet, but killers definitely speeded crafty up, both from smaller
trees and fewer move generations. I'll try to collect some data when I test
the killer capture idea.
Peter Gillgasch
|> In article <DF7vA...@cix.compulink.co.uk>,
|> Ian Kennedy <iken...@cix.compulink.co.uk> wrote:
|> --->I don't currently use a killer heuristic although I did in the past. All
|> --->I do is sort on capture value. Does anyone have any *hard, statistical*
|> --->evidence (as opposed to empirical or gut feeling) as to how often a
|> --->killer heuristic is a capture, or even the best capture move?
|> --->
|> --->Also, in light of this info if available, do people who put the killer
|> --->heuristic first before general captures exclude or include captures in
|> --->picking the killer?
|> --->
|> --->Thanks
|>
|> First, I don't allow captures into the killer list. Testing a long while
|> back convinced me it was a bad idea, since a capture is a local refutation
|> most of the time (specific capture refutes specific blunder...)
|>
|> I've since had second thoughts, and want to re-visit this question, but
|> not allow a capture that captures piece moved at previous ply to get into
|> killer list, but to allow other captures. The idea is that a killer can
|> be tried before generating or sorting regular move list, so how about
|> trying killer captures before generating or sorting capture move list.
|>
|> No data as yet, but killers definitely speeded crafty up, both from smaller
|> trees and fewer move generations. I'll try to collect some data when I test
|> the killer capture idea.
Now while I don't really want to second guess Ian here I
*think* that he was not talking about capturing moves in
the killer list - the moves that are (or to be exact have
been) killers and now happen (by chance, accident or whatever)
to be a *capture* are quite interesting, aren't they? If a
move was "good enough" when capturing nil material then I'd
say that it is a good refutation candidate when it even disturbes
the material balance right away!
BTW a more or less long time ago I used SEE ordering as Bob
did/does/will and played with the following ordering:
"good" captures, "equal" captures, non capturing killers, "bad
captures", history, rest of the moves more or less unsorted.
The reason for putting bad captures in front of the rest of
the moves was my firm disbelief in static analysis. Plus I did
not see any gain when moving them to the end of the list except
the cost that I have to generate non captures now...
I remember that I then changed it to
"good" captures, "equal" captures, *former killers that happen
to capture something now*, killers, "bad captures", history,
rest of the moves.
Note that since all "good" and "equal" captures are exhausted the
"killers" that happen to be a capture now are so called "bad"
captures. If you try this and your tree size shrinks, well then
this heuristic obviously fixes oversights of your ripoff() function.
I recall that it was a slight win in performance, unfortunately
I cannot conduct any experiments & post data - I dumped SEE a
long time ago and the original sources are in Pascal. Ancient
Egypt language.
Maybe this idea is helpful for someone.
-- Peter