Answers.Body: <p>Perhaps it could be due to the lack of inputs? Many videos of Snake AIs that use NN and GA to learn seem to have more than double or triple the amount of inputs you're feeding to your neural network (See <a href="https://www.youtube.com/watch?v=vhiO4WsHA6c" rel="nofollow noreferrer">here</a> and <a href="https://www.youtube.com/watch?v=3bhP7zulFfY" rel="nofollow noreferrer">here</a>). I would recommend that you add more inputs by giving the NN the distance to the snake part and the wall for every direction you're looking in.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-25T04:23:36.663Z
Answers.LastActivityDate: 2020-08-25T04:23:36.663Z
Answers.UserDisplayName: Gamer818
Body: <p>So, i have created Snake game using Pygame and Python. Then i wanted to create an AI with Genetic algorithm and a simple NN to play it. Seems pretty fun, but things aren't working out.</p>
  
  <p>This is my genetic algorithm:</p>
  
  <pre><code>def calculate_fitness(population):
      """Calculate the fitness value for the entire population of the generation."""
      # First we create all_fit, an empty array, at the start. Then we proceed to start the chromosome x and we will
      # calculate his fit_value. Then we will insert, inside the all_fit array, all the fit_values for each chromosome
      # of the population and return the array
      all_fit = []
      for i in range(len(population)):
          fit_value = Fitness().fitness(population[i])
          all_fit.append(fit_value)
      return all_fit
  
  
  def select_best_individuals(population, fitness):
      """Select X number of best parents based on their fitness score."""
      # Create an empty array of the size of number_parents_crossover and the shape of the weights
      # after that we need to create an array with x number of the best parents, where x is NUMBER_PARENTS_CROSSOVER
      # inside config file. Then we search for the fittest parents inside the fitness array created by the
      # calculate_fitness function. Numpy.where return (array([], dtype=int64),) that satisfy the query, so we
      # take only the first element of the array and then it's value (the index inside fitness array). After we have
      # the index of the element we just need to take all the weights of that chromosome and insert them as a new
      # parent. Finally we change the fitness value of the fitness value of that chromosome inside the fitness
      # array in order to have all different parents and not only the fittest
      parents = numpy.empty((config.NUMBER_PARENTS_CROSSOVER, population.shape[1]))
      for parent_num in range(config.NUMBER_PARENTS_CROSSOVER):
          index_fittest = numpy.where(fitness == numpy.max(fitness))
          index_fittest = index_fittest[0][0]
          parents[parent_num, :] = population[index_fittest, :]
          fitness[index_fittest] = -99999
      return parents
  
  
  def crossover(parents, offspring_size):
      """Create a crossover of the best parents."""
      # First we start by creating and empty array with the size equal to offspring_size we want. The type of the
      # array is [ [Index, Weights[]] ]. If the parents size is only 1 than we can't make crossover and we return
      # the parent itself, otherwise we select 2 random parents and then mix their weights based on a probability
      offspring = numpy.empty(offspring_size)
      if parents.shape[0] == 1:
          offspring = parents
      else:
          for offspring_index in range(offspring_size[0]):
              while True:
                  index_parent_1 = random.randint(0, parents.shape[0] - 1)
                  index_parent_2 = random.randint(0, parents.shape[0] - 1)
                  if index_parent_1 != index_parent_2:
                      for weight_index in range(offspring_size[1]):
                          if random.uniform(0, 1) &lt; 0.5:
                              offspring[offspring_index, weight_index] = parents[index_parent_1, weight_index]
                          else:
                              offspring[offspring_index, weight_index] = parents[index_parent_2, weight_index]
                      break
      return offspring
  
  
  def mutation(offspring_crossover):
      """Mutating the offsprings generated from crossover to maintain variation in the population."""
      # We cycle though the offspring_crossover population and we change x random weights, where x is a parameter
      # inside the config file. We select a random index, generate a random value between -1 and 1 and then
      # we sum the original weight with the random_value, so that we have a variation inside the population
      for offspring_index in range(offspring_crossover.shape[0]):
          for _ in range(offspring_crossover.shape[1]):
              if random.uniform(0, 1) == config.MUTATION_PERCENTAGE:
                  index = random.randint(0, offspring_crossover.shape[1] - 1)
                  random_value = numpy.random.choice(numpy.arange(-1, 1, step=0.001), size=1, replace=False)
                  offspring_crossover[offspring_index, index] = offspring_crossover[offspring_index, index] + random_value
      return offspring_crossover
  </code></pre>
  
  <p>My neural network is formed using 7 inputs:</p>
  
  <pre><code>is_left_blocked, is_front_blocked, is_right_blocked, apple_direction_vector_normalized_x,
  snake_direction_vector_normalized_x, apple_direction_vector_normalized_y,snake_direction_vector_normalized_y
  </code></pre>
  
  <p>Basically if you can go left, front, right, direction to the apple and snake direction.
  Then i have an hidden layer with 8 neurons and finally 3 output that indicate left, keep going or right.</p>
  
  <p>The Neural Network forward() is calculate like this:</p>
  
  <pre><code>self.get_weights_from_encoded()
  Z1 = numpy.matmul(self.__W1, self.__input_values.T)
  A1 = numpy.tanh(Z1)
  Z2 = numpy.matmul(self.__W2, A1)
  A2 = self.sigmoid(Z2)
  A2 = self.softmax(A2)
  return A2
  </code></pre>
  
  <p>where self.__W1 and self.__W2 are the weights from input to hidden layer and then the weights from hidden layer to the output. Softmax(A2) return the index of the matrix[1,3] where the value is the biggest, then i use that index to indicate the direction that my neural network choose. </p>
  
  <p>This is the config file that contains the parameters:</p>
  
  <pre><code># GENETIC ALGORITHM
  NUMBER_OF_POPULATION = 500
  NUMBER_OF_GENERATION = 200
  NUMBER_PARENTS_CROSSOVER = 50
  MUTATION_PERCENTAGE = 0.2
  
  # NEURAL NETWORK
  INPUT = 7
  NEURONS_HIDDEN_1 = 8
  OUTPUT = 3
  NUMBER_WEIGHTS = INPUT * NEURONS_HIDDEN_1 + NEURONS_HIDDEN_1 * OUTPUT
  </code></pre>
  
  <p>And this is the main:</p>
  
  <pre><code>for generation in range(config.NUMBER_OF_GENERATION):
  
      snakes_fitness = genetic_algorithm.calculate_fitness(population)
  
      # Selecting the best parents in the population.
      parents = genetic_algorithm.select_best_individuals(population, snakes_fitness)
  
      # Generating next generation using crossover.
      offspring_crossover = genetic_algorithm.crossover(parents,
                                                        offspring_size=(pop_size[0] - parents.shape[0], config.NUMBER_WEIGHTS))
  
      # Adding some variations to the offspring using mutation.
      offspring_mutation = genetic_algorithm.mutation(offspring_crossover)
  
      # Creating the new population based on the parents and offspring.
      population[0:parents.shape[0], :] = parents
      population[parents.shape[0]:, :] = offspring_mutation
  </code></pre>
  
  <p>I have 2 problems:</p>
  
  <p>1) I don't see an improvement over the new generations</p>
  
  <p>2) I'm actually running the game inside the for loop, but waiting for all the snake of a generation to die and repeat with the new one is really time consuming. Isn't there a way to launch all or, atleast, more than 1 instance of the game and keep filling the array with the result?</p>
  
  <p>This is Fitness().fitness(population[i])</p>
  
  <pre><code>def fitness(self, weights):
      game_manager = GameManager(weights)
      self.__score = game_manager.play_game()
      return self.__score
  </code></pre>
  
  <p>This is where it's called inside the for loop</p>
  
  <pre><code>def calculate_fitness(population):
      """Calculate the fitness value for the entire population of the generation."""
      # First we create all_fit, an empty array, at the start. Then we proceed to start the chromosome x and we will
      # calculate his fit_value. Then we will insert, inside the all_fit array, all the fit_values for each chromosome
      # of the population and return the array
      all_fit = []
      for i in range(len(population)):
          fit_value = Fitness().fitness(population[i])
          all_fit.append(fit_value)
      return all_fit
  </code></pre>
  
  <p>This the function that launch the game (GameManager(weights)) and return the score of the snake.</p>
  
  <p>This is my first time on AI so this code could be all a mess, don't worry about pointing out what i did wrong, just please don't say "It's all wrong" because i won't be able to learn otherwise.</p>
  
Tags: <python><genetic-algorithms>
Title: Genetic Algorithm Python Snake not improving
UserDisplayName: Fanto
ThreadText: # Genetic Algorithm Python Snake not improving
  
  (Asked by: username_0 on 2020-04-26)
  
  So, i have created Snake game using Pygame and Python. Then i wanted to create an AI with Genetic algorithm and a simple NN to play it. Seems pretty fun, but things aren't working out.
  
  This is my genetic algorithm:
  
  ```
  def calculate_fitness(population):
      """Calculate the fitness value for the entire population of the generation."""
      # First we create all_fit, an empty array, at the start. Then we proceed to start the chromosome x and we will
      # calculate his fit_value. Then we will insert, inside the all_fit array, all the fit_values for each chromosome
      # of the population and return the array
      all_fit = []
      for i in range(len(population)):
          fit_value = Fitness().fitness(population[i])
          all_fit.append(fit_value)
      return all_fit
  
  def select_best_individuals(population, fitness):
      """Select X number of best parents based on their fitness score."""
      # Create an empty array of the size of number_parents_crossover and the shape of the weights
      # after that we need to create an array with x number of the best parents, where x is NUMBER_PARENTS_CROSSOVER
      # inside config file. Then we search for the fittest parents inside the fitness array created by the
      # calculate_fitness function. Numpy.where return (array([], dtype=int64),) that satisfy the query, so we
      # take only the first element of the array and then it's value (the index inside fitness array). After we have
      # the index of the element we just need to take all the weights of that chromosome and insert them as a new
      # parent. Finally we change the fitness value of the fitness value of that chromosome inside the fitness
      # array in order to have all different parents and not only the fittest
      parents = numpy.empty((config.NUMBER_PARENTS_CROSSOVER, population.shape[1]))
      for parent_num in range(config.NUMBER_PARENTS_CROSSOVER):
          index_fittest = numpy.where(fitness == numpy.max(fitness))
          index_fittest = index_fittest[0][0]
          parents[parent_num, :] = population[index_fittest, :]
          fitness[index_fittest] = -99999
      return parents
  
  def crossover(parents, offspring_size):
      """Create a crossover of the best parents."""
      # First we start by creating and empty array with the size equal to offspring_size we want. The type of the
      # array is [ [Index, Weights[]] ]. If the parents size is only 1 than we can't make crossover and we return
      # the parent itself, otherwise we select 2 random parents and then mix their weights based on a probability
      offspring = numpy.empty(offspring_size)
      if parents.shape[0] == 1:
          offspring = parents
      else:
          for offspring_index in range(offspring_size[0]):
              while True:
                  index_parent_1 = random.randint(0, parents.shape[0] - 1)
                  index_parent_2 = random.randint(0, parents.shape[0] - 1)
                  if index_parent_1 != index_parent_2:
                      for weight_index in range(offspring_size[1]):
                          if random.uniform(0, 1) < 0.5:
                              offspring[offspring_index, weight_index] = parents[index_parent_1, weight_index]
                          else:
                              offspring[offspring_index, weight_index] = parents[index_parent_2, weight_index]
                      break
      return offspring
  
  def mutation(offspring_crossover):
      """Mutating the offsprings generated from crossover to maintain variation in the population."""
      # We cycle though the offspring_crossover population and we change x random weights, where x is a parameter
      # inside the config file. We select a random index, generate a random value between -1 and 1 and then
      # we sum the original weight with the random_value, so that we have a variation inside the population
      for offspring_index in range(offspring_crossover.shape[0]):
          for _ in range(offspring_crossover.shape[1]):
              if random.uniform(0, 1) == config.MUTATION_PERCENTAGE:
                  index = random.randint(0, offspring_crossover.shape[1] - 1)
                  random_value = numpy.random.choice(numpy.arange(-1, 1, step=0.001), size=1, replace=False)
                  offspring_crossover[offspring_index, index] = offspring_crossover[offspring_index, index] + random_value
      return offspring_crossover
  
  ```
  
  My neural network is formed using 7 inputs:
  
  ```
  is_left_blocked, is_front_blocked, is_right_blocked, apple_direction_vector_normalized_x,
  snake_direction_vector_normalized_x, apple_direction_vector_normalized_y,snake_direction_vector_normalized_y
  
  ```
  
  Basically if you can go left, front, right, direction to the apple and snake direction.
  Then i have an hidden layer with 8 neurons and finally 3 output that indicate left, keep going or right.
  
  The Neural Network forward() is calculate like this:
  
  ```
  self.get_weights_from_encoded()
  Z1 = numpy.matmul(self.__W1, self.__input_values.T)
  A1 = numpy.tanh(Z1)
  Z2 = numpy.matmul(self.__W2, A1)
  A2 = self.sigmoid(Z2)
  A2 = self.softmax(A2)
  return A2
  
  ```
  
  where self.\_\_W1 and self.\_\_W2 are the weights from input to hidden layer and then the weights from hidden layer to the output. Softmax(A2) return the index of the matrix[1,3] where the value is the biggest, then i use that index to indicate the direction that my neural network choose.
  
  This is the config file that contains the parameters:
  
  ```
  # GENETIC ALGORITHM
  NUMBER_OF_POPULATION = 500
  NUMBER_OF_GENERATION = 200
  NUMBER_PARENTS_CROSSOVER = 50
  MUTATION_PERCENTAGE = 0.2
  
  # NEURAL NETWORK
  INPUT = 7
  NEURONS_HIDDEN_1 = 8
  OUTPUT = 3
  NUMBER_WEIGHTS = INPUT * NEURONS_HIDDEN_1 + NEURONS_HIDDEN_1 * OUTPUT
  
  ```
  
  And this is the main:
  
  ```
  for generation in range(config.NUMBER_OF_GENERATION):
  
      snakes_fitness = genetic_algorithm.calculate_fitness(population)
  
      # Selecting the best parents in the population.
      parents = genetic_algorithm.select_best_individuals(population, snakes_fitness)
  
      # Generating next generation using crossover.
      offspring_crossover = genetic_algorithm.crossover(parents,
                                                        offspring_size=(pop_size[0] - parents.shape[0], config.NUMBER_WEIGHTS))
  
      # Adding some variations to the offspring using mutation.
      offspring_mutation = genetic_algorithm.mutation(offspring_crossover)
  
      # Creating the new population based on the parents and offspring.
      population[0:parents.shape[0], :] = parents
      population[parents.shape[0]:, :] = offspring_mutation
  
  ```
  
  I have 2 problems:
  
  1) I don't see an improvement over the new generations
  
  2) I'm actually running the game inside the for loop, but waiting for all the snake of a generation to die and repeat with the new one is really time consuming. Isn't there a way to launch all or, atleast, more than 1 instance of the game and keep filling the array with the result?
  
  This is Fitness().fitness(population[i])
  
  ```
  def fitness(self, weights):
      game_manager = GameManager(weights)
      self.__score = game_manager.play_game()
      return self.__score
  
  ```
  
  This is where it's called inside the for loop
  
  ```
  def calculate_fitness(population):
      """Calculate the fitness value for the entire population of the generation."""
      # First we create all_fit, an empty array, at the start. Then we proceed to start the chromosome x and we will
      # calculate his fit_value. Then we will insert, inside the all_fit array, all the fit_values for each chromosome
      # of the population and return the array
      all_fit = []
      for i in range(len(population)):
          fit_value = Fitness().fitness(population[i])
          all_fit.append(fit_value)
      return all_fit
  
  ```
  
  This the function that launch the game (GameManager(weights)) and return the score of the snake.
  
  This is my first time on AI so this code could be all a mess, don't worry about pointing out what i did wrong, just please don't say "It's all wrong" because i won't be able to learn otherwise.
  
  **Tags:** python, genetic-algorithms
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-08-25. Score: 2 | Accepted answer
  
  Perhaps it could be due to the lack of inputs? Many videos of Snake AIs that use NN and GA to learn seem to have more than double or triple the amount of inputs you're feeding to your neural network (See [here](https://www.youtube.com/watch?v=vhiO4WsHA6c) and [here](https://www.youtube.com/watch?v=3bhP7zulFfY)). I would recommend that you add more inputs by giving the NN the distance to the snake part and the wall for every direction you're looking in.
  
  
  ---
  
  