Using Citizen Science to discover Cool Patterns
-
LumpsOfMuck
- Posts: 60
- Joined: October 11th, 2011, 5:58 pm
Using Citizen Science to discover Cool Patterns
I'm pretty sure some of you know that as far as we've come in creating patterns in conway's game of life, there is still a lot we don't know. For example, does Conway's game of life contain a replicator, are there oscillators for all periods, and how many spaceship velocities are there to name a few. Now here's where citizen science comes in. FOr anyone who doesn't know what citizen science is, it's when citizens aid a cause by doing minor things in large numbers. An example of this is a program called B.O.I.N.C. that was developed by Berkely University. WHat B.O.I.N.C. does in a nutshell is send out workunits to computers all around the world, and the recipients of said work units process them using their computers' unused processing power. It stands to reason that, if enough people run these workunits, even if their computers are supstandard in speed, they can accomplish more things faster than even the fastest computers in existance. Now here's where life comes in. If someone was to develope a project which sent out initial starting patterns for Conway's game of life, things could be discovered at a rate that is much faster than anything before. Of course, several things would need to be done before any workunits could be sent out, such as a reliable workunit generator and admission to B.O.I.N.C., but the rewards are well worth it, or at least in my opinion anyways. Just wanted to let everyone know about this idea and see what they thought about it. Please give your thoughts on the idea, they don't have to be deep, but I want to see what you think
Last edited by LumpsOfMuck on November 12th, 2011, 5:43 pm, edited 1 time in total.
-
LumpsOfMuck
- Posts: 60
- Joined: October 11th, 2011, 5:58 pm
Re: Using Citizen Sciience to help life, Your Thoughts
I really need your opinions people, do you think sending out datapackets to numerous computers around the world is a waste of time, or is it a worthy cause? Please leave your comments and concerns.
Re: Using Citizen Science to discover Cool Patterns
I think it is potentially very useful. I don't think a replicator is something we can search for, as it would be too large. However, we could attempt to do a complete search for GoEs in an 11 by 11 bounding box.
Re: Using Citizen Science to discover Cool Patterns
There has been discussion of distributed search projects in the past (e.g. here), but few have ever been implemented (the only example I know of is Nathaniel Johnston's soup search). Some of the programs that could potentially be turned into distributed programs are LifeSearch, gfind, and ptbsearch.
In many cases, such as brute force enumeration searches, it would be necessary for the server to keep track of which parts of the search space have been covered, and to assign parts of the search to different computers to ensure that none of them are performing redundant calculations. How exactly to split the search is an important issue to consider. A naive method may work in some cases. For example, censusing the final result of all of the patterns in a given bounding box can be done relatively simply by assigning each computer a subset of the total possible patterns to test. Since, on average, the patterns will take approximately the same amount of time to be tested, a particular computer is unlikely to be given too large of a portion of the search to manage.
In other cases, however, a naive approach may not work so well, as it may result in assigning a branch of the search that is too large for a single computer to finish in a reasonable amount of time. For example, when using the lifesearch algorithm, it is generally difficult (I think) to predict the size of the branch of the search created when a particular cell's state is set. In such cases, a more sophisticated method of splitting the search may be necessary, such as splitting any tasks that are taking too long on a single computer (the difficulty in this particular example being that the server must dynamically split the search).
Since the purpose of this type of distributed project is to reduce the overall time to find a solution, it would be good to optimize ones algorithm in the context of distributed programming. For example, sending large files over the network too often would negatively affect the programs performance.
There are, of course, other things to consider, such as optimizing the search algorithm and and determining what data needs to be sent between the server and clients.
In terms of using BOINC, it is not necessary, but being associated with a larger project may result in contributions from people outside of the Life community.
The primary reason that none of these projects have been started is that nobody has been able to devote the necessary time to them. I greatly encourage anyone who has the time and desire to work on such a project! I know there are plenty of people in the Life community who would be glad to contribute to a distributed search effort.
In many cases, such as brute force enumeration searches, it would be necessary for the server to keep track of which parts of the search space have been covered, and to assign parts of the search to different computers to ensure that none of them are performing redundant calculations. How exactly to split the search is an important issue to consider. A naive method may work in some cases. For example, censusing the final result of all of the patterns in a given bounding box can be done relatively simply by assigning each computer a subset of the total possible patterns to test. Since, on average, the patterns will take approximately the same amount of time to be tested, a particular computer is unlikely to be given too large of a portion of the search to manage.
In other cases, however, a naive approach may not work so well, as it may result in assigning a branch of the search that is too large for a single computer to finish in a reasonable amount of time. For example, when using the lifesearch algorithm, it is generally difficult (I think) to predict the size of the branch of the search created when a particular cell's state is set. In such cases, a more sophisticated method of splitting the search may be necessary, such as splitting any tasks that are taking too long on a single computer (the difficulty in this particular example being that the server must dynamically split the search).
Since the purpose of this type of distributed project is to reduce the overall time to find a solution, it would be good to optimize ones algorithm in the context of distributed programming. For example, sending large files over the network too often would negatively affect the programs performance.
There are, of course, other things to consider, such as optimizing the search algorithm and and determining what data needs to be sent between the server and clients.
In terms of using BOINC, it is not necessary, but being associated with a larger project may result in contributions from people outside of the Life community.
The primary reason that none of these projects have been started is that nobody has been able to devote the necessary time to them. I greatly encourage anyone who has the time and desire to work on such a project! I know there are plenty of people in the Life community who would be glad to contribute to a distributed search effort.
-Matthias Merzenich