Home Artificial Intelligence Evolving Chess Puzzles Population Generation Survival of the Fittest The Next Generation So… What’s the Catch? Results To Conclude

Evolving Chess Puzzles Population Generation Survival of the Fittest The Next Generation So… What’s the Catch? Results To Conclude

0
Evolving Chess Puzzles
Population Generation
Survival of the Fittest
The Next Generation
So… What’s the Catch?
Results
To Conclude

An exploration of Evolutionary AI

Towards Data Science
A chess puzzle, generated using the speculation of evolution. Checkmate in 2 moves for white…

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 an alternative of describing the steps required to succeed in a goal, EAs describe what the goal looks like.

In this text I’ll explore how we are able to utilize this incredible 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 will 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 at last 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 more likely to pass on their traits to the subsequent generation. After many generations, sometimes a whole bunch of hundreds, the population converges on an optimal result. So how can we apply this to chess?

With chess, we are able to 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 hundreds of times, large samples of random positions will be analyzed for fitness.

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

public List<(int[] from, int[] to)> GetAllPotentialMoves(Color currentColour) 
{
var activePieces = ActivePieces.Find(p => p.color == currentColour);
var allLegalMoves = recent 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?

A puzzle generated using a heuristic favoring knights on the board. Checkmate in 2 moves.

One option is to have a look at the structure of the puzzle. Is the king secure? 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 are able to create a measure of difficulty. The problem with this approach is it’s really hard to choose the way to create a final rating from so many aspects. Rigid rules also completely ignore biases in human perception. It could 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 crammed with real games, machine learning models have been trained to play chess like players of certain levels. Through these models we are able to 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. Nevertheless, machine learning models aren’t 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 could 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 the very best puzzles in a population have been found, the subsequent step is to create recent generations. This will 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 the very best features of each. We will cross over similar chess positions by going back a variety of moves to a shared origin, then picking legal moves used to succeed in 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 an excellent more compelling problem.

Similarly, we are able to mutate puzzles by backtracking after which going forwards a variety of moves. Depending on the variety of moves you go backwards and forwards it could 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.

Probably 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 resembling 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 a little bit while, I gave them respiratory room enough to take care of some diversity and avoid converging too early.

Evolutionary Algorithms can be very slow. Chess is actually no exception. Running heuristic evaluation on thousands and thousands 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 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 far more detail, I could optimise the time an affordable amount. Deciding when to stop generating can be crucial. If a sample has stopped improving for several generations then perhaps it’s best to start out again with a brand new random population, as it could 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 will be incredibly difficult. With many programs you may expect certain outputs given certain inputs. With evolution it’s a distinct kettle of fish. I spent numerous 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 be easy to not even notice if some things aren’t working as intended when the expected output of a program can’t be clearly defined.

Nevertheless, issues aside, the ability 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 implies that it creates an incredibly vibrant and diverse set of puzzles. Interesting tactical problems we rarely see in chess resembling queen sacrifices, knight promotions and en passant are easy to search out using evolution, but difficult using databases of real games. Nevertheless, 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 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 only can’t do that with databases of games, as they simply don’t exist!

A Shatranj puzzle generated by the algorithm. Are you able to checkmate the white king in 2 moves?

Although a forgotten corner of AI to many, I’ve shown how evolution will 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 possibly can experience the puzzles for yourself on my website, chesspuzzler.com.

Unless otherwise noted, all images are by the writer.

LEAVE A REPLY

Please enter your comment!
Please enter your name here