Search Algorithm¶

Overview¶

Kirin uses a negamax search with alpha-beta pruning, iterative deepening, and aspiration windows.

Alpha-Beta Search¶

Check transposition table for cached result score $\gets$ $-$ Store killer move $\beta$ $\alpha \gets$ score Update history heuristic Update PV table Store position in transposition table $\alpha$

Iterative Deepening¶

The engine uses iterative deepening with aspiration windows:

void searchPosition(int depth) {
  int score = 0;
  int alpha = -infinity;
  int beta = infinity;
  
  for(int currentDepth = 1; currentDepth <= depth; currentDepth++) {
    score = negamax(alpha, beta, currentDepth);
    
    // Aspiration window for next iteration
    alpha = score - 50;
    beta = score + 50;
    
    // Print UCI info
    printf("info score cp %d depth %d nodes %ld time %d pv ...", 
           score, currentDepth, nodes, getTimeMS() - startTime);
  }
  printf("bestmove ...");
}

Search Enhancements¶

Transposition Table¶

Zobrist hashing is used for position identification:

U64 pieceKeys[12][64];    // Random keys for each piece on each square
U64 enpassantKeys[64];    // Random keys for en passant squares
U64 castlingKeys[16];     // Random keys for castling states
U64 sideKey;              // Random key for side to move

U64 generateHashKey() { 
  U64 finalKey = 0ULL; 
  for(int piece = P; piece <= k; piece++) { 
    U64 bitboard = bitboards[piece];
    while(bitboard) { 
      int square = getLSBindex(bitboard);
      finalKey ^= pieceKeys[piece][square];
      popBit(bitboard, square);
    }
  }
  if(enpassant != no_sq) finalKey ^= enpassantKeys[enpassant];
  finalKey ^= castlingKeys[castle];
  if(side == black) finalKey ^= sideKey;
  return finalKey;
}

Move Ordering¶

Moves are ordered for optimal alpha-beta pruning:

Hash move (from transposition table)
Winning captures (MVV-LVA ordering)
Killer moves (quiet moves that caused beta cutoffs)
History heuristic (successful quiet moves)
Remaining quiet moves

MVV-LVA Table¶

Most Valuable Victim - Least Valuable Attacker scoring:

// MVV LVA [attacker][victim]
static int mvvLVA[12][12] = {
  105, 205, 305, 405, 505, 605, ...  // Pawn captures
  104, 204, 304, 404, 504, 604, ...  // Knight captures
  103, 203, 303, 403, 503, 603, ...  // Bishop captures
  102, 202, 302, 402, 502, 602, ...  // Rook captures
  101, 201, 301, 401, 501, 601, ...  // Queen captures
  100, 200, 300, 400, 500, 600, ...  // King captures
};

Repetition Detection¶

The engine maintains a repetition table to detect threefold repetition:

U64 repetitionTable[1000];
int repetitionIndex;

static inline int isRepetition() {
  for(int i = 0; i < repetitionIndex; i++) {
    if(repetitionTable[i] == hashKey) return 1;
  }
  return 0;
}

The pruning and reduction surface¶

Everything above describes the search’s skeleton. What actually determines its strength is the set of techniques layered on top that let it avoid searching most of the tree. Every one of them is individually switchable at runtime through a UCI option, which is not a convenience feature: it is the mechanism that makes the A/B testing in Ch. Measuring Strength possible at all. A technique that cannot be turned off cannot be measured.

Technique	Default	What it does
Principal variation search	on	assume the first move is best; search the rest with a null window
Null-move pruning	on	give the opponent a free move; if the position still fails high, prune
Late move reductions	on	search moves ordered late at reduced depth
Aspiration windows	on	re-search around the previous iteration’s score
History ordering	on	order quiets by how often they have caused cutoffs
SEE ordering	on	bucket captures as winning/losing before searching them
SEE pruning	on	skip losing captures in quiescence
Rich evaluation	on	the full positional term set (§Evaluation)
Futility pruning	off	skip quiet moves that cannot raise alpha
Singular extensions	off	extend a move that is much better than every alternative
ProbCut	off	shallow, wide-margin search to prove a beta cutoff early
Internal iterative deepening	off	shallow search to find a hash move when none exists
Continuation history	off	order by the follow-up to the previous move
NNUE evaluation	off	neural evaluation (Ch. NNUE Evaluation)

Note

The defaults above are the shipped defaults, read from kirin/src/engine/uci.cpp. Several powerful techniques are off. That is not an oversight — it reflects what has and has not been through an SPRT run. A feature stays off until it has demonstrated a gain; see Ch. Measuring Strength and decision D-13.

Late move reductions¶

The two governing constants live in search.cpp: the first fullDepthMoves = 4 moves at a node are searched to full depth, and reductions only apply at depth >= reductionLimit = 3. Beyond that, the reduction amount comes from a precomputed lmrReductionTable[depth][moveNumber], with one adjustment worth knowing about:

int reduction = lmrReductionTable[d][m];
if (pvNode && reduction > 0) reduction--;  // reduce principal-variation nodes less
return std::max(1, reduction);

Principal-variation nodes are reduced one ply less than the rest. The PV is the line the engine actually intends to play, so an error there costs far more than an error in a line it is merely refuting.

Null-move pruning¶

The reduction scales with remaining depth rather than being fixed:

int reduction = 2 + depth / 6;
score = -negamax(-beta, -beta + 1, depth - 1 - reduction);

Null-move pruning is unsound in zugzwang, where having to move is itself the disadvantage, so the guard conditions matter as much as the reduction — search.cpp gates it on side-to-move material and on not already being in check.

Static exchange evaluation¶

SEE answers “if I initiate this capture sequence on this square, do I come out ahead?” by playing out the exchange with the least valuable attacker each time. It is exposed as two independent options because the two uses carry very different risk:

SEE ordering re-buckets winning versus losing captures during move ordering. Low risk — it changes the order moves are examined, never which ones are examined.
SEE pruning skips captures with $\text{SEE} < 0$ in quiescence outright. More aggressive, and the one that can actually lose information: a losing capture is occasionally the point of a combination.

The Use SEE option sets both together; the individual options exist so a gauntlet can isolate which half of the technique is responsible for a result. That distinction is a comment in the source itself (search.cpp:71--72) and is exactly the kind of separation that makes an A/B result interpretable rather than merely positive.

History and continuation history¶

Plain history scores a quiet move by historyMoves[piece][target] — how often moving this piece to this square has caused a cutoff anywhere in the search. Continuation history extends the idea by conditioning on what was played immediately before, indexed [offset][prevPiece][prevTarget][piece][target], which captures follow-up patterns that plain history flattens away. It is off by default and is a natural SPRT candidate.