1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 and here). 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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.