A Probabilistic Approach To Conway's Game of Life (And Related Cellular Automata)
Mentor 1
Jeb Willenbring
Location
Union 250
Start Date
24-4-2015 2:00 PM
Description
Conway's Game of Life is the most well-known instance of a class of computational structures known as cellular automata. Conway's Game of Life, and other "life-like" cellular automata, are "played" on an infinite/arbitrarily large square lattice. At the beginning of the game every square (known as a "cell") is either "alive" or "dead", and at each stage of the game ("generation"), every cell changes its state or not based on the number of alive cells around it. Locally, the game is very simple, but globally, surpisingly complex and chaotic patterns emerge from these rules. The central question in our investigation is: given a starting "density", what can we say about the eventual or long-term behavior of our board? In particular, what can we say about the long-term density? We attempted to tackle this question theoretically and experimentally. We collected large amounts of data running finite boards in Mathematica that seems to converge to likely behavior for the idealized infinite case. In addition to that we used a combination of algebraic, probabilistic and combinatorial reasoning to develop a polynomial that both accurately predicts short-term behavior and, in a looser way, reflects the behavior of various automata rules.
A Probabilistic Approach To Conway's Game of Life (And Related Cellular Automata)
Union 250
Conway's Game of Life is the most well-known instance of a class of computational structures known as cellular automata. Conway's Game of Life, and other "life-like" cellular automata, are "played" on an infinite/arbitrarily large square lattice. At the beginning of the game every square (known as a "cell") is either "alive" or "dead", and at each stage of the game ("generation"), every cell changes its state or not based on the number of alive cells around it. Locally, the game is very simple, but globally, surpisingly complex and chaotic patterns emerge from these rules. The central question in our investigation is: given a starting "density", what can we say about the eventual or long-term behavior of our board? In particular, what can we say about the long-term density? We attempted to tackle this question theoretically and experimentally. We collected large amounts of data running finite boards in Mathematica that seems to converge to likely behavior for the idealized infinite case. In addition to that we used a combination of algebraic, probabilistic and combinatorial reasoning to develop a polynomial that both accurately predicts short-term behavior and, in a looser way, reflects the behavior of various automata rules.
