Author: Robert Hyatt
Date: 09:33:10 07/13/03
Go up one level in this thread
On July 13, 2003 at 03:53:19, Walter Faxon wrote:
>On July 12, 2003 at 22:28:53, Robert Hyatt wrote:
>
>>On July 12, 2003 at 18:42:51, Rick Bischoff wrote:
>>
>>>Hi all,
>>>
>>>First time poster, long time listener(reader) :-) Anyway, I am busy away
>>>implementing my chess engine and have a question about killer moves-- first some
>>>background:
>>>
>>>My move structure has a "score" field that is used to sort the moves in
>>>descending order after generation. This score is simply 0 for no captures,
>>>PieceValue(Captured) - PieceValue(MyOwnPiece) + PieceValue(QUEEN) +
>>>PieceValue(PROMOTION).
>>>
>>>Ok, so now I have an array somewhere called : int killerMoves[MAX_PLY][64*64]
>>>
>>>and my idea is this--
>>> A) After a "real" move is made, zero out the entire array
>>> B) During move generation, for each move M, if
>>>killerMoves[ply][M.from*64+M.to]>0, M.score = that value
>>> C) During the search...
>>>
>>>... if (val >= beta) { killerMoves[ply][currentMove.from * 64 + currentMove.to]
>>>= M.score + 1; return beta; }
>>>
>>>.... }
>>>.... killerMoves[ply][bestMove.from*64 + bestMove.to] = bestMove.score+1;
>>>.... return alpha;
>>>
>>>Is this the "proper" way to implement killer moves? Would it be better to set
>>>the score of the move to +INF after a cutoff? Is there a better structure I
>>>can use other than an int array?
>>>
>>>Thanks,
>>>Rick
>>
>>
>>Killers are actually easier to implement than that. When you get a fail
>>high, or back up a score > alpha (that means this is _not_ a fail low node,
>>store the best move if it is not a capture. If the best move is a capture,
>>you will search it before killers anyway so there is no reason to dislodge a
>>non-capturing killer with a killer that will have already been searched by
>>the time you get around to trying "killer moves".
>
>
>Dr. Hyatt:
>
>Any advantage to having two killer lists: regular non-capturing killers, and
>capturing killers, to be examined first when looking at captures?
I don't believe so. Captures (as refutations) are very specific. IE you
move your queen to an unsafe square, capturing it is the best move to
refute it. There's no way that capture can be a "killer" since it only
kills a specific stupid queen move.
Something like SEE or MVV/LVA will pick that up first, and quickly, and won't
be fooled into capturing something that is not a good capture in the given
circumstance.
>
>Maybe have some additional logic before that to look at "new" captures
>immediately after PV or TT move (i.e., captures of pieces that were not attacked
>two plies earlier). Or something like that.
>
>Actually, with IID, shouldn't nearly every position not at the frontier already
>have some TT move associated with it? I realize that half the time you must
>search every alternative, and that special effort in ordering moves at these
>nodes doesn't pay off. Or does it?
>
After an IID cycle, yes you should have captures in the TT. But while you
are doing the IID cycle, you obviously don't. There you need something else
to guide the search, and good captures, killers and history heuristic moves
work well there.
>So, provisionally:
> 1) PV (if available)
> 2) TT (if available)
Those should be the same thing. IE if a move is in the PV, it should
be the TT move as well.
> 3) New captures (or promotions)
> 4) Killer captures (or promotions)
I don't particularly see any advantage in (4). (3) should pick up the
ones that are good, first.
> 5) Other captures (or promotions; maybe R and B promotions here)
> 6) Other killers
> 7) Killers from two plies earlier? Vaguely remember stuff about this...
We did that in Cray Blitz. I took it out later, and Harry found that it
was better to put it back in, so we did. In fact, at depthj=7, we first
tried the depth 7 killers, then depth 5, 3, etc.
> 8) Other moves (maybe in some standard order, such as centralizing or towards
>the opponent's king, or advancing pawns to 7th, etc.)
>
>And where does the null move fit in this list?
>
>Dr. Hyatt, what's Crafty's complete order? We need a Crafty algorithm FAQ!
1. hash table (TT) move.
2. non-losing captures (SEE says score >= 0)
3. two killer moves
4. four history-heuristic moves
5. remaining moves.
>
>-- Walter Faxon
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.