Searching for patterns in Conway's Game of Life
| dc.contributor.advisor | Gain, James | |
| dc.contributor.author | Bontes, Johan | |
| dc.date.accessioned | 2020-03-12T13:43:26Z | |
| dc.date.available | 2020-03-12T13:43:26Z | |
| dc.date.issued | 2019 | |
| dc.date.updated | 2020-03-12T13:07:38Z | |
| dc.description.abstract | 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. | |
| dc.identifier.apacitation | Bontes, J. (2019). <i>Searching for patterns in Conway's Game of Life</i>. (). ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/31573 | en_ZA |
| dc.identifier.chicagocitation | Bontes, Johan. <i>"Searching for patterns in Conway's Game of Life."</i> ., ,Faculty of Science ,Department of Computer Science, 2019. http://hdl.handle.net/11427/31573 | en_ZA |
| dc.identifier.citation | Bontes, J. 2019. Searching for patterns in Conway's Game of Life. . ,Faculty of Science ,Department of Computer Science. http://hdl.handle.net/11427/31573 | en_ZA |
| dc.identifier.ris | TY - Thesis / Dissertation AU - Bontes, Johan AB - 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. DA - 2019 DB - OpenUCT DP - University of Cape Town KW - Computer Science LK - https://open.uct.ac.za PY - 2019 T1 - Searching for patterns in Conway's Game of Life TI - Searching for patterns in Conway's Game of Life UR - http://hdl.handle.net/11427/31573 ER - | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/11427/31573 | |
| dc.identifier.vancouvercitation | Bontes J. Searching for patterns in Conway's Game of Life. []. ,Faculty of Science ,Department of Computer Science, 2019 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/31573 | en_ZA |
| dc.language.rfc3066 | eng | |
| dc.publisher.department | Department of Computer Science | |
| dc.publisher.faculty | Faculty of Science | |
| dc.subject | Computer Science | |
| dc.title | Searching for patterns in Conway's Game of Life | |
| dc.type | Master Thesis | |
| dc.type.qualificationlevel | Masters | |
| dc.type.qualificationname | MSc |