An exploration of evolutionary ai
Evolutionary algorithms (EA) are a subset of ai that solve problems using methods inspired by biological evolution. From neural network optimization to resource scheduling, they have an impressive variety of real-world applications. Its beauty comes through a shift in focus on what it takes to solve a problem. Instead of describing the steps necessary to achieve a goal, EAs describe what the goal is like.
In this article I will explore how we can use this fantastic ai to generate chess puzzles, the benefits it provides and the drawbacks we need to consider.
A chess puzzle is a legal chess position, where a unique combination of moves results in a victory, often ending in checkmate. They are typically found analyzing databases of competitive games between human players.
By generating my own puzzles using nothing more than code, randomness, and a pinch of biology, an interesting and diverse database of puzzles can be created. Let's explore how.
Evolutionary algorithms typically work by randomly generating a large population of results, then selecting the “fittest” results using a heuristic, and finally taking those “fittest” results and generating subsequent random populations. They are inspired by Darwin's theory of natural selection, according to which animals in a population that are more likely to survive are also more likely to pass on their traits to the next generation. After many generations, sometimes hundreds of thousands, the population converges toward an optimal outcome. So how can we apply this to chess?
With chess, we can create a population of random legal positions by simulating games in which the program takes turns making random moves for white and black a random number of times. By repeating this process tens of thousands of times, large samples of random positions can be analyzed for suitability.
Below you can see a feature of my Board class, which returns a list of moves.
public List<(int() from, int() to)> GetAllPotentialMoves(Colour currentColour)
{
var activePieces = ActivePieces.Find(p => p.colour == currentColour);
var allLegalMoves = new List<(int() from, int() to)>();foreach (var piece in activePieces.pieces)
{
var moves = piece.GetLegalMoves(this);
allLegalMoves.AddRange(moves);
}
return allLegalMoves;
}
Once a population of positions has been generated, the really complicated stuff begins. The key to any evolutionary algorithm is how it evaluates its heuristics. In my case, only positions where a single solution led to checkmate were considered for a puzzle. After narrowing down those results, the heuristic is a measure of how difficult it is to choose the right moves to win the game. But how can a computer program estimate how difficult it is for a human to interpret a chess position?
One option is to look at the structure of the puzzle. Is the king safe? Are there moves that don't solve the puzzle, but look good? Do we sacrifice any material? What pieces are we moving? By evaluating many factors, we can create a measure of difficulty. The problem with this approach is that it is very difficult to decide how to create a final score from so many factors. Rigid rules also completely ignore biases in human perception. It could be that even subtle changes in a chess position make it much more difficult for some individuals to choose the correct move.
So how can we get a better idea of human performance? Using large databases full of real games, machine learning models have been trained to play chess like players of certain levels. Through these models we can get a better idea of how players of different abilities might attempt to solve a puzzle. Can an ai trained with 1200 ranked players solve the puzzle? What about 1600, 1900? The benefit of this approach is that it delves deeper into the minds of real players. However, machine learning models are not without drawbacks. These AIs don't play like a real player, they play like an approximation of a player. They are also trained in real, regular games, which means they may not be reliable when evaluating random chess positions.
By combining machine learning models with complex and detailed rules-based evaluation, I created a best-of-both-worlds scenario. A heuristic that understands the composition of the puzzle while also considering how humans might approach it.
Once the best puzzles of a population have been found, the next step is to create new generations. This can be done using many techniques inspired by evolution. I chose to use crossover and mutation.
Crossover involves randomly merging features from two outcomes in the hopes of getting the best features from both. We can cross similar chess positions by backtracking a series of moves to a shared starting point and then choosing legal moves used to achieve each outcome. Maybe moving the queen gave one puzzle a really cool property, and moving the knight made another puzzle interesting. By combining both features we create an even more compelling problem.
Likewise, we can mutate puzzles by going back and then forward a series of moves. Depending on how many moves you make back and forth, you can change the puzzle subtly or massively. Too much mutation and the algorithm will never improve; too little, the best result could converge to a single value too quickly.
The most common problem with evolutionary algorithms is convergence too quickly. Initially, the puzzles it was generating stopped improving after just a few generations. In the real world, physical borders such as mountains, deserts and seas have prevented populations from crossing their DNA, allowing genetic diversity to be preserved. Without enough genetic diversity, a population will not evolve much. By running smaller populations of chess puzzles in parallel for a while, I gave them enough room to maintain some diversity and avoid converging too early.
Evolutionary algorithms can also be very slow. Chess is certainly no exception. Running a heuristic evaluation on millions of chess positions requires a considerable amount of processing. Generally, the longer a chess engine runs in a position, the more accurately it can predict the next best move. By finding the sweet spot in the time spent analyzing each position, selecting the most promising ones, and looking at them in much more detail, I was able to optimize the time by a reasonable amount. Deciding when to stop generating is also crucial. If a sample has stopped improving for several generations, it may be best to start over with a new random population, since it may not be able to improve much further. After countless optimizations, my home PC is capable of generating over 1000 challenging puzzles per day using evolution.
Finally, diagnosing errors can be incredibly difficult. With many programs you can expect certain results given certain inputs. With evolution the situation is different. I spent a lot of time scratching my head wondering why my population was converging too quickly. Was it position generation? Were the methods evolutionary, perhaps heuristic? It can be easy to not even notice if some things are not working as intended when the expected outcome of a program cannot be clearly defined.
However, issues aside, the power and potential of this ai technique shines for all to see. Using just my old PC, I've been able to generate almost 50,000 chess puzzles in 3 months, containing a huge number of weird and wonderful positions.
The random nature of the algorithm means it creates an incredibly colorful and diverse set of puzzles. Interesting tactical problems that we rarely see in chess, such as queen sacrifices, knight raises, and the walk, are easy to find using evolution, but difficult using real game databases. However, the nonsensical nature of the puzzles makes them less applicable to real-world scenarios. Although they are a lot of fun, one could argue that puzzles based on real games are better for learning common patterns in chess games.
In addition to being incredibly productive, the algorithm is also exceptionally flexible. Shatranj, crooked chess boards, it is easy to extend the EA to work with any chess derivative. This extensible nature is where the evolutionary technique really excels. You can't do this with game databases, as they simply don't exist!
Although a forgotten corner of ai for many, I have demonstrated how evolution can be used to create a novel solution to a real-world problem. There is a lot of unexplored potential with this technology. With generative ai on the rise, I wonder what other original applications people will find for EAs in the future…
You can experience the puzzles for yourself on my website, chesspuzzler.com.
Unless otherwise noted, all images are the author's.
