Author: Omid David Tabibi
Date: 18:37:35 07/13/03
Go up one level in this thread
On July 13, 2003 at 12:33:10, Robert Hyatt wrote:
>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
And how is the history heuristic implemented in Crafty? A simple
[side][piece][square] array? And how is the data stored in the history (and
updated)?
(I agree with Walter, we really need a Crafty algorithm FAQ. Tracking the ideas
behind that highly optimized (i.e., unreadable) code is not that easy...!)
>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.