# The zero player Darwinism simulation game as described by Conway (demonstrates Turing Completeness)

### Related tags

Game Development Conway

# Conway's Game of Life

The zero player Darwinism simulation game as described by Conway (demonstrates Turing Completeness).

I created this script after having made attempts to do the same project in the past, but being limited by the horizons of my knowledge. I've tried again recently and the algorithms I chose to use in this one were much faster. My old project often ran out of memory or spent ~20 seconds in between each generation, this project gets through a couple hundred at least in the same amount of time, but I digress.

If you aren't already aware, Conway's Game of Life is a thought experiment turned into a program which simulates natural selection in order to demonstrate the idea of Turing Completeness. In this "zero player game" as Conway described it, cells are given an initial state, or seed, and then the rules below are applied over and over, for an undecidable amount of time in most cases.

The rules are as follows:

1. Any live cell with fewer than two live neighbours dies, as if by underpopulation.
2. Any live cell with two or three live neighbours lives on to the next generation.
3. Any live cell with more than three live neighbours dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.

For further information on the game itself (and for generally interesting information told in a digestible format) see this video: https://www.youtube.com/watch?v=HeQX2HjkcNo

Keep reading if you care to know the implementation / thought process behind the program's algorithm (it isn't obvious just looking), otherwise you can stop here. (Note: this is all pure Python, no Cython)

The most naive approach, and the one I had used to tackle this problem the first time is essentially brute force. In this method, I stored every cell in a list. When I needed a particular cell in a particular position, I used a method that would search that list, checking each and every Cell's x and y values until I found the exact one I needed. Not the best time complexity wise, especially when you have to do something that simple so often. Even worse, when grabbing the neighbors, I simply repeated the same thing 8 times. The benefits of such an approach are limited mostly to simplicity, and of course, this approach did not work. At extremely small scales, with "non explosive" patterns, the algorithm did appear to work in terms of the rules, but it certainly did not work with my GPU.

The next approach I tried, some few months later, was to use a dictionary to store cells by location. This is certainly getting there, and is actually implemented in my current version, however it does not go far enough. Neighbors were still grabbed manually, methods handling cell positions and graphics were stil slow and unoptimized, and there was a lot of unnecessary clutter.

In the current approach, I store the grid in the format `dict[tuple[int, int], dict[tuple[int, int], bool]]` such that the outer tuples are the locations of a cell, the inner dict tuples are locations of that cells neighbors, and the boolean values are the cells dead or alive status. This comes with the benefit of constant lookup times in all aspects regarding cells, leaving almost all time constraints up to the algorithms themselves. I would love to say there are more major optimizations but this data structure is actually hyper-efficient compared to my previous iterations of this project, and it's likely doing all the heavy lifting. That isn't to say there aren't other optimizations, though. There are probably hundreds of micro-optimizations scattered throughout this code compared to the old attempts.

##################################################################################################################################################################

The reason I chose to write so much about this project is due to my lack of having a GitHub account before this. I did not upload the old versions of this project, nor anything else I have ever written, and my digital organizational skills are poor, so they are lost to the sands of time as far as I'm considered. This readme is to make up for that lost history, I suppose. In the future I'll only be doing this much if there is really this much to say. I'll also be uploading all my major and minor projects (anything that is more than a "quick script") on GitHub from here on out. Thanks for reading.

##### Wordle-player - An optimal player for Wordle. Based on a rough understanding of information theory

Wordle-player - An optimal player for Wordle. Based on a rough understanding of information theory

##### Official PyTorch implementation of NAC from the paper: Neural Auto-Curricula in Two-Player Zero-Sum Games.

NAC Official PyTorch implementation of NAC from the paper: Neural Auto-Curricula in Two-Player Zero-Sum Games. We release code for: Gradient based ora

##### This is a two player snake game

Trake This is a two player snake game How to play the game There is food and two players. You try to eat food to become large and gain points. Player

##### A Gomoku game GUI using pygame where the user can choose to play against another player or an AI using minimax with alpha-beta pruning

Gomoku A GUI based Gomoku game using pygame where the user can choose to play against another player or an AI using minimax with alpha-beta pruning. R

##### 2d war game single player

WarGame-third-version-0.0.4- 2d war game single player Hi ! Today, I publish on GitHub the version 0.0.4 of "WarGame". In this version, you can find a

##### AutoPilot is a game where the player controls a car and tries to get the highest score he can while not dying under falling cement blocks.

AutoPilot AutoPilot is a game where the player controls a car and tries to get the highest score he can while not dying under falling cement blocks. C

##### A python-based multi-player online educational game for students to play in a class or club setting.

Kurono (codename: aimmo) Code for Life has been developed by Ocado Technology as a free, open-source project to inspire the next generation of compute

##### Follow the numbers - A simple game where the player should follow the numbers and connect the dots

follow_the_numbers This is a simple game where the player should follow the numb

###### jachinema
Been coding for a little while, I do projects for fun when I can. Rate of doing so is slow at the moment because of school, but I try.
###### Game-of-life - A simple python program to simulate and visualise the Conway's Game of life

Conway's game of life A simple python program to simulate and visualise the Conw

3 Feb 20, 2022
###### Implementation of Conway's game of life in python.

?? ????‍?? Conway's Game of Life ????‍?? ?? by FranciscoCharles An interactive simulator that implements the standard Conway Game of Life with a simpl

3 Oct 1, 2021
###### An interactive pygame implementation of Conway's Game of Life

Game of Life An interactive pygame implementation of Conway's Game of Life Installation Clone the repo and navigate into it. git clone https://github.

1 Dec 5, 2021
###### Simple python program to simulate Conway's game of life with custom variables.

ConwaysGameOfLife Simple python program to simulate Conway's game of life with custom variables. Custom Variables Grid-size : Change the size of the p

1 Oct 28, 2021
###### A small fun project to simulate Conway's Game of Life, created in Python.

A small fun project to simulate Conway's Game of Life, created in Python. Conway's Game of Life simulates a grid of cells, where the state of each cell consists of whether the cell is alive or dead.

1 Jun 19, 2022
###### Graphical impimetaion of Conway's Game of Life in Python using pyglet

Conway's Game of Life in Python Konstantin Opora Conway's Game of Life: graphical implementation in python using pyglet. developed in Python 3.10.0 Re

1 Nov 30, 2021
###### A pygame implementation of John Conway's Game of Life

Game of Life A Pygame Simulation This is a Pygame implementation of the famous Conway's Game of Life. The game features a set of very simple rules: An

1 Jan 6, 2022
###### 🐍 Conway's Game of Life cellular automaton implemented in PyGame

Conway's Game of Life My PyGame implementation of Conway's Game of Life. This implementation involves treating all edges of the grid as stitched toget

1 May 29, 2022
###### Synthesizer based on Conway's Game of Life

Conway Synth Synthesizer based on Conway's Game of Life Trying to avoid step sequencer fashions that have been done before and basing it on actual cel

4 Mar 15, 2022
###### An implementation of John Conway's Game of Life.

This is an implementation of John Conway's Game of Life in Python, and a very basic and straightforward one at that.

3 Feb 11, 2022