« Back
in AI Algorithms Scala read.

Solving A 2D Maze Game Using a Genetic Algorithm and A* Search - Part 2.

Part 2 focuses on solving the simple maze in this earlier post. Just as a recap though the maze looks like this:

# = Wall
P = Player  
F = Finish  
  = Floor Tile
# # # # # # # # # # # # # # # 
#                           # 
#   # # # #   #   # # #     # 
#   # # # #   #   # # #     # 
#   # # # # # #   #   #     #
# P # # # #       #   #     #
#   # # # # # # # #   # #   #
#   # # #             # #   #
#           # # # #     # F #
# # # # # # # # # # # # # # #

Solving it might not be the right word as a genetic algorithm is more of an optimization algorithm. Optimization implies that we can find a "solution" that is good enough but might not necessarily be the best way. It's good to use when there are just way too many variables to test all the different combinations exhaustively.

A good way to quickly visualize this is like this function here where y=f(x).
local vs global maximum We can use the computer to cycle through many combinations of f(x) using a genetic algorithm and see if we can get anything good enough. What is good enough? That is very much based on the subject matter and context of whatever it is you're trying to solve. If you kind of already know a little bit about GA's then it's the fitness function which we'll get to in a bit for the maze. The difference between a GA and just brute forcing the inputs is the inspiration that a GA takes from nature (Darwin's theory of evolution) to converge onto a more 'fit' solution but at the same time have mutations in the genes to allow for a bit of diversity and other possibilities.

Just in case you didn't read up on GA's yet I'll take this snippet from Wikipedia for you of the methodology of a GA:

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.[6]

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

a genetic representation of the solution domain,

a fitness function to evaluate the solution domain.

GA Components

GA code typically has the following functions:

  1. An initial population. Usually randomized and I usually go with a large amount for variety. Having a smaller population might make computing a little bit longer.
  2. A fitness function. The fitness function determines how "fit" or how close it is to the desired solution.
  3. Selection. We want to select only the fittest members of the population.
  4. Crossover. We have the members "mate" and produce offspring that have similar genes as the parent members.
  5. Mutation. Some of the genes have a random chance of mutating when producing offspring. Mutation plays a pretty important part of the GA. If there is no mutation then the solution will kind of all end up being the same with no chance of breaking free for other potential solutions.

GA Code

I'll put the GA code into an object which we can execute in our Main program. If you recall previously, the game methods are also in a separate object which we can call. The following functions sit inside this:

object GA {  
  val MOVE_LIMIT = 30
  val POPULATION_SIZE = 200000
  val MUTATION_CHANCE=0.5
  val randomizer = scala.util.Random
}

The chromosome or encoding of our problem into genes is a list of moves. So a member of the population is an array of moves.

  • 0 = no move,
  • 1 = up,
  • 2 = down,
  • 3 = left,
  • 4 = right

To solve this puzzle we put a MOVE_LIMIT of 30 moves as a constraint and we start with a population of 200,000 members. There is a 50% chance that when an offspring is produced, there is a mutation just to get things moving. To simulate things more realistically that mutation number should actually be much smaller.

The Initial Population

  val population = Array.fill(POPULATION_SIZE, MOVE_LIMIT) {
    randomizer.nextInt(5)
  }

This fills an Array size 200,000 of Array[30] moves. randomizer.nextInt(5) will produce a random number between 0-4 inclusively which is our moves list into all 30 slots. Pretty quick for a one liner.

Fitness Function

Probably the most important bit of a GA next to figuring out how to encode the population's genes. We will use this function later to determine when to actually stop the code from running. Once we've found a good enough solution. I'll determine in a bit what is good enough. Since the moves are on a Cartesian plane, we can simply use the Manhattan distance as our fitness function.

d=|x2-x1| + |y2-y1|

Additionally, if any of the moves is walking into a wall, we impose a penalty on the score. The lower the score, the closer we are to the finish F. So a penalty would actually add to the score.

  def fitness(chromosome: Array[Int]): Int = {
    chromosome.foreach(move =>
      move match {
        case 0 => 0
        case 1 => Maze.movePlayerUp()
        case 2 => Maze.movePlayerDown()
        case 3 => Maze.movePlayerLeft()
        case 4 => Maze.movePlayerRight()
      })

    // fitness = | (x2-x1) | + | (y2-y1) | + accumulated penalties
    val score =  Math.abs((Maze.finishPosition._1 - Maze.playerCurrentPosition._1)) + Math.abs((Maze.finishPosition._2 - Maze.playerCurrentPosition._2)) + Maze.penalties

    Maze.resetPlayer()
    score
  }

  def fittestScore(population:Array[Array[Int]]):Int={
    val fitness=population.map(c=>GA.fitness(c))
    val sortedFitness=fitness.sorted
    sortedFitness.head
  }

I've also included an additional function in there to get the fittest member of the population any time.

Crossover

  def crossOver(population: Array[Array[Int]]): Array[Array[Int]] = {

    val newPopulation = mutable.ArrayBuilder.make[Array[Int]]

    for (i <- 0 to POPULATION_SIZE -1) {
      val firstParent = population(randomizer.nextInt(population.length))
      val secondParent = population(randomizer.nextInt(population.length))
      val crossOverPoint=randomizer.nextInt(MOVE_LIMIT)

      val offSpring = mutate(Array.concat(firstParent.slice(0,crossOverPoint),secondParent.slice(crossOverPoint,secondParent.length)))

      newPopulation+=offSpring
    }

    newPopulation.result()
  }

There's one ugly line there that might not make much sense. Let's go through this step by step:

  • Pass in a population which is a selection of the fittest. This amount is smaller than the population size because they will produce offspring that will fill up the population pool again.
  • Select 2 parents from the passed in population at random and yes there is a possibility that the same member might be selected twice. I'm going to allow that :D
  • Determine the index in the chromosome (index of the array) where we'd like to swap over
  • Swap the elements from Parent 1 and Parent 2 at the index
  • Mutate a random gene in the chromosome when we produce the new offspring
  • Return the new population

Mutation

  def mutate(chromosome:Array[Int]):Array[Int]={
    if (MUTATION_CHANCE > Math.random()){
      chromosome(randomizer.nextInt(chromosome.length))=randomizer.nextInt(5)
    }
    chromosome
  }

Math.random() produces a number between 0-1 and our MUTATION_CHANCE is 0.5. So roughly 50% of the time we should have a mutation occurring. When that happens, a random element of the Array[30] gets a random move between 0-4.

Searching for a Solution

Now we need a method that runs all the functions of our GA to produce a population that solves our problem. Now we need to determine what kind of solution is good enough.
I would say that if the Player P is 2 tiles away from F that is good enough.

  def searchOptimalMoves(population: Array[Array[Int]]): Array[Array[Int]] = {
    def searchOptimalMovesHelper(population: Array[Array[Int]], mostFitScore: Int): Array[Array[Int]] = {
      if (mostFitScore <= 2)
      {
        population
      }
      else {
        val fitness = population.map(c => (GA.fitness(c), c))
        val sorted = fitness.sortBy { case (score, moves) => score }
        val halfMostFit = sorted.slice(0, sorted.length / 2)
        val newPopulation = crossOver(halfMostFit.map(_._2))
        searchOptimalMovesHelper(newPopulation,fittestScore(newPopulation))
      }
    }
    searchOptimalMovesHelper(population, 999)
  }

This is a tail recursive call in Scala. The main program will run searchOptimalMoves and inside that function, it will run the helper. The last statement is always the calling statement of the helper thus the recursion. Since there's nothing else to do or keep track of, memory is never increasing. We kick start the function with an initial fitness value of 999, just an arbitrarily large value.

This method also has the definition of when to stop which is our good enough scenario:
if (mostFitScore <= 2)

The selection process itself is simply choosing 50% of the most fit in the population. In order to do that we need to sort the population by their fitness scores first. This was done using tuples (score, moves).

Sure, we could wait until we find the absolute optimal solution by changing the good enough function to find a fitness score of 0. But that will take a really long time to run.

Note though that I made this maze have a bottom route which can get close to the finish but there is a wall in the way. It's very possible that by using this distance function we could go totally the wrong way but still satisfy the condition. The bottom route of the maze would be the local optimum.

Running the GA

object GameRunner {  
  def main(args: Array[String]) {
    println("Started Game Runner")

    val x = GA.searchOptimalMoves(GA.population)

    println("Final Result")

    val finalFitness = x.map(c => (GA.fitness(c), c))
      .sortBy { case (score, moves) => score }

    println(s"Top Score: ${finalFitness.head._1}")
    val topScorer=finalFitness.head._2.foreach(move=>
      move match {
        case 0 => 0
        case 1 => Maze.movePlayerUp()
        case 2 => Maze.movePlayerDown()
        case 3 => Maze.movePlayerLeft()
        case 4 => Maze.movePlayerRight()
      }
    )
    Maze.display()
  }
}

Genetic Algorithm 2d Maze final result

Looks like this time it decided to go down.

Using a 2d maze was was instead of the typical hello world for GA's. It also gives me the opportunity to reuse the same code for the next part which is standard in games for path finding.

Tune in next time for part 3 - A* Search.

comments powered by Disqus