Solve puzzles of shamans in the World of Warcraft genetic algorithm

Hello, habrazhitel!
Not so long ago, another World of Warcraft Legion supplement was released. The first thing I did was to pump the shaman. In the stronghold of the shamans, I wandered over to the Master of Puzzles Luo and saw what you thought — a puzzle.

In front of me was a square of fire and water totems 5 by 5, after you click on the totem, it changes to the opposite, for example, water to fire or fire to water and also changes neighboring totems from above, below, to the left and to the right. It is necessary to make so that all totems become water. After the first click, I realized that I urgently need to write a solution for this cool puzzle.
What came out of it, read under the cut.

The task was as follows:

Given a matrix of dimension N on M, each cell of the matrix contains either 0 or 1 . When the value of the matrix cell changes to the opposite, automatically change to the opposite values ​​on the neighboring cells from the top, bottom, left and right. Find the sequence of cell changes, so that the matrix would consist only of zeros.

The solution to this problem is very standard and boring and I decided to write a genetic algorithm for solving the problem.

UPD: Since misunderstanding is noticed, I emphasize that the meaning is not in solving the problem, but in writing the genetic algorithm for finding a solution

Some theory

To write algorithms, we need to introduce the concept of genes, genotype, fitness functions, mutation, generation, and generation survival.

Genes

The genome will be called the cell value of the matrix, i.e. it's either 1 or 0

Genotype

The genotype is the matrix represented as a string of length L = N x M , which will contain successively combined rows of the matrix, each character of the string is a gene

Example
For matrix

 [ [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0] ] 

The genotype will be the string 0000011111000001111100000 , where L = 25

Fitness function

A fitness function (fitness function) is a function that returns a number from 0 to 1 , the closer the value is to 1 , the better is the individual's ability. The question remains, what is considered the fitness of the individual. For simplicity, we can do with the number of zero genes in the genotype divided by the length of the genotype

 function fitness(genotype) { return genotype.replace(/1/g,'').length / genotype.length; } 

Mutation

The change of a single gene in the genotype of the individual. Since According to the rules of the game, 5 cells of the matrix change (target and neighboring), then one mutation will give 5 new individuals.

 const DIRECTIONS = [ {x: 0, y: 0}, {x: 1, y: 0}, {x:-1, y: 0}, {x: 0, y: 1}, {x: 0, y:-1} ]; function mutate(genotype) { return DIRECTIONS.map( direction => { const nextX = x + direction.x; const nextY = y + direction.y; return genotype.flip(nextX, nextY); } ); } 

Survival

Selection of individuals according to their fitness as a result of which, a limited number of the fittest remain. In our case, we sort all individuals by decrease of the fitness function value and leave the first L x 8 (value obtained experimentally)

 const maxGenerationSize = 400; // 5 * 5 * 8 function surviving(populations) { return populations.sort( (a, b) => { return b.fitness - a.fitness; }).slice(0, maxGenerationSize); } 

Generation

Many individuals left after "Survival." Moreover, the very first generation individual will be the decision if its fitness is equal to one.

Some more theory about optimization

It can be noted that after a mutation, it is very often possible to obtain a previously known genome or a genome obtained by a smaller number of mutations, but with the same or better fitness. Whatever happens, create a hash table of genomes, the key of which is the gene itself, and the value, an array of mutation cells. If this genome has already been encountered and the number of mutation cells does not exceed that already encountered, we create a reproduction from it.

It is also easy to notice that we are changing all over the field either 3 or 5 cells, i.e. the fitness function returns 1 only after the values L - 3 and L - 5 . For them, you can return the values ​​of 0.999 fthness functions to increase their fitness.

Example
For maritsa 5x5 value of fitness function 1 will be in the presence of all 25 zeros in the genome, and they will be preceded only by either 20 zeros or 22

The entire solution search cycle can be represented as the following code.

 while ( generation++ < maxGenerationsCount && populations[0].fitness !== 1 ) { populations = mutating( populations ); populations = surviving( populations ); } 

Armed with a Webpack, React-Redux, and Material-UI in a couple of hours, it’s such a simple web application:

The calculations are performed on the Web Worker side in the breeder.js file in order to take the load off the UI.

• Link to the task in WiKi
• Look at the ready reshny can here
• Sources on GitHub
• All noticed and unnoticed errors here.