Extended Ease Metric (2): Variation Ease

Intro

Hey all, in this blog I will go over one of the most interesting problems I been trying to solve, given a chess variation and position, how easy is the variation? This question came from when I was working on extending the original ease metric for a given position. If you have not already, feel free to read my analysis on the extended ease metric formula here. Coming back to this problem, I thought this will more challenging than just analyzing how easy a position is via comparison of candidate moves to Stockfish since we are dealing with list of moves, and doing brute force of computing the extended ease metric for each move will make the algorithm very slow, approximately O(n^3) time complexity, and it will also exhaust the engines and neural nets. Looking at what @matstc came up with in the original ease metric collab notebook was interesting. I will quote the algorithm and notes here.

## Over Multiple Moves
A single position is not quite enough. I am interested in how easy it will be to find **one good move after another**. If a natural move has to be followed up with a difficult one, then the ease of the current position is less relevant. Let’s look at the ease over multiple moves.
The algorithm below looks at the next 3 moves by one color (i.e. 5 plies) and calculates the ease for all of the visited positions. The final metric is the minimum ease that was encountered.
A few assumptions are made when building the move tree:
- The imaginary opponent only plays the best moves.
- The player will play a natural-looking move among the top moves ranked by P. All of these moves are searched.
- If P for any move is below the P-threshold, that move will be excluded. This removes noise from the metric when non-natural moves lead to terrible consequences for the player.
Picking out the minimum ease encountered seems reasonable because the opponent has an incentive to steer the player towards difficult paths. If most paths are easy to play but one is very difficult, then I assume the player will want to avoid that position entirely, instead of hoping that the difficult variation will not happen. - Matstc

This algorithm that was described is indeed better than the brute force I was thinking about, as at least here we are selective on which positions to discard when P-threshold is not met, but the problem was again building this tree for just natural looking moves where the opponent always plays the best move seemed contradictory to finding ease over a list of moves, because not all natural P move be best and than if imaginary opponent is always playing "best" engine move, than in the tree there will be many paths where playing the natural move just to justify the algorithm would lead to more lost positions as natural P not be the best move at all. This also might make paths lead to hard positions for the player, given that their opponent is always playing the best move, so this just makes it unfair and unrealistic, ease metric calculations, either we make the imaginary player play natural moves as the player like a human vs human game, or we make both players play the best moves in a given variation (full engine line), this way the paths to easy and hard in a tree are equal, so than searching a equal tree would make calculations correct, as both sides are doing their best to finding moves in a variation. While I wanted to fix the algorithm on the logic above, another thing that was hard to optimize was the computation time. If I'm building the tree by myself, just using neural nets on the user's browser is overkill, so I just left the problem hanging in my head for quite a few weeks...

A chess variation tree from the starting position: if the natural-looking move was the worst, and an imaginary player played the best move, say the first branch, then the ease metric for branches 2nd and 3rd is automatically ignored, even though those branches could have an easier path. Here, there are a few branches. Imagine now searching 50 positions, which will require a lot of computation time to run on any browser. Image by chrisbutner

Finding The Solution

The solution to the problem seemed hard, and I honestly didn’t care much, especially since I had already published my extended ease metric blog a couple of days earlier. So I almost forgot about it until a later day, when I decided to take the bus.
Given how funny this is as a way to find the solution, I’ll share it here anyway.

I was taking the bus to a nearby chess event, and I had left quite early, knowing how bad evening traffic can be. I found a seat in front of the map that shows the next station and draws the entire route the bus takes. As I rode, it became annoying that the bus kept stopping at stations where no one was getting on. Every few stations, I checked the time and stared at the map to see what the next stop was. I basically kept doing this until I finally arrived at my destination and checked the clock again, only to realize I was late by 45 minutes!

I told myself the bus trip was brutal. I had left at 6:00 PM and arrived around 8:30 PM, and suddenly something clicked. I knew the time I left home and the time I arrived, so I easily calculated how late I was by subtracting start time from end time. Then I thought about this problem of finding ease over variations.
I realized that if a move in a variation is like a station on the bus map, and if the ease metric for that move is the time you reach that nth station, then the ease of a variation is simply the difference between how easy the position was and how easy it becomes.

It makes sense: no matter how many moves there are, or whether they’re easy or hard, they can be disregarded. After all, once you’ve played those moves and reached the destination, the real question is whether you’re happy with the position you ended up in compared to where you started. Such a simple observation, but a key one that supports the Variation Ease Function I be presenting.

The above represents the variation ease function mathematically, Pvease = Pv(n - 1) ease - R ease, Let me put it in words, the 1) is my extended ease metric for my previous blog, 2) is the converter function that converts Stockfish cp to Q, 3) says given a variation has N moves, lets say m1, m2, m3 .. all the way to mN, we can have Pv contain a list of ease metrics related to that moves, 4) is my Variation ease function, the ease of entire variation is the ending move's ease metric (n-1) - the starting root ease metric.

We can say a variation is easy if the delta is > 0.1, hard variation if < 0.1, otherwise similar ease from where we started.

A sample tree visualization, the values here are sample values. As you can see, if Pv values get lower as we approach the Nth move, the variation becomes harder than where we started.

Stockfish Variation Ease Function Code

Given the function above that finds the ease of any variation, we can easily compute the ease metric of a given Stockfish variation. Note that a Stockfish variation already provides paths where both players are playing their best moves, so we don’t run into the issue of missing easy or hard paths that I discussed earlier.

Computing the ease metric of a Stockfish variation tells us how easy it would be for a human to follow that variation up to the Nth move from their starting position. This gives us insight into something important: even if a variation is objectively best, is it practical for humans?

Stockfish already provides a principal variation (PV) consisting of a list of top moves. From there, all that’s left is to compute the variation ease metric.
Below is the Stockfish Variation Ease Metric calculator code. You can also explore the React hook that helps in finding Vith ease metric and engine eval here.

import { PositionEval } from "@/stockfish/engine/engine";
import { MaiaEvaluation } from "../nets/types";
import { StockfishEaseMetricCalculator } from "./stockfishEaseMetric";

export class StockfishVEaseMetricCalculator {

    private stockfishCalculator: StockfishEaseMetricCalculator;

    constructor(log: boolean){
        this.stockfishCalculator = new StockfishEaseMetricCalculator(log);
    }

    public calculatePvEaseMetric(RnetEval: MaiaEvaluation, REngineEval: PositionEval | null, ViNetEval: MaiaEvaluation, ViEngineEval: PositionEval | undefined): number {
        if(!REngineEval){
            console.log('Root Engine lines not present, exist 0');
            return 0.5;
        }
        const REase = this.stockfishCalculator.calculateEaseMetric(RnetEval, REngineEval); 
        const ViEase = this.stockfishCalculator.calculateEaseMetric(ViNetEval, ViEngineEval!);

        console.log('R ease is start:', REase);
        console.log('Vi ease is end:', ViEase);
        const diff = ViEase - REase;
        console.log('diff: ', diff);

        return diff;
    }

}

Sample Tests

I would show some screenshots of my function in play, the EM change tells us the Pv ease here, and the slider allows us to select how many moves we want to have in the variation itself, so if we pick 9 moves, the EM change will tell us how would ease metric looks like from the starting position to the 8th move in that variation

Red indicates the position becomes harder, grey indicates the variation is the same in ease from start, and green represents it's easier than before. According to the algorithm, playing d4 d5 c4 e6 Nf3 Nf6 Nc3 c5 cxd5 is slightly harder than other variations.

Here in a typical open Sicilian position, when we consider up to 20 moves in a calculated variation, we find that playing the best variation Be3 a6 Bd3 Bb4 O-O Nxd4 Bxd4 e5 Be3... is harder than other candidate variations!

Conclusion

This concludes my in-depth analysis of developing a formula that produces an objective measure of the ease of a given variation. I explored several possible algorithms that could have addressed this problem, but ultimately, I believe the function I designed is both simple and effective.

Of course, the system is not perfect. Because it relies on browser-based Stockfish and the T1-256 Leela neural network, the evaluations can still be slightly inaccurate. Even so, I believe this approach is far more informative than simply staring at Stockfish’s top five variations and guessing whether any of them are actually practical for human play. Looking ahead, I plan to write a follow-up paper exploring how this ease metric may correlate with Lichess puzzle ratings.

Thanks for reading!

Noob