2

I implemented the killer move heuristic based on my understanding, but is it correct?

Inserting a killer move when a non-capture causes a beta cutoff (i is a Move pointer)

// Stuff
if(val >= beta){
        // Non capture move that causes a beta cutoff = Killer Move
        if(!GameObj.is_capture(*i, player))
            insert_killer(*i, depth);
        return beta;
    }

Actual Insertion By Shifting

void insert_killer(Move m, short depth){
for(short i = 0; i < KillerSize - 1; i++)
    // Shift the moves
    KillerMoves[depth][i] = KillerMoves[depth][i + 1];
KillerMoves[depth][KillerSize - 1] = m;
}

Storing in move generator

vector<Move> non_captures;
vector<Move> captures;
vector<Move> Killers;
// Stuff
if(!this->is_capture(move)){
    if (is_killer(depth, move))
        Killers.push_back(move);
    else
        non_captures.push_back(move);
}
// Stuff

Ordering in move generator

// Stuff
vector<Move> all_moves;
sort(captures.begin(), captures.end(), comparer);
all_moves.reserve(captures.size() + non_captures.size() + Killers.size());
all_moves.insert(all_moves.end(), captures.begin(), captures.end());
if(!capture_only){
    all_moves.insert(all_moves.end(), Killers.begin(), Killers.end());
    all_moves.insert(all_moves.end(), non_captures.begin(), non_captures.end());
}
return all_moves;
1
  • This question might be better suited for another community, like the Computer Science one. It involves code and optimizing the alpha-beta pruning algorithm, and there's not much that is chess specific. – Inertial Ignorance May 6 '20 at 10:55
2

This appears fine to me. However, there are some things to note:

1) Its important to be careful that you do not try playing the same move twice. Your "Storing in Move Generator" appears to accomplish this.

2) It is generally a bad idea to save the SAME killer into multiple slots of your table. This reduces to effective size of your Killer Move table, and also makes it possible such that the following occurs: Your table contains {A, B, C, D} for a given depth. Move D is then found to refute 3 different lines of play (Awesome!), now your table contains {D, D, D, D}. If A, B, or C had any value, it is now lost.

3) From personal experience, there is hardly any benefit to having more than two Killer moves for a given depth. In Ethereal, three-moves loses elo over two-moves, and two-moves is almost the same as one-move. I believe Stockfish uses two killers, although my information may be out of date.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.