Author: Walter Faxon
Date: 00:53:19 07/13/03
Go up one level in this thread
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?
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?
So, provisionally:
1) PV (if available)
2) TT (if available)
3) New captures (or promotions)
4) Killer captures (or promotions)
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...
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!
-- 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.