I can either write a hundred lines of code for one or two Elo or find one or two wrong lines of code for a hundred Elo. Such is life.

My long-running slow-burn side project is Fiddler, a chess engine. The last time I wrote about it, I wrote about 300 lines of code to get a 6 Elo improvement, equivalent to a 1% improvement to its match performance. This time, I’m writing about a more recent development, when I edited one line of code to get a 64 Elo improvement, for about a 9.2% improvement in match performance.

To avoid clickbaiting you, here’s the line in question.

if best_score >= beta { BoundType::Upper } else { BoundType::Lower }

However you’ll have to read the rest of this post for a full explanation..

Learning to sing the alpha-beta

Our story begins with the foundational algorithm of all classical chess engines: alpha-beta search. It’s a small, yet critical improvement to the Minimax algorithm. By adding a set of bounds parameters, we can reduce the runtime of searching a game tree with branch factor and depth from in Minimax to in alpha-beta, subject to some constraints.

The core idea behind alpha-beta is that we never need to search a line that has already been refuted. If you try a move and find that it trivially loses the game, there’s no point in finding out all the other ways that playing the move can lose you the game. Under ideal search heuristics, this means that we only need to check one move (the critical move) at each depth, which yields a halving in the effective depth of our search.

I’ll give a brief pseudocode description of alpha-beta below.

def alpha_beta(game, depth, alpha, beta):
if depth == 0 or game.is_over():
return leaf_evaluate(game) # heuristic evaluation of the game

score = -infinity
for m in game.moves():
game.make_move(m)
score = max(score, -alpha_beta(game, -beta, -alpha))
game.undo_move()

alpha = max(alpha, score)
if score >= beta:
break

return score

In practice and in my code, most engines use an extension of alpha-beta search called principal variation search; however, we do not need to discuss it for the sake of this post.

Transposing isn’t just for matrices

Those familiar with chess (the kind played by humans) may know the term transposition. Transposition is the process by which two different sequences of moves can reach the same position. For instance, e4 e5 Nf3 Nc6 yields the same position as Nf3 Nc6 e4 e5.

To take advantage of this, chess engines use a transposition table: a glorified hash-map from positions to useful evaluation data. If all you care about is the high-level algorithms, you can treat it like a hash-map and call that a day. However, since you’ve bothered to read this far, I think you might like to hear about the internal details of my transposition table’s implementation. In my engine, every entry in the map stores the evaluation, search depth, best move, and some other extra data.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
/// An entry in the transposition table.
pub struct TTEntry {
tag: u8,         key_low16: u16,             pub depth: i8,         pub best_move: Option<Move>,         pub value: Eval, } /* total size: 8 bytes */

However, just storing a raw evaluation in the transposition table is insufficient. The core problem is that in an alpha-beta search, the evaluations of a position are not exact: often, we don’t know the exact evaluation of a position, only a lower or upper bound on its value. If you wanted, you could store a pair containing the upper and lower bound of the evaluation for each position, but that requires 32 bits - not very efficient.

In my engine, each evaluation is a 16-bit integer. Meanwhile, there are three possible cases for the type of an evaluation:

• exact evaluations, where the value stored in the table is the exact value of the evaluation of the position,
• lower bounds, where a beta cutoff has occurred, and
• upper bounds, where an alpha cutoff has occurred.

If we assume that all values of an Eval are used, that means we need to express ![](data:image/svg+xml,%3Csvg%20class%3D%22typst-doc%22%20viewBox%3D%220%200%2068.02567777777777%2021.878999999999998%22%20width%3D%2268.02567777777777pt%22%20height%3D%2221.878999999999998pt%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20xmlns%3Axlink%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxlink%22%20xmlns%3Ah5%3D%22http%3A%2F%2Fwww.w3.org%2F1999%2Fxhtml%22%3E%0A%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%200%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-group%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%280%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g65E1D552EC5C6CAF9D05332A228A5D13%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%286.5%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g519539DFB7C3B4CC2ADC59E4BE021112%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2815.88888888888889%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g336941987CF1DC5E91C04B83C279288F%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2828.891777777777776%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g3A6D0C4E38D1D84234788C3515FFABFF%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23gCA7B675BF5428ADA44A6BA224A38E08F%22%20x%3D%223.6140000000000003%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23gC9779672C52C758CEA74B8B35DEF5EAE%22%20x%3D%2210.114%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2845.50577777777777%2018.590000000000003%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23gFDA419B76A9D37F8650592252C53A8E%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2851.411677777777776%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g192572223871326894A4BD925EDB7FF0%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2856.46867777777778%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g3F5F39516EB44A39BCA9BC78DC789217%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20transform%3D%22translate%2862.96867777777777%2015.379%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cg%20class%3D%22typst-text%22%20transform%3D%22scale%281%2C%20-1%29%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3Cuse%20xlink%3Ahref%3D%22%23g40D2F3CABA690FF94C49784F3505354B%22%20x%3D%220%22%20fill%3D%22%23000000%22%20fill-rule%3D%22nonzero%22%2F%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%3Cdefs%20id%3D%22glyph%22%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g65E1D552EC5C6CAF9D05332A228A5D13%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%203.497%208.658%20C%202.964%208.112%202.184%207.839%201.1570001%207.839%20L%201.1570001%207.3320003%20C%201.8330001%207.3320003%202.392%207.4360003%202.821%207.644%20L%202.821%201.066%20C%202.821%200.832%202.769%200.676%202.652%200.611%20C%202.535%200.546%202.21%200.507%201.69%200.507%20L%201.235%200.507%20L%201.235%200%20C%201.5600001%200.026%202.262%200.039%203.341%200.039%20C%204.42%200.039%205.122%200.026%205.447%200%20L%205.447%200.507%20L%204.992%200.507%20C%204.459%200.507%204.1340003%200.546%204.03%200.611%20C%203.926%200.676%203.861%200.832%203.861%201.066%20L%203.861%208.268001%20C%203.861%208.58%203.835%208.658%203.497%208.658%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g519539DFB7C3B4CC2ADC59E4BE021112%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%204.979%206.552%20C%205.408%206.552%205.616%206.7730002%205.616%207.215%20C%205.616%208.151%204.914%208.658%203.9520001%208.658%20C%202.8730001%208.658%202.015%208.151%201.378%207.124%20C%200.819%206.2400002%200.546%205.2390003%200.546%204.1080003%20C%200.546%202.457%200.845%201.3000001%201.4560001%200.611%20C%201.9760001%200.013%202.5740001%20-0.286%203.263%20-0.286%20C%204.056%20-0.286%204.7060003%200.013%205.2130003%200.611%20C%205.6940002%201.183%205.941%201.872%205.941%202.665%20C%205.941%203.4580002%205.7070003%204.1340003%205.2390003%204.6930003%20C%204.745%205.291%204.1080003%205.603%203.341%205.603%20C%202.665%205.603%202.145%205.2260003%201.794%204.498%20L%201.794%204.576%20C%201.794%206.045%202.158%207.293%202.938%207.8650002%20C%203.276%208.112%203.627%208.229%203.9780002%208.229%20C%204.446%208.229%204.784%208.099%205.005%207.826%20C%204.563%207.826%204.342%207.579%204.342%207.189%20C%204.342%206.8250003%204.6150002%206.552%204.979%206.552%20Z%20M%204.472%204.42%20C%204.6150002%204.1210003%204.6930003%203.536%204.6930003%202.678%20C%204.6930003%201.8330001%204.6280003%201.274%204.485%200.98800004%20C%204.225%200.455%203.822%200.18200001%203.263%200.18200001%20C%202.8860002%200.18200001%202.6000001%200.312%202.392%200.572%20C%202.223%200.78000003%202.106%200.962%202.0540001%201.105%20C%201.898%201.508%201.82%202.119%201.82%202.951%20C%201.82%203.315%201.872%203.6660001%201.963%204.004%20C%202.132%204.6150002%202.6130002%205.1870003%203.328%205.1870003%20C%203.835%205.1870003%204.225%204.927%204.472%204.42%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g336941987CF1DC5E91C04B83C279288F%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%209.074%203.562%20L%205.369%203.562%20L%205.369%207.267%20C%205.369%207.4750004%205.2650003%207.579%205.057%207.579%20C%204.849%207.579%204.745%207.4750004%204.745%207.267%20L%204.745%203.562%20L%201.04%203.562%20C%200.832%203.562%200.72800004%203.4580002%200.72800004%203.25%20C%200.72800004%203.042%200.832%202.938%201.04%202.938%20L%204.745%202.938%20L%204.745%20-0.767%20C%204.745%20-0.975%204.849%20-1.079%205.057%20-1.079%20C%205.2650003%20-1.079%205.369%20-0.975%205.369%20-0.767%20L%205.369%202.938%20L%209.074%202.938%20C%209.282001%202.938%209.386001%203.042%209.386001%203.25%20C%209.386001%203.4190001%209.243%203.562%209.074%203.562%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22g3A6D0C4E38D1D84234788C3515FFABFF%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%201.872%200.039%20L%203.315%200%20L%203.315%200.507%20C%202.8470001%200.507%202.561%200.52%202.47%200.572%20C%202.379%200.624%202.3400002%200.78000003%202.3400002%201.0270001%20L%202.3400002%209.022%20L%200.42900002%208.879%20L%200.42900002%208.385%20C%200.884%208.385%201.1700001%208.346%201.261%208.268001%20C%201.352%208.190001%201.404%208.008%201.404%207.709%20L%201.404%201.0270001%20C%201.404%200.78000003%201.365%200.624%201.274%200.572%20C%201.183%200.52%200.897%200.507%200.42900002%200.507%20L%200.42900002%200%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22gCA7B675BF5428ADA44A6BA224A38E08F%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%203.237%20-0.143%20C%204.043%20-0.143%204.719%200.143%205.278%200.71500003%20C%205.837%201.2870001%206.123%201.9760001%206.123%202.782%20C%206.123%203.601%205.85%204.316%205.304%204.914%20C%204.758%205.512%204.0690002%205.8240004%203.25%205.8240004%20C%202.431%205.8240004%201.755%205.512%201.196%204.914%20C%200.637%204.316%200.36400002%203.601%200.36400002%202.782%20C%200.36400002%201.9760001%200.637%201.2870001%201.196%200.71500003%20C%201.755%200.143%202.444%20-0.143%203.237%20-0.143%20Z%20M%203.25%200.273%20C%202.6260002%200.273%202.158%200.546%201.8330001%201.105%20C%201.625%201.469%201.521%202.0670002%201.521%202.8860002%20C%201.521%203.6790001%201.625%204.251%201.82%204.6150002%20C%202.132%205.1740003%202.6000001%205.447%203.237%205.447%20C%203.848%205.447%204.316%205.1740003%204.6410003%204.6410003%20C%204.862%204.277%204.966%203.6920002%204.966%202.8860002%20C%204.966%201.378%204.524%200.273%203.25%200.273%20Z%20%22%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2Fsymbol%3E%0A%20%20%20%20%20%20%20%20%3Csymbol%20id%3D%22gC9779672C52C758CEA74B8B35DEF5EAE%22%20overflow%3D%22visible%22%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%3Cpath%20d%3D%22M%205.603%205.889%20C%205.109%205.889%204.6540003%205.6940002%204.238%205.304%20C%203.848%205.603%203.4060001%205.7460003%202.8990002%205.7460003%20C%201.781%205.7460003%200.767%204.914%200.767%203.822%20C%200.767%203.276%200.962%202.834%201.352%202.496%20C%201.105%202.184%200.975%201.8330001%200.975%201.4300001%20C%200.975%200.936%201.144%200.559%201.469%200.312%20C%200.92300004%200.13%200.36400002%20-0.338%200.36400002%20-1.001%20C%200.36400002%20-1.5600001%200.72800004%20-2.002%201.4430001%20-2.3140001%20C%201.9890001%20-2.561%202.5870001%20-2.678%203.237%20-2.678%20C%203.9%20-2.678%204.511%20-2.561%205.057%20-2.3140001%20C%205.7720003%20-2.002%206.123%20-1.5600001%206.123%20-0.975%20C%206.123%20-0.286%205.837%200.221%205.2650003%200.546%20C%204.6670003%200.871%204.004%200.91%203.042%200.91%20C%202.47%200.91%202.158%200.91%202.093%200.92300004%20C%201.7290001%200.975%201.469%201.326%201.469%201.7290001%20C%201.469%201.924%201.521%202.106%201.638%202.262%20C%202.002%202.015%202.418%201.885%202.8990002%201.885%20C%204.017%201.885%205.018%202.717%205.018%203.809%20C%205.018%204.316%204.849%204.732%204.511%205.057%20C%204.836%205.356%205.1870003%205.499%205.564%205.499%20C%205.499%205.434%205.46%205.33%205.46%205.2000003%20C%205.46%204.914%205.603%204.771%205.889%204.771%20C%206.162%204.771%206.3050003%204.914%206.3050003%205.2130003%20C%206.3050003%205.616%205.993%205.889%205.603%205.889%20Z%20M%202.8990002%205.343%20C%203.601%205.343%203.9520001%204.836%203.9520001%203.822%20C%203.9520001%202.795%203.601%202.275%202.8990002%202.275%20C%202.184%202.275%201.8330001%202.782%201.8330001%203.809%20C%201.8330001%204.836%202.184%205.343%202.8990002%205.343%20Z%20M%202.132%200.052%20L%202.8860002%200.052%20C%203.562%200.052%204.1080003%200.013%204.524%20-0.078%20C%205.083%20-0.19500001%205.356%20-0.507%205.356%20-1.001%20C%205.356%20-1.417%205.096%20-1.742%204.576%20-1.9890001%20C%204.173%20-2.184%203.7310002%20-2.275%203.25%20-2.275%20C%202.782%20-2.275%202.3400002%20-2.184%201.924%20-1.9890001%20C%201.391%20-1.742%201.131%20-1.417%201.131%20-1.001%20C%201.131%20-0.455%201.599%200.052%202.132%200.052%20Z%20%22%2F%3E%