Conway's Game of Life is a 'cellular automaton' created by the British mathematician John Conway in 1970. It is a zero-player game, meaning that once the initial state is set, the game evolves without any further input. The game is played on a grid of cells, each of which can be in one of two states: alive or dead.
The game's evolution is determined by a set of simple rules based on the number of live neighbors around a cell. The game takes place in discrete time steps, with the state of the grid being updated in each step according to the following rules:
Rules:
- Any live cell with two or three live neighbors survives to the next generation.
- Any dead cell with exactly three live neighbors becomes a live cell (birth).
- All other live cells die (due to loneliness or overpopulation).
- All other dead cells remain dead.
Create a genetic algorithm that finds the best Methuselahs in the "Game of Life" (The 'best' starting configurations that live the longest and create as many cells alive throughout their existence (until they become either static or repeat themselves)):
1. Start with a random population of n chromosomes (n grids which represent each starting configuration of a different Methuselah).
3. Calculate the probabilities of choosing the i'th configuration to be a parent (of another descendent configuration), using a normalisation function
How did you define what is a repetitive state (and follows from that how did you define a static state)?
Well, the cellsAlive() function is a tricky function, you need to count the current cells alive in the grid but also have to stop when you reach a repetitive state.
The first idea I thought about is to just keep a list of my last n grids representing my previous n-genertaions though that is an expensive approach in terms of Space complexity and Time Complexity assuming I would need a list of n-previous grids the Space complexity would be
The Second idea I had was, to distinguish each repetitive state, by defining a variable that would indicate if there was a 'big' change, in the amount of cells in the previous n generations, and if there weren't any then it would declare the state as repetitive and exit the aliveCells function
The last idea I had was the best one that worked perfectly, for anyone not familiar with hash algorithms, here is a short description of them: Hash algorithms are mathematical functions that take input data of any size and produce a fixed-size string of characters, typically a sequence of numbers and letters. This output, known as a hash or digest, is unique to the input data, meaning even small changes to the input will produce a significantly different hash. Hash algorithms are widely used in cryptography, data integrity checks, and password storage due to their ability to create a secure, irreversible representation of data.
Based on that idea in mind, I used a list that contained the previous-n hashes calculated by my hash function (which later on you can read what I used) of the each previous generation-grid.
Continuously, each generation, I would calculate my current generation-grid hash, and check if the hash is the same as any other hash I stored in the list, later on (if it wasn't in the list, i.e. not repetitive) add it to the previous previous-n hashes and count the current alive cells. This solution is sufficient with
I thought about many hash functions that might work, such as: SHA256 or maybe even the checksum function (like in linux) - but eventually I decided to implement a different one, a one that has it's collision number at the lowest (A case were 2 different imputs create the same hash value).
Here it is:def compute_grid_unique_integer(grid):
"""
Encodes a binary grid (1s and 0s) into a unique integer.
Assumes the grid dimensions are fixed.
"""
binary_string = ''.join(str(cell) for row in grid for cell in row)
return int(binary_string, 2)Each grid-offspring is created using two parents. Each parent contributes equally to the offspring, with both having an equal chance of influencing the child's traits. This ensures that the genetic diversity from both parents is preserved and balanced, giving both parents an equal opportunity to pass on their beneficial characteristics to the next generation.
The process as I chose to implement it is as follows: 1. Iterate through only the relevent cells (meaning we produce a "starting configuration" of the offspring, the same size of the parents). 2. For each cell position in the grid (i,j) we choose a parent randomly. 3. We insert the chosen parent at indexes (i,j) to the same cell position in the offsprings grid. offspring[i][j] = chosen_parent[i][j] . 4. At the end we introduce a mutation 🦠🦠🦠 with a certain probability, where a cell can switch between alive and dead states.
For those interested in the code here it is:def mate(parent1, parent2, parents_configuration_size):
"""
Create offspring by mating two parents with a chance of mutation.
Parameters:
parent1 (list): The first parent's 2D grid.
parent2 (list): The second parent's 2D grid.
parents_configuration_size (int): The size of the parent configuration.
Returns:
list: A 2D grid representing the offspring.
"""
MUTATION_PROBABILITY = 0.02
offspring = [[0 for _ in range(GRID_WIDTH)] for _ in range(GRID_HEIGHT)]
start_row = (GRID_WIDTH - parents_configuration_size) // 2
start_column = (GRID_HEIGHT - parents_configuration_size) // 2
# Embed the input matrix into the center of the output matrix
for i in range(start_row, parents_configuration_size + start_row):
for j in range(start_column, parents_configuration_size + start_column):
current_chosen_parent_matrix = random.choice([parent1, parent2])
offspring[i][j] = current_chosen_parent_matrix[i][j]
if random.random() < MUTATION_PROBABILITY:
offspring[i][j] = mutate(offspring[i][j])
return offspring
def mutate(number):
"""
Mutate a given value by flipping its binary state.
Parameters:
number (int): The binary value (0 or 1) to mutate.
Returns:
int: The mutated binary value.
"""
return 1 - numberIn genetic algorithms, selecting weak individuals (those with lower fitness scores) plays an important role in maintaining genetic diversity and ensuring robust exploration of the solution space. While strong individuals (with advantageous phenotypes, or expressed solutions) dominate reproduction to improve the population's overall fitness, weaker individuals often carry genotypes— underlying encoded traits that may not currently contribute to fitness but hold latent potential. These traits can act like recessive genes in biology, becoming valuable when combined with other genotypes in future generations to produce superior offspring.
By including weak individuals, the algorithm avoids premature convergence, where the population becomes too uniform and risks getting stuck in local optima. Weak individuals introduce less common genetic material into the pool, which can enhance adaptability, especially in problems with dynamic or complex fitness landscapes. Additionally, this strategy mimics the stochastic nature of evolution, where even less fit organisms occasionally survive and reproduce, leading to unexpected innovations. This balance between exploiting strong phenotypes and exploring diverse genotypes increases the algorithm’s ability to find global solutions efficiently.
