Lab Exercise 3 (Two-Player Game of Life and Beyond)

Context

The Game of Life is not your typical computer game. It is a cellular automaton, and was invented by Cambridge mathematician John Conway.

This game became widely known when it was mentioned in an article published by Scientific American in 1970. It consists of a grid of cells which, based on a few mathematical rules, can live, die or multiply. Depending on the initial conditions, the cells form various patterns throughout the course of the game.

Conway's Game of Life works on an infinite two-dimensional grid of cells. A cell is either "alive" (occupied), or "dead" (empty).

An initial state of the grid is set, after which, the next turn, or generation, of the cells in the grid is determined from the current state, and a set of very simple rules:

Game of Life Rules

For a cell that is empty:

Each cell with exactly three neighbors becomes occupied

For a cell that is occupied:

Each cell with one or no neighbors dies, as if by solitude
Each cell with four or more neighbors dies, as if by overpopulation
Otherwise, the cell survives

Here, the neighbors of the cell are interpreted to be the Moore neighborhood (all 8 adjacent cells)

Here is a short video explaining the rules. (link).

What is surprising is that from these simple rules, a lot of different shapes or "lifeforms" arise, exhibiting complex behavior such as movement, replication, repetition, or apparent randomness.

One example would be the Gosper Glider gun, which is a cyclic "gun" that generates "gliders", which are one of basic shapes that exhibit stable movement.

Conway's Game of Life can be shown to be Turing complete. Constructs can be created to simulate bit streams, basic logic gates, as well as memory (link).

It can be shown that the Game of Life

Two-"player" Game of Life?

Extensions or variants of the game have been created, with varying rules, or neighborhoods, or even different cell entities, aside from just the binary "alive" or "dead".

One such extension is the p2life (link) p2life allows one of two types of tokens, black or white, to inhabit a cell, and adds competitive elements into the birth and survival rules of the original game.

The rules of p2life are as follows, from white's point of view:

For a cell that is empty:

If the cell has exactly three white neighbors and the number of black neighbors is different from three, then a white token is born in the empty cell.
If the cell has exactly three white and three black neighbors, an unbiased coin toss determines whether a white or black token is born in the cell.

For a cell that is occupied (by a white token):

If the difference between the number of white and black neighbors is two or three, then the white token survives.
If the difference between the number of white and black neighbors is one and the number of white neighbors is at least two, then the white token survives.
Otherwise, the white token dies.

The rules are symmetric for black; just swap "white" and "black" in the rules above.

Summary of Task

Your task is to implement several classes following the Grid Protocol and the Ruleset Protocol for a terminal-based engine for the Game of Life, and other Life-like games. The engine should be capable of simulating different types of behavior through the use of subtyping as well as dependency injection of the Rulesets. The lab will exhibit separation of concerns using the MVC pattern.

The class implementations should all be in the grids_rulesets.py file.

Overview

Task

Common types

You must have a file in common_types.py containing exactly the following:

from collections.abc import Sequence
from enum import Enum


class Species(Enum):
    EMPTY = '.'
    ALIVE = '▮'
    WHITE = 'o'
    BLACK = '*'


type Coords = tuple[int, ...]
type Neighbors = dict[Coords, Species]


class Ruleset(Protocol):
    def empty_cell_next(self, neighbors: Neighbors, *coords: int) -> Species:
        ...

    def occupied_cell_next(self, neighbors: Neighbors, value: Species, *coords: int) -> Species:
        ...


class Grid(Protocol):
    @property
    def dimensions(self) -> Coords:
        ...

    @property
    def grid_display(self) -> str:
        ...

    def init_grid(self, initial_state: Sequence[tuple[Coords, Species]]):
        ...

    def get_neighbors(self, *coords: int) -> Neighbors:
        ...

    def get_cell(self, *coords: int) -> Species:
        ...

    def set_cell(self, value: Species, *coords: int) -> None:
        ...

    def get_next_generation(self, ruleset: Ruleset) -> None:
        ...

Coords is an alias for a tuple of ints, representing grid coordinates. For this lab, we will mostly be using 2D coordinates.

Neighbors is a mapping of Coords to the Species occupying that cell in the grid. Species.EMPTY means that a cell is empty.

You may edit the Species Enum to add more species types. Aside from that, if you need to define more types that are accessible across the different MVC parts, create a new file instead of editing common_types.py.

Classes following the Grid protocol have empty grids by default.

Protocols and Model

When we say "formal argument", we mean the x and y in def f(x: int, y: int) -> int:.

The Ruleset Protocol prescribes the following methods:

empty_cell_next (method)
- Takes in a Neighbors, corresponding to neighbors of an empty cell. This is a Python dictionary mapping Coords to Species
- Takes in a Coords, corresponding to the coordinates of the empty cell
- Returns the Species value of the empty cell in the next generation, according to the ruleset
occupied_cell_next (method)
- Takes in a Neighbors neighbors, corresponding to neighbors of an occupied cell. This is a Python dictionary mapping Coords to Species
- Takes in a Species value, corresponding to the value of the occupied cell
- Takes in a Coords, corresponding to the coordinates of the occupied cell
- Returns the Species value of the occupied cell in the next generation, according to the ruleset

The Grid Protocol prescribes the following attributes and methods:

dimensions (@property attribute)
- A tuple[int, int] denoting the number of display rows and display columns of the grid.
- The topleftmost cell has coordinates (0, 0).
grid_display (@property attribute)
- Returns a str representing the viewable grid
init_grid (method)
- Takes in a Sequence of pairs (tuples with two elements) of Coords and Species
- Initializes the grid. Populates the grid at each coordinate with the given Species value
get_neighbors (method)
- Takes in *coords: int, a variadic argument of ints. For this lab, we will mostly be working with two coordinates (2D).
- Returns a Neighbors type (see custom types above)
get_cell (method)
- Takes in *coords: int and returns the Species in the cell with the given coordinates.
set_cell (method)
- Takes in value: Species and *coords: int
- Sets the contents of the cell to value
get_next_generation (method)
- Takes in ruleset: Ruleset
- Uses the methods in ruleset to produce the next state of the grid

The Game class will be provided to you as the controller in the MVC framework. It will accept a Grid and a Ruleset in its initializer.

You may add additional fields and methods to the ones listed above, but your implementation will be tested using the prescribed fields and methods.

You must have unit tests (runnable via pytest) for the attributes and methods of each specific Ruleset you will be implementing.

You must also have unit tests for Grids paired up with specific Rulesets, especially to test the get_next_generation method. For Rulesets with randomization elements, you should use a fixed random seed for the random number generation (Random(seed) where seed is your seed).

All unit tests must be runnable using pytest from the base directory.

Note

To make testing elements that involve randomness easier, you may use a fixed random number generator by making a Random object (passing in an integer as the seed).

For example, the following block of code will always print out the same five lines:

from random import Random

rng = Random(12)
for _ in range(5):
    print(rng.randint(1, 10))

Meanwhile, the following block of code will (likely) have different outputs every time you run it:

from random import randint

for _ in range(5):
    print(randint(1, 10))

Scoring

This lab exercise will be scored in phases. You can get \(0/20/50/80/100 \%\) of the points in a phase depending on how far/close you are from meeting the phase's requirements. You must get \(\ge 80 \%\) of the points in each of the previous phases to get nonzero points for a certain phase.

For example, if you get Phases 1, 2, \(80\%\) of Phase 3, and \(20\%\) of Phase 4, you get a total of \(30 + 60 + 30 \times 0.8 + 30 \times 0.2 = 120\) points for this lab.

This lab will be scored over \(100\) 🔴.

Note

For all phases, your program should be runnable using the command python3 game_of_life.py.

Indicate the farthest phase you (think you) got in a README.md file.

Sample game_of_life.py

from lab03.view import GameOfLifeView
from lab03.controller import GameOfLifeController
from lab03.grids_rulesets import (
    SomeGrid,
    SomeRuleset,
    gosper_glider_gun
)


ROWS = 30
COLS = 70
FPS = 30


if __name__ == '__main__':
    grid = SomeGrid(ROWS, COLS)
    grid.init_grid(gosper_glider_gun)
    gol = SomeRuleset()
    view = GameOfLifeView(FPS)
    controller = GameOfLifeController(grid, gol, view)
    controller.run()

Phase 1 (\(40\) 🔴)

For Phase 1, you will need to implement two things:

Inf2DGrid class, following the Grid Protocol. The class initializer must take at least two parameters, corresponding to the number of rows and columns of the visible grid.

The topleftmost cell of the visible grid has coordinates (0, 0), and the bottomrightmost cell has coordinates (rows - 1, cols - 1).

Inf2DGrid will simulate an infinite 2D grid, so you will need to keep track of the state of the cells outside the visible grid. You could implement it as a normal grid that is slightly larger than the visible grid.

GameOfLifeRuleset class, following the Ruleset Protocol. This class will implement the basic rules of the original Conway's Game of Life.

Create unit tests for both Inf2DGrid and GameOfLifeRuleset, as well as both of the classes working together.

Phase 2 (\(40\) 🔴)

For Phase 2, in addition to the Phase 1 classes, you will need to implement:

P2LifeRuleset class, following the Ruleset Protocol. This class will implement the rules of the p2life extension of Game of Life. P2LifeRuleset must take a seeded Random instance in its initializer, for the randomization aspects of the p2life rules.

Create unit tests for P2LifeRuleset, as well as both P2LifeRuleset and Inf2DGrid working together.

Phase 3 (\(40\) 🔴)

For Phase 3, experiment with your own Grid, or Ruleset, or both. Try to find a combination that produces "interesting" behavior.

Stick to simple rules. The goal is to follow the idea behind Conway's Game of Life: complex behavior arising from simple rules.

Document your choices and specifications in the README.md given in the lab repository. Note at least one initial state that leads to "interesting" behavior given your Grid and Ruleset choices.

Here are suggestions for the aspects of Grids and Rulesets that you can vary/extend:

`Grid`s

grid shape (e.g. hexagonal, triangular)
grid limits (e.g. finite)
alternative neighborhoods (e.g. toroidal (wraps around), diagonal)

`Ruleset`s

alternative rules for birth and death
other info aside from neighborhood info affects births and deaths (e.g. parity of coordinates)

Final Submission

Via DCS Yagit (https://yagit.upd-dcs.work/).

Deadline: September 21, 2026 (M) 11:12 pm