DATA STRUCTURES AND ALGORITHMS

SOLVING A BATTLESHIP BOARD GAME AS AN OPTIMIZATION PROBLEM

A genetic algorithm is a prime example of technology imitating nature to solve complex problems, in this case, by adopting the concept of natural selection in an evolutionary algorithm. Genetic algorithms, introduced in 1960 by John Holland, extend Alan Turing’s concept of a “learning machine” and are best-suited for solving optimization problems such as the traveling salesman.

To intuitively understand the practical implementation and fundamental requirements for employing genetic algorithms, we can set up a toy problem and solve the board of the classic guessing game, Battleship, first released by Milton Bradley in 1967. But rather than calling a sequence of individual shots, let’s ask our genetic algorithm to make a series of guesses of the entire board.

Continue reading the full story curated by Towards Data Science, a Medium publication...

• Project Features
• Source Code
• Output Results
• Contribute

ARTIFICIAL INTELLIGENCE | MACHINE LEARNING | OPTIMIZATION | EVOLUTIONARY ALGORITHMS | TOY PROBLEMS

• Random Board Generator for Battleship Game
  Graphical and binary representation of a Battleship board game with 5 ships occupying 17 squares
• Implementation of Genetic Algorithm
  Iterative solver that generates candidate solutions of an entire board of a random Battleship game, which converge to the genetic solution
• Genetic Selector: Elitism
  The fittest chromosomes from the former generation that are selected to be parents of all of the chromosomes in a new generation.
• Genetic Operator: Crossover
  Two chromosomes can be spliced at a random crossover gene and recombined to create two children, sharing gene chains from both parents.
• Genetic Operator: Mutation
  Random genes of one chromosome can be inverted with bit flips to create a single child that exhibits a small genetic variation from its parent.

PYTHON | NUMPY | PANDAS

The Random Board Generator

1. Position the head of the ship with a random two-dimensional tuple
2. Orient the heading of the ship with a random cardinal direction
3. Locate the tail of the ship based on its head position, direction and length
4. Check that the tail of the ship remains within the boundaries of the board
5. Check that the ship does not overlap with any previously positioned ships
6. Repeat the process if the ship fails either of the two assertion tests

The Battleship Module

• Random board generator for a new Battleship game
• Genetic representation of the board solution as binary representation
• Fitness function evaluator of a candidate solution based on accuracy

The Genetic Algorithm Module

• Random solution generator for first generation
• Assignment of elite chromosomes within a generation
• Selection of elite parents to populate a new generation with elite rate
• Creation of mutant descendents with bit flip rate
• Creation of splice pair descendents with number of splice pairs
• Filling of generation vacancies with random descendents
• Creation of descendent generations with specified population mix and termination criterion
• Solution driver to create generations until convergence to the genetic solution

SEABORN | MATPLOTLIB

Genetic Algorithm Demo

1. Set up the board with random board generator
2. Generate candidate solution for the entire board
3. Determine fitness of candidate solution based on accuracy
4. Create descendent generations until convergence to the genetic solution
5. Describe fitness statistics of generations to inspect algorithm behavior
6. Solve 1,000 random board games to assess performance of model parameters of genetic algorithm

Random Chromosome

• 51 Occupied Squares (Solution: 1, Candidate: Red)
• 49 Unoccupied Squares (Solution: 0, Candidate: Blue)

Accuracy Rate of Random Chromosome

• 52% candidate accuracy
• 52 Matches (Green)
• 48 Mismatches (Red)

Fitness of Generation 1

• 10 Random chromosomes
• 2 top performers are 57% accurate
• Median fitness of generation is 52.5%

Fitness of Generation 2

• 10 total chromosomes
• 2 Elitism chromosomes (20% elite rate)
• 2 Splice Pair chromosomes (20% crossover rate)
• 6 Mutation chromosomes (60% mutation rate and 1% bit flip rate)
• 2 top performers improve fitness to be 60% and 58% accurate

Fitness of Generation 155

• 155 generations with 10 chromosomes per generation
• 1 Mutation chromosome converges to genetic solution

Fitness Distribution Statistics for Generations 1 to 10

• Natural selection gradually improves population fitness
• Dispersion is highest in the first random generation

Fitness Distribution Statistics for Generations 146 to 155

• All generations are extremely fit with least fit chromosome having 95% accuracy
• Improved fitness is most likely to occur through mutation of a single gene
• High mutation rates and low bit flip rates give latter generations better chance to converge

Convergence of the Gene Pool Towards the Optimal Solution Over 155 Generations

• First random generation will be 50% accurate
• Elitism guarantees that generational peak performance is monotonically increasing
• Crossover promotes substantial improvements to fitness in initial generations
• Mutation achieves convergence with genetic solution in latter generations

Performance Metric of a Genetic Algorithm with Fixed Model Parameters Over 1,000 Samples

• Genetic algoritm performance is influenced by nature of Battleship problem and the model parameters
• Performance can be measured by sampling and solving 1,000 random Battleship board games
• Model parameters can be tuned by using the performance distribution as an objective function

Contact

• Email
• LinkedIn
• Medium
• Scholar

License

• MIT License