Author: Robert Hyatt
Date: 20:51:16 07/13/03
Go up one level in this thread
On July 13, 2003 at 21:37:35, Omid David Tabibi wrote:
>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)?
Just a simple <from><to> combination, 12 bits (6 from 6 to). This produces
a 64 X 64 array of 4096 entries.
When a move doesn't fail low (best move or fail high move) I add depth*depth
to the history counter. A simple selection sort tries the best four history
value moves at any ply, by picking them out one at a time.
>
>(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.