Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Searching for patterns in Conway's Game of Life
Conway’s Game of Life (Life) is a simple cellular automaton, discovered by John Conway in 1970, that exhibits complex emergent behavior. Life-enthusiasts have been looking for building blocks with specific properties (patterns) to answer unsolved problems in Life for the past five decades. Finding p...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
Department of Computer Science
2020
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613573024317440 |
|---|---|
| access_status_str | Open Access |
| author | Bontes, Johan |
| author2 | Gain, James |
| author_browse | Bontes, Johan Gain, James |
| author_facet | Gain, James Bontes, Johan |
| author_sort | Bontes, Johan |
| collection | Thesis |
| description | Conway’s Game of Life (Life) is a simple cellular automaton, discovered by John Conway in 1970, that exhibits complex emergent behavior. Life-enthusiasts have been looking for building blocks with specific properties (patterns) to answer unsolved problems in Life for the past five decades. Finding patterns in Life is difficult due to the large search space. Current search algorithms use an explorative approach based on the rules of the game, but this can only sample a small fraction of the search space. More recently, people have used Sat solvers to search for patterns. These solvers are not specifically tuned to this problem and thus waste a lot of time processing Life’s rules in an engine that does not understand them. We propose a novel Sat-based approach that replaces the binary tree used by traditional Sat solvers with a grid-based approach, complemented by an injection of Game of Life specific knowledge. This leads to a significant speedup in searching. As a fortunate side effect, our solver can be generalized to solve general Sat problems. Because it is grid-based, all manipulations are embarrassingly parallel, allowing implementation on massively parallel hardware. |
| format | Thesis |
| id | oai:open.uct.ac.za:11427/31573 |
| institution | University of Cape Town (South Africa) |
| language | eng |
| last_indexed | 2026-06-10T12:38:17.565Z |
| license_str | Not specified — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from UCTD — University of Cape Town Open Access Repository |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| publisher | Department of Computer Science |
| publisherStr | Department of Computer Science |
| record_format | dspace |
| source_str | UCTD — University of Cape Town Open Access Repository |
| spelling | oai:open.uct.ac.za:11427/31573 Searching for patterns in Conway's Game of Life Bontes, Johan Gain, James Computer Science Conway’s Game of Life (Life) is a simple cellular automaton, discovered by John Conway in 1970, that exhibits complex emergent behavior. Life-enthusiasts have been looking for building blocks with specific properties (patterns) to answer unsolved problems in Life for the past five decades. Finding patterns in Life is difficult due to the large search space. Current search algorithms use an explorative approach based on the rules of the game, but this can only sample a small fraction of the search space. More recently, people have used Sat solvers to search for patterns. These solvers are not specifically tuned to this problem and thus waste a lot of time processing Life’s rules in an engine that does not understand them. We propose a novel Sat-based approach that replaces the binary tree used by traditional Sat solvers with a grid-based approach, complemented by an injection of Game of Life specific knowledge. This leads to a significant speedup in searching. As a fortunate side effect, our solver can be generalized to solve general Sat problems. Because it is grid-based, all manipulations are embarrassingly parallel, allowing implementation on massively parallel hardware. 2020-03-12T13:43:26Z 2020-03-12T13:43:26Z 2019 2020-03-12T13:07:38Z Master Thesis Masters MSc http://hdl.handle.net/11427/31573 eng application/pdf Department of Computer Science Faculty of Science |
| spellingShingle | Computer Science Bontes, Johan Searching for patterns in Conway's Game of Life |
| thesis_degree_str | Master's |
| title | Searching for patterns in Conway's Game of Life |
| title_full | Searching for patterns in Conway's Game of Life |
| title_fullStr | Searching for patterns in Conway's Game of Life |
| title_full_unstemmed | Searching for patterns in Conway's Game of Life |
| title_short | Searching for patterns in Conway's Game of Life |
| title_sort | searching for patterns in conway s game of life |
| topic | Computer Science |
| url | http://hdl.handle.net/11427/31573 |
| work_keys_str_mv | AT bontesjohan searchingforpatternsinconwaysgameoflife |