I recently started learning AI and i watched this video of Code Bullet, presenting a very simple genetic algorithm of a simple game where dots need to reach to a goal. I wanted to recreate this game in python using pygame. Since it didn't work at all, I tried redesigning it a bit.
Here is the code:
import pygame as pg
from DotGame.DotGameFunctions import *
import random as r
import time
pg.init()
WIN_WIDTH = 500
WIN_HEIGHT = 500
win = pg.display.set_mode((WIN_WIDTH, WIN_HEIGHT))
pg.display.set_caption('DotGame')
SPAWN = Vector2(WIN_WIDTH / 2, WIN_HEIGHT - 40)
GOAL = Vector2(WIN_WIDTH / 2, 10)
class Dot:
def __init__(self, pos: Vector2):
self.pos = pos
self.dead = False
self.reachedGoal = False
self.is_best = False
self.fitness = 0
self.brain = Brain(1000)
self.vel = Vector2()
def move(self):
if self.brain.step < len(self.brain.directions):
self.vel = self.brain.directions[self.brain.step]
self.brain.step += 1
else:
self.dead = True
self.pos = self.pos + self.vel
def update(self):
if not self.dead and not self.reachedGoal:
self.move()
if self.pos.x < 5 or self.pos.y < 5 or self.pos.x > WIN_WIDTH - 5 or self.pos.y > WIN_HEIGHT - 5:
self.dead = True
elif dis(self.pos.x, self.pos.y, GOAL.x, GOAL.y) < 5:
self.reachedGoal = True
if self.is_best:
color = (0, 255, 0)
width = 7
else:
color = (0, 0, 0)
width = 5
if self.fitness > .005:
color = (0, 0, 255)
width = 7
pg.draw.circle(win, color, tuple(self.pos), width)
def calculate_fitness(self):
if self.reachedGoal:
self.fitness = 1 / 16 + 10000 / self.brain.step
else:
distance_to_goal = dis(self.pos.x, self.pos.y, GOAL.x, GOAL.y)
self.fitness = 1 / distance_to_goal
def make_baby(self):
baby = Dot(SPAWN)
baby.brain = self.brain.clone()
return baby
class Goal:
def __init__(self):
self.pos = GOAL
def update(self):
pg.draw.circle(win, (255, 0, 0), tuple(self.pos), 10)
class Brain:
def __init__(self, size):
self.size = size
self.step = 0
self.directions = []
self.randomize()
self.mutationRate = 1
def randomize(self):
self.directions = []
for i in range(self.size):
self.directions.append(Vector2.from_angle(r.random() * 2 * math.pi) * 4)
def clone(self):
clone = Brain(len(self.directions))
clone.directions = self.directions
return clone
def mutate(self):
for i in range(len(self.directions) - 1):
rand = r.random()
if rand < self.mutationRate:
self.directions[i] = Vector2.from_angle(r.random() * 2 * math.pi) * 4
class Population:
def __init__(self, size):
self.size = size
self.Dots = []
for i in range(size):
self.Dots.append(Dot(SPAWN))
self.minStep = 20
self.gen = 0
self.bestDot = 0
self.fit_sum = 0
def update(self):
for d in self.Dots:
d.update()
def fitness(self):
for d in self.Dots:
d.calculate_fitness()
def end_of_generation(self):
for d in self.Dots:
if not d.dead and not d.reachedGoal:
return False
return True
def natural_selection(self):
self.fitness()
new_dots = sorted(self.Dots, key=lambda x: x.fitness)
new_dots.reverse()
new_dots = new_dots[:len(new_dots)//2] * 2
print([i.fitness for i in new_dots])
self.Dots = [d.make_baby() for d in new_dots]
self.Dots[0].is_best = True
for d in range(len(self.Dots) // 2, len(self.Dots)):
self.Dots[d].brain.mutate()
test = Population(100)
goal = Goal()
run = True
while run:
win.fill('white')
goal.update()
if test.end_of_generation():
test.natural_selection()
time.sleep(1)
else:
test.update()
# for event in pg.event.get():
# if event.type == pg.QUIT:
# run = False
pg.display.update()
time.sleep(0.005)
pg.quit()
The important part of this code is the natural_selection() function in the population class:
def natural_selection(self):
self.fitness()
new_dots = sorted(self.Dots, key=lambda x: x.fitness)
new_dots.reverse()
new_dots = new_dots[:len(new_dots)//2] * 2
print([i.fitness for i in new_dots])
self.Dots = [d.make_baby() for d in new_dots]
self.Dots[0].is_best = True
for d in range(len(self.Dots) // 2, len(self.Dots)):
self.Dots[d].brain.mutate()
What it does (or supposed to do) is to calculate the fitness of the dots, sort the list of dots by fitness from highest to lowest, cuts the list in half and duplicating it, so the first and second halves are the same, and then sets the first dot to be the best and mutates the second half. The problem is that as the print in line 6 shows, it doesn't really mutate the dots, and the result is that in every generation it just takes the same repeating list and sorts it, and the fitnesses look like this:
[0.003441755148372998, 0.0034291486755453414, 0.003070574887525978, 0.0030339596318951327, 0.003030855079397534,...]
[0.00481387362410465, 0.00481387362410465, 0.003468488512721536, 0.003468488512721536, 0.0032419920180191478,...]
[0.004356736047656708, 0.004356736047656708, 0.004356736047656708, 0.004356736047656708, 0.003056862712974015,...]
I checked the brain.mutate function and it seems to work just fine.