An exploration of Evolutionary AI

Evolutionary Algorithms (EAs) are a subset of AI that solve problems using methods inspired by biological evolution. From optimizing neural networks to resource scheduling, they’ve a shocking range of applications in the actual world. Their beauty emerges through a shift in focus in what’s required to resolve an issue. As a substitute of describing the steps required to achieve a goal, EAs describe what the goal looks like.

In this text I’ll explore how we will utilize this unbelievable AI to generate chess puzzles, the advantages it provides, and the drawbacks we’d like to contemplate.

A chess puzzle is a legal chess position, where one unique combination of moves leads to a win, often ending in a checkmate. They’re typically found by analysing databases of competitive games between human players.

By generating my very own puzzles using nothing but code, randomness, and a sprinkle of biology, an interesting, diverse database of puzzles may be created. Lets explore how.

Evolutionary Algorithms typically work by randomly generating a big population of results, then picking the ‘fittest’ results using a heuristic and eventually taking those ‘fittest’ results and generating subsequent random populations. They’re inspired by Darwin’s theory of natural selection, where the animals in a population which usually tend to survive are also more prone to pass on their traits to the subsequent generation. After many generations, sometimes a whole bunch of 1000’s, the population converges on an optimal result. So how can we apply this to chess?

With chess, we will create a population of random legal positions by simulating games where this system takes it in turns to play random moves for black and white a random variety of times. By repeating this process tens of 1000’s of times, large samples of random positions may be analyzed for fitness.

Below, you may see a function from my Board class, which returns an inventory of moves.

public List<(int[] from, int[] to)> GetAllPotentialMoves(Color currentColour) 
{
var activePieces = ActivePieces.Find(p => p.color == currentColour);
var allLegalMoves = latest 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 actual tricky bit starts. The important thing to any Evolutionary Algorithm is the way you evaluate your heuristic. In my case, only positions where a single solution resulting in a checkmate were considered for a puzzle. After narrowing those results down, heuristic is a measure of how difficult it’s to decide on the proper moves to win the sport. But how can a pc program estimate how difficult it’s for a human to interpret a chess position?

One option is to take a look at the structure of the puzzle. Is the king protected? Are there moves that don’t solve the puzzle, but look good? Can we sacrifice any material? What pieces are we moving? By evaluating many aspects, we will create a measure of difficulty. The difficulty with this approach is it’s really hard to come to a decision create a final rating from so many aspects. Rigid rules also completely ignore biases in human perception. It may be that even subtle changes to a chess position make it much harder for some individuals to select the proper move.

So, how can we get a greater idea of human performance? By utilizing large databases stuffed with real games, machine learning models have been trained to play chess like players of certain levels. Through these models we will get a greater idea how players of various abilities might attempt a puzzle. Can an AI trained on 1200 rated players solve the puzzle? What about 1600, 1900? The good thing about this approach is it delves deeper into the minds of real players. Nonetheless, machine learning models are usually not without their drawbacks. These AIs don’t play like an actual player, they play like an approximation of a player. They’re also trained on real, regular games, meaning they may be unreliable evaluating randomized chess positions.

By combining the machine learning models with complex and detailed rule based evaluation, I created a better of each worlds type scenario. A heuristic that each understands the composition of the puzzle, whilst at the identical time considering how humans might approach it.

Once one of the best puzzles in a population have been found, the subsequent step is to create latest generations. This may be done through many evolution inspired techniques. I selected to make use of crossover and mutation.

Crossover involves randomly merging the features of two leads to the hope you may find yourself with one of the best features of each. We will cross over similar chess positions by going back a lot of moves to a shared origin, then picking legal moves used to achieve each result. Perhaps moving the queen gave one puzzle a extremely good property, and moving the knight made one other puzzle interesting. By combining each of those features we create a good more compelling problem.

Similarly, we will mutate puzzles by backtracking after which going forwards a lot of moves. Depending on the variety of moves you go backwards and forwards it could possibly change the puzzle subtly or massively. An excessive amount of mutation and yow will discover the algorithm never improving, too little and your best result could converge on a single value too quickly.

Essentially the most common issue with Evolutionary Algorithms is converging too fast. Initially, the puzzles I used to be generating stopped improving after only a number of generations. In the actual world, physical boundaries similar to mountains, deserts and seas have prevented populations from crossing over their DNA, allowing genetic diversity to be preserved. Without enough genetic diversity, a population won’t evolve vary far. By running smaller populations of chess puzzles in parallel for just a little while, I gave them respiratory room enough to take care of some diversity and avoid converging too early.

Evolutionary Algorithms will also be very slow. Chess is actually no exception. Running heuristic evaluation on tens of millions of chess positions requires a substantial amount of processing. Generally, the longer you run a chess engine on a position the more accurate it could possibly predict the subsequent best move. By finding the sweet spot in time spent analysing each position, picking out essentially the most promising ones and looking out at them in rather more detail, I could optimise the time an inexpensive amount. Deciding when to stop generating can also be crucial. If a sample has stopped improving for several generations then perhaps it’s best to begin again with a latest random population, as it might be unable to enhance much further. After countless optimisations, my home PC is in a position to generate over 1000 difficult puzzles per day using evolution.

Finally, diagnosing errors may be incredibly difficult. With many programs you may expect certain outputs given certain inputs. With evolution it’s a unique kettle of fish. I spent quite a lot of time scratching my head wondering why my population was converging too quickly. Was it position generation? Was it the evolutionary methods, perhaps the heuristic? It may well be easy to not even notice if some things aren’t working as intended when the expected output of a program cannot be clearly defined.

Nonetheless, issues aside, the facility and potential of this AI technique shines brilliant for all to see. Using just my old PC I’ve been in a position to generate almost 50,000 chess puzzles in 3 months, containing an abundance of extraordinary positions.

The random nature of the algorithm signifies that it creates an incredibly vibrant and diverse set of puzzles. Interesting tactical problems we rarely see in chess similar to queen sacrifices, knight promotions and en passant are easy to search out using evolution, but difficult using databases of real games. Nonetheless, the nonsensical nature of the puzzles makes them less applicable to real world scenarios. Although great fun, an argument might be made that puzzles based on real games are higher for learning common patterns in chess games.

In addition to being incredibly productive, the algorithm can also be exceptionally flexible. Shatranj, lopsided chess boards, it’s easy to increase the EA to work with any derivative of chess. This extendable nature is where the evolutionary technique really excels. You simply can’t do that with databases of games, as they simply don’t exist!

Although a forgotten corner of AI to many, I’ve shown how evolution may be used to create a novel solution to an actual world problem. There’s much unexplored potential with this technology. With generative AI on the rise, I ponder what other funky applications people will find for EAs in the long run…

You may experience the puzzles for yourself on my website, chesspuzzler.com.

Unless otherwise noted, all images are by the creator.