The Chess Horse Journey is a problem that has been studied for centuries by both chess players and mathematicians. A route of the horse is proposed, with its characteristic jump, in such a way that it runs through all the squares on the board (64 squares, 8 × 8) touching each one only once.
The first data on this problem was found in an Arabic manuscript from the year 840 (Murray, 1913), where two routes were detailed. The first mathematical analysis was presented by Leonhard Euler in Berlin (1759). Other known mathematicians who dealt with it were Taylor, de Moivre and Lagrange.
Closer to our time, McKay and Mordecki used powerful mainframes looking for the most possible routes on an 8 × 8 board. McKay calculated the total number of closed routes (when the horse completes the circuit, the next jump takes him to the starting square) in
13,267,364,410,532, while Mordecki found
1,305 × 10 35 open routes.
As for search systems, they range from purely heuristic systems (Warnsdorff 1823), depth first search / backtracking, neural networks, genetic algorithms, ant colony algorithms, etc.
For the resolution of this work, a genetic algorithm based on the one developed by
Chu-Beasley
Genetic algorithms
Genetic Algorithms (AGs) are methods used to solve search and optimization problems. They are based on the evolution of populations in nature, according to the principles of natural selection and survival of the fittest, postulated by Charles Darwin (1859)
By mimicking these adaptive processes, AGs are able to generate solutions for real-life problems. By adequately coding the initial GA population and correctly implementing evolutionary methods, optimal solutions can be reached.
The basic principles of GAs were established by Holland in 1975, but that technique only became popular in the mid-1980s, especially through the work of Goldberg (1989).
In nature, individuals compete for survival resources as well as for reproduction. Those who have the best conditions to survive and attract their partners are the ones who will have the best chance of generating descendants. On the contrary, the least gifted will have little chance of reproducing. The characteristics of the best adapted are inherited by their children, who receive a combination of the best genes from their parents and thus evolve, achieving greater adaptation to the environment in which they live.
AGs work similarly to the natural system. They have a population of individuals where each is the potential solution to a given problem. Each of these individuals will have an aptitude or adaptation value related to how close or far they are from achieving such a solution.
Analogously with nature, these individuals will be able to interbreed and generate descendants, who will receive the best of their ancestors and thus, as generations go by, they will converge towards the optimal solution to the problem.
A typical GA employs simplified notions of selection, crossover, mutation, and survival of the fittest so that with relatively little knowledge of the methods of solving a problem, you can also reach a solution.
In fields where specific techniques exist for particular solutions, they will always work better than an AG. The idea of using these algorithms is to search in fields without a delimited solution, or if that solution exists, it can be improved by combining it with the use of the AG.
AGs are used in a wide variety of areas, such as: numerical and combinatorial optimization, machine learning, automatic programming, economics, immune systems, ecology, evolution and learning, social systems, etc.
Structure and Functioning of a Genetic Algorithm
A Simple AG (like the one created by Holland and one of the most used) is made up of a population of individuals, also called chromosomes. Each chromosome represents a possible solution to the proposed problem and is made up of a series of values, which can be {0,1}, integers, reals, etc. These values correspond to each of the genes that make up the chromosome. A possible graphic representation is as follows:
The AG also has genetic operators, who carry out the selection, crossing and mutation processes. Since these three operators are the most common and basic, some specialized AGs incorporate operators of feasibility improvement, optimality improvement, etc.
Chu-Beasley Genetic Algorithm
As stated above, the Chu-Beasley GA was used for this work. The most important differences with simple AGs are:
- There cannot be equal chromosomes in the population. In simple GAs, all or almost the entire population is replaced in each generation. In Chu-Beasley only one individual is replaced, provided that the new one has the desired characteristics of diversity, feasibility, etc. It incorporates an optimality improvement operator.
Adaptation of the GA to the Chess Horse Problem
Depending on the square in which it is located, the horse can have from two to eight legal moves, which can be coded in various ways. In this work, an encoding with integers was solved:
Thus, a partial horse run can be represented with an integer strip similar to this:
4 - 6 - 0 - 0 - 2 - 4…
If we take a starting point like e4 (center of the board) and represent that path in algebraic notation, we would have:
(e4) - f6 - h5 - g3 - f1 - d2 - e4
Note that the last movement takes us to a previously visited space (e4), making this route illegal. Therefore, we could say that this route has a valid length of five jumps. That number of jumps is what we call the individual's fitness function. For this problem, a fitness function of 63 legal jumps is a valid solution. Returning to the similarity with nature, an individual or chromosome is more or less apt depending on whether the number of its fitness function is higher or lower. The greater the aptitude function, the closer the problem will be to solving: completing the horse's journey around the chessboard.
Implementation of the Genetic Algorithm
It was decided to create an initial population of 64 individuals or chromosomes (subsequent tests confirmed that it is the most appropriate number) Each of the genes on these chromosomes was completed with a random number between 0 and 7. The only initial restriction that was taken was that the jump from an x square did not take the horse off the board.
With the initial population created, a cycle or generation begins, which can be simplified as follows:
- Progenitor Selection Progenitor Crossing and Generation of a Child Mutation of the Child Improvement of Adaptability of the Child Incorporation (Possible) of the Child in the Population
Selection of Parents
There are several methods to select the parents that will generate a descendant of the population. The most used are:
- Elite Roulette or Monte Carlo Tournament Ranking
In this work, the selections for Torneo, Elitista and Montecarlo were experimented, being the latter the one that produced the best results, as will be seen later.
Selection by Tournament
Two pairs of Candidate Progenitors (chromosomes) are chosen at random from the population. From each pair, the chromosome that has the best fitness function is chosen, and the cross is produced from the two chosen.
Elitist Selection
The two best chromosomes are always taken from the population and a cross occurs between them to generate the child.
Monte Carlo or Roulette Selection
With this method, the probability that an individual has to reproduce is proportional to the difference between his aptitude and that of his competitors. This can be represented as a roulette game where each individual gets a section or part of the roulette, but the fittest get larger sections than the least fit. Then the roulette is spun (a number is chosen at random), and each time the individual is chosen who has the section in which the roulette stops.
By running the roulette twice, the two parents are selected to cross.
Parent Crossing
A gene crossover occurs with the two selected chromosomes, of which two children will be generated. Only the fittest of these children may enter the population.
Just as there are various selection methods, it also occurs with crossing. In this work, the crossing operators by one point and by two points were tested, resulting in the crossing with one point being the most successful. Its implementation is as follows:
Once the two parents have been chosen, their chromosomes are cut at a randomly selected point. With this, two different segments are generated in each chromosome: head and tail. Then the genes of the tails are exchanged between each individual and in this way two children are created that inherit characteristics from both parents. Finally, only the child with the best aptitude function will have possibilities of entering the population.
Mutation of the Son
The son's mutation causes some of his genes, usually only one, to vary their value randomly. In this way, the behavior that occurs in nature is imitated, since when the offspring are generated, some type of error usually occurs, usually without major significance, in the passage of the genetic load from parents to children. Normally the probability of mutation is very low, less than 1%. However, the tests in this work had better results with a mutation close to 85%.
The most used genetic mutation operators are the random replacement and the swapping of two genes of the chromosome.
In the present work, there is the possibility that either of the two operators could be applied in a mutation.
Improvement of Child Adaptability
This point is more than important in the AG. The tests carried out by various authors (and also in the present work), with simple GAs, failed in the search for valid routes for the chess horse. In order to improve the functioning of the AGs, various methods were implemented that partially specialize the process. This idea of adaptability was explored by Whitley (1994)
Gordon and Slocum (2004) introduced the repair technique, which will be explained below. Another specialization was that of Al-Gharaibeh, Qqwagneh, and Al-zahawi (2007), who improved offspring adaptability through heuristics.
Gordon and Slocum's idea was as follows: for each chromosome in the population, at the point where a jump is invalid (that is, it takes the horse off the board or to a square already visited) a repair is applied. This move is examined and an attempt is made to replace it with another valid move that allows the journey to continue. If there is no valid jump, evaluation of that chromosome is terminated. In case there is a valid jump, the invalid gene is modified by that jump and it is passed to the gene that follows to the right. This is continued until a square reappears with no possible jumps or the solution of the horse's path is reached. No heuristics or backtracking are applied, as with other techniques.
In the example presented above, the evaluation of the chromosome ended when the horse jumped back to box e4. That is, the gene chain:
4 - 6 - 0 - 0 - 2 - 4…
(e4) - f6 - h5 - g3 - f1 - d2 - e4 where the last value (4) is invalid.
The repair process tries to find a correct value for that gene, let's say the value 7, which would take us off the board. Then we search for another value, for example 3, which would take us to c4, which is a box not yet visited. Then the gene chain would be left
4 - 6 - 0 - 0 - 2 - 3…
(e4) - f6 - h5 - g3 - f1 - d2 - c4
and we would proceed in the same way with the next gene to the right of the chain.
The difference between the present work and that of Gordon and Slocum is that they apply reparation to the entire population, whereas in our Chu-Beasley AG we work only on the newly created son.
Incorporation of the Son into the Population
Once the child is obtained and improved, his aptitude function is calculated, that is, how many valid jumps does his gene chain have. This function is compared with each of the members of the current population. If the fitness function is better than that of the worst member of the population, this individual is eliminated and is replaced by the current child. Always respecting diversity: that the child is not equal to any of the members present in the population.
If a chromosome with the same genes as the current child already existed in the population, or if this child was no better than the worst of the individuals, then it is discarded and it is assumed that there was no offspring in this generation.
Results obtained
For the work, the C # language was used together with the A-Forge.Net framework, an excellent free and open source product, oriented to Artificial Intelligence and that allows speeding up development times.
We attempted to carry out a testing process similar to the previous investigations, but since Chu-Beasley is a different AG, the same parameters cannot be used. Finally, an initial population of 64 chromosomes was created and 1,000,000 generations were made for each square on the board. The process was repeated five times for each box, in order to obtain averages comparable to the other proposals. The results can be seen in the following table:
The three selection methods allowed finding, at least once, a trip in the first generation. This is thanks to the repair mechanism.
It is noteworthy that while Gordon and Slocum's AG found the highest number of runs in an individual square (642 vs. 529), our AG recognized a higher average in almost every square on the board.
On the other hand, there were no tests that gave a negative result, that is, the GA always found valid routes in each test.
Travel averages in five tests.
References:
- Murray HJR (1913) History of Chess BD McKay, “Knight's tours of an 8 × 8 chessboard,” Ph.D. dissertation, Department of Computer Science, Australian National University, 1997. Mordecki, “On the number of knight's tours,” in Prepublicaciones de Matematica de la Universidad de la Republica, Uruguay 2001/57, 2001.BEASLEY, JE E CHU, PC A Genetic Algorithm for the Generalized Assignment Problem. Computers Operations Research, 24 (1), pp 17-23, 1997. Holland, J., Adaptation in Natural and Artificial Systems, 1st ed., Univ. Of Michigan, 1975. 2nd ed. 1992 by MIT Press. Goldberg, D., Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989. Whitley, D., Gordon, VS, and Mathias, K., "Lamarckian Evolution, the Baldwin Effect and Function Optimization," Parallel Prob. Solving from Nature 3, Israel, pp 6-15, 1994
- Gordon VS and Slocum TJ (2004) The Knight's Tour - Evolutionary vs. Depth-First Search. In proceedings of the Congress of Evolutionary Computation 2004 (CEC'04), Portland, Oregon, pp. 1435-1440
- Al-Gharaibeh, Z. Qawagneh, and H. Al-zahawi, “Genetic algorithms with heuristic - Knight's tour problem,” in Proc. of International Conference on Genetic and Evolutionary Methods, 2007, pp. 177-81.A-Forge.Net
