Origins
When developing a chess engine, particularly one based on a hand-crafted evaluation function, one of the most challenging tasks is optimizing the weights of that function. In this type of engine, a position is evaluated through a combination of several terms: material, mobility, pawn structure, king safety, piece activity, and numerous other strategic and positional factors. Each term is assigned one or more numerical coefficients, known as weights, which determine its relative importance.
The overall quality of a chess engine’s hand-crafted evaluation function depends to a large extent on the balance between these parameters. A weight that is too high may cause the engine to overvalue a particular aspect of the position, while a value that is too low may render it practically irrelevant. Furthermore, the various evaluation terms are not necessarily independent: changing the weight of one parameter can affect the effectiveness of others, making it difficult to manually identify the optimal combination.
When I was developing my first engine, Naraku, one of the most straightforward approaches was to gradually adjust individual parameters and evaluate the results by playing a large number of games. However, this was a time-consuming and inefficient procedure, especially as the number of weights to be optimized increased. Each modification required a new testing cycle and, once a seemingly better value had been found, the same process had to be repeated for the other parameters. It was often necessary to revisit previously adjusted weights to compensate for the effects of subsequent changes.
I therefore decided to develop a standalone tool to automate much of this process. The idea I came up with was relatively simple: instead of optimizing one parameter at a time, I would have numerous versions of Naraku compete against each other simultaneously, each featuring a different combination of weights, and let the results of their games determine which configuration deserved to survive.
I called this algorithm Highlander, after the famous motto, “There can be only one”, from the movie of the same name, starring Sean Connery and Christopher Lambert.
From a computer science classification perspective, Highlander belongs to the family of evolutionary algorithms and, more specifically, can be described as a (1+λ) evolution strategy based exclusively on mutation and elitist selection. This distinction is important: unlike a classical genetic algorithm, which is generally more complex, Highlander does not use a population of individuals that reproduce by combining their characteristics through crossover. Instead, the evolutionary process starts with a single individual, which generates a series of variants through random mutations.
How It Works
To understand how Highlander works, it is useful to briefly introduce the notation commonly used in evolution strategies.
In the (1+λ) formulation, the number 1 represents the single parent individual, while λ denotes the number of offspring generated in each generation. The “+” symbol indicates that, during the selection process, the parent competes directly against its offspring: the best-performing individual among all of them becomes the parent of the next generation.
In Highlander’s case, an individual was simply a particular version of Naraku, identified by the configuration of the weights in its evaluation function.
The algorithm starts with an initial version of the engine, which I will call the parent. This serves as the reference configuration and competes directly against dozens of automatically generated variants.
Each variant, or offspring, is created by randomly modifying one or more weights in the evaluation function. These perturbations are generated stochastically, with their magnitude varying according to the value of the parameter being modified. In general, weights with larger numerical values can undergo larger variations, whereas smaller weights are modified within narrower ranges. This approach makes it possible to explore the parameter space proportionally to the scale of the values used by the evaluation function, avoiding the indiscriminate application of the same mutation magnitude to coefficients that may differ considerably in scale.
Once the variants have been generated, the selection phase begins. All versions of the engine, including the parent, are pitted against one another in a large number of games played at extremely fast time controls. The goal is not so much to obtain an absolute measure of each variant’s playing strength, but rather to determine which weight configuration produces the best results relative to the others.
At the end of the competition, a single survivor is selected: the engine that has achieved the highest overall score. All the others are eliminated.
Hence the name Highlander.
This very mechanism is what characterizes the (1+λ) evolution strategy: the parent is not automatically replaced, but must prove itself inferior to at least one of its offspring. If none of the offspring achieves a better result, the parent itself survives and goes on to generate the next generation.
The Evolutionary Process
The surviving program thus becomes the new parent and serves as the starting point for the next generation.
Dozens of new variants are once again generated from its weights through further random mutations. The procedure is then repeated: offspring generation, competition, selection of the best candidate, and elimination of all the others.
An important feature of the algorithm is the gradual reduction in mutation magnitude.
In the early generations, weights can be modified within relatively wide ranges. The goal is to explore a sufficiently large portion of the solution space, identifying potentially better configurations even if they differ significantly from the initial one. As the process progresses, the mutation ranges are progressively narrowed. The new variants therefore become increasingly similar to their parent, and the modifications tend to focus on small adjustments to the parameters.
In this way, Highlander alternates between two complementary behaviours: an initial phase focused on exploring the solution space, followed by a phase increasingly dedicated to searching for a local optimum in the vicinity of the best configuration found so far. The process is repeated over numerous generations until further changes to the weights no longer produce significant improvements in the test results. At this point, the algorithm has converged.
From a mathematical perspective, the selection mechanism can be represented relatively simply. Let P denote the parent program and C₁, C₂, …, Cλ its λ offspring. The new parent of the next generation is the candidate that achieves the highest performance:
where F represents the fitness function, determined empirically from the results of the games.
This is therefore an elitist selection mechanism: the best solution is never discarded in favour of a worse one. This property guarantees that the observed result cannot deteriorate from one generation to the next, at least in terms of the score measured during the selection process. Naturally, as we shall see, the statistical variability of game results requires some additional considerations.
Advantages and Limitations
Compared with manual optimization or the sequential adjustment of individual parameters, Highlander offers several interesting advantages.
The first is its ability to evaluate numerous combinations of weights simultaneously. Rather than focusing on a single coefficient, the algorithm can modify multiple terms of the evaluation function and directly measure the overall impact of these changes on playing strength.
This approach is particularly useful when parameters interact with one another. A weight, for example, may appear ineffective when considered in isolation, but become beneficial in combination with specific values of other coefficients. Evaluating the entire configuration makes it possible to account for these dependencies without necessarily having to model them explicitly.
A second advantage is its relative simplicity of implementation. There is no need to know the analytical form of the function being optimized, calculate its derivatives, or have any prior information about the relationships between parameters. All that is required is the ability to generate a new version of the program and measure its performance through a series of games.
The algorithm also has a relatively good convergence rate, making it possible to achieve appreciable improvements in the evaluation function within a comparatively short period of time.
So much for the advantages. There are, however, some limitations as well.
The main problem with this type of algorithm is its tendency to converge towards local maxima: configurations that appear to be optimal but do not necessarily correspond to the best solution available across the entire parameter space.
Once a particularly competitive configuration has been identified, subsequent generations tend to explore an increasingly narrow region around it. If the search has started in the wrong region, moving away from it becomes difficult. The algorithm will eventually converge towards a suboptimal solution.
To address this problem, I adopted a rather straightforward strategy: occasionally and randomly modify some of the weights in the best configuration and start a new testing cycle. In other words, rather than continuing the search around the latest survivor, the idea is to deliberately perturb the solution. I used this approach as a starting point for a further evolutionary process.
This technique does not guarantee that local maxima will be avoided, but it increases the chances of exploring different configurations and, occasionally, discovering better solutions.
Another limitation, which I unfortunately became aware of quite early on, is the statistical nature of the selection process. Games played at very fast time controls make it possible to accumulate a large number of results quickly, but inevitably introduce a certain degree of variability. A variant may prevail not only because its weights are genuinely better, but also because of a favourable combination of positions, opening lines, or random outcomes. For this reason, it is important to have a sufficiently large number of games: a test sample that is too small may lead to the selection of a lucky variant rather than one that is genuinely stronger.
From a statistical standpoint, the score obtained over a limited number of games is merely an estimate of the engine’s actual relative playing strength. Nevertheless, using Highlander, rather than testing each individual weight separately over what would still have been a considerable number of games, allowed me to reduce the total number of games required by several orders of magnitude.
Comparison with Modern Tuning Methods
There are considerably more sophisticated and, in many cases, more efficient optimization methods for automatically tuning the evaluation functions of chess engines.
One particularly interesting example is Texel’s Tuning Method, proposed by Peter Österlund and used in the Texel chess engine.
Unlike Highlander, which selects parameter configurations based directly on the results of competitions between different versions of the program, Texel’s Tuning uses a collection of games to extract a set of positions and compare the engine’s evaluations with the actual outcomes of those games.
The procedure is based on logistic regression and the minimization of an error function that relates the evaluation of each position to the probability of its corresponding game result. Optimization can be performed simultaneously on a very large number of parameters, using numerical local-search techniques and more advanced optimization methods.
This approach offers significant advantages: it can make use of millions of positions extracted from previously played games, reduces the need to continuously organize tournaments between new engine variants, and makes it possible to optimize numerous coefficients in a structured manner.
With today’s available tools, particularly for traditional evaluation functions characterized by a large number of parameters, techniques such as Texel’s Tuning generally offer a considerably more effective and systematic solution.
Beyond Chess
Although I had originally designed it specifically for Naraku, without knowing at the time what an evolutionary algorithm actually was, Highlander had one characteristic that immediately struck me during my first experiments: its structure was, and still is, extremely generic.
The algorithm does not require any specific knowledge of the problem being optimized. The only requirements are the ability to generate variants of an initial solution by modifying some of its parameters, and the availability of a quantitative criterion for measuring their performance. More generally, all that is needed is an objective function, even if it is complex or not easily differentiable, against which each candidate can be evaluated.
This characteristic led me to occasionally reuse Highlander in my work as a chemical engineer, adapting it to optimization problems quite different from those for which it had originally been developed.
In engineering, it is quite common to encounter situations in which an optimal combination of parameters must be identified without having access to a simple analytical relationship between the input variables and the final result. In certain circumstances, the objective function may be represented by a function to be fitted, a numerical model, or a relatively complex computational procedure.
In such cases, an evolution strategy can be particularly interesting precisely because it does not require any knowledge of the underlying mathematical structure of the problem: it simply needs to generate new configurations and compare their results.
Recently, I have resumed working on Highlander with the aim of using it in Musashi, the new chess engine I have started developing, while also looking for ways to further improve the algorithm.