Reversing Conway’s Game of Life: An Exploration of Solutions to a One-to-Many Problem

Authors

  • Brittany Harbison
  • Eric Cabarlo
  • Dustin Lee
  • Logan Capes

Abstract

Conway's Game of Life is a classic cellular automaton, developed by mathematician John Conway in 1970. It explores the evolution of a grid of cells, how each cell lives or dies based upon the state of the cells surrounding it. The Game of Life follows a set of defined rules of cellular automata to determine this state, which mimic rules of reproduction, isolation, overcrowding, and survival in a population. These rules, and the patterns they generate, have proved widely applicable to research in many fields, including cellular biology, epigenetics, population dynamics, and others. The questions that this automaton answered also inspired another: Is it possible to determine the unique starting configuration of a pattern of cells? This is a non-trivial problem, as the relationship between the starting and ending configurations is one-to-many; for a specific starting state, many different end states may arise. This work highlights methods of reversing Conway’s Game of Life using various machine learning algorithms, discusses the benefits and drawbacks of each approach, and provides a comparison of the accuracy and memory footprint associated with each approach.

Downloads

Published

2020-05-11

Issue

Section

Computer Science