I'm not going to argue with you about my choice of tool, enough bits have been spent arguing the pros and cons of various languages without getting anywhere.
But here's a challenge for you:
I've spent, start to finish less than 10 hour to code that, having the idea (life cells that track time independently by counting generations) was 5 minutes, building it including breaks for dinner and a movie and a nightly session to work out the kinks was 10 hours.
Clone it, in any other language that you care about, as long as the following conditions are still met:
- no fixed size world
- uses the same principles
- produces correct output (easy enough to verify, the
'end' stable state of the f-pentomino minus the ejected
gliders is easily checked)
You have this code for a reference, so you really only have to make a port, or you can decide not to look at it and build it from scratch.
Report back how long it took and show the source. That way we can all learn something because I'm really curious to see other implementations in other languages.
edit: to make this clear, my 'hangup' had to do with the bit that creates new cells on the fly, I was making them one generation older than the current one, that was a tricky mistake, it seemed like the right thing to do, after all then they could 'catch up' with the current crop and things would continue.
The reason that strategy backfires is that you potentially create a cell that is older than the 2 generation 'window' that you can accommodate in this scheme (because you only hold the state for the current and previous generations in a cell).
It took me a long time to figure that out because I was very much convinced the problem was elsewhere.
If I had chosen to use a statically allocated array of cells (more in line with a hardware simulation) that would have never happened, so as always, premature optimization is the root of all evil.
Usage: run and click on the window to get next generation
I used Jython with a Swing GUI. It took me about 1.5 hours in total half of which was spent getting the GUI right :S (I never used Swing before).
The algorithm itself was fairly straightforward. It was buggy and gliders didn't work and I tried fixing the state management in the cells but in the end the bug turned out to be in the update rule of the game of life. I had "cell is alive in the next generation if it has 2 or 3 live neighbors". That should be "a cell is alive if (it is ALIVE and has 2 or 3 neighbors) OR (it is dead and has 3 neighbors)".
I don't know if it's correct now, I only tested a glider.
Features:
- the world is created on the fly
- dead cells are removed from the world, so gliders run in O(1) space
- GUI :)
A good test for 'correctness' is to run the F-pentomino both in some known good program and your own.
It looks like this:
xx
xx
x
I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders.
edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'.
The problem is with the generation counter, you only have 1 bit for the generation.
In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour.
But that is not the same as having cells completely independent.
The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current.
A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours.
In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility.
I hope that's all clear :)
Think of it this way, effectively you've made your cells globally clocked again.
You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other.
If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work.
Simulating asynchronous devices on synchronous devices is quite tricky!
> If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime.
So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work.
This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :)
The other change was:
if any(cells[n].gen < self.gen for n in neighbors if n in cells):
return
And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync.
Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern.
I can't get it to work though, because of the swing stuff.
I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax').
I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly.
The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns.
As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells.
The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion.
Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected.
That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully.
So, I'm curious if it really works for more complex structures.
All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable.
Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
The F-pentomino works, but it is VERY slow because gliders fly away and this increases the number of cells a lot O(generation) space and O(generation^2) time.
> Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
Hmm. Two cells that are next to each other can never be more than 1 generation apart, right? For example if we have cells AB then if A is in generation 10 then B can be in generation 9, 10 or 11. This happens when we call update on A:
- if B is in generation 9 we do nothing
- if B is in generation 10 we use its current value
- if B is in generation 11 we use its previous value
So really you only need to remember 2 generations (current and previous). So that would be gen%2 instead of gen%3 or gen%4...what am I missing?
When two adjacent cells are only 1 generation apart that can lead to a cell being created that is two generations away from a neighbour. It took me a while to clue in to what was happening there.
So you are correct in that you only need the two states stored, that is fine.
But the generation counter needs to have at least two full bits. 1.5 bits isn't a value to begin with in electronics, and when two populations that are synchronized via some tenuous link meet you need to guarantee that there will not be a mis interpretation of the states. For instance (not sure if this will come out ok):
3 3 0 0
3 3 3 3 1 1
2 2 2 2 2 2 2 2
Is consistent. Now if an empty cell is created between the topmost 3 and 0 it would depend on which cell caused the creation how it would interpret the value of its neigbour.
In a 'true' fabric this would not occur (because all the dead cells would exist at all times), so in this case it is an artifact of the creation of cells.
But in logic there would be no way to know who is 'ahead' when counting from 0 to 2 only, that's why you need the third possibility (modulo 3 counting), which when you make it simple hardware automatically becomes modulo 4 (otherwise you get a whole pile of gates more to use less state!).
So the generation counters would end up being 2 bits each, or two bits with a 'reset' happing at the fourth state, effectively making them 3 positions, each output from the two bit counters would go in to a 1 selected output for 4 bits input (so 16 outputs, or in your 1.5 bits case 1 out of 9) demultiplexer which would select the right combination of previous/current generation states to be used.
That's quite doable. So the effect would be completely free-running life cells that stay within one step of all their neighbours at all time.
It is very tempting to actually go and wire this up.
edit: hm, I see I'm contradicting myself here, you are right, a count of 3 should be sufficient in actual logic, it is the imperfection of the simulation that causes the problem, if all cells existed at all times 3 would be enough. But it would still require two lines for the generation to be transmitted to the neighbours.
So, in summary: two states, but 3 possibilities for the generation counter. Otherwise you can't tell who is ahead or behind, then 'different' is all you've got and you can't make the decision to wait.
Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works:
01 -- the 0 is behind
12 -- the 1 is behind
20 -- the 2 is behind
If you have non existing cells the generation counter needs to be able to go arbitrarily large (which is why it does in my program):
000 888
1 7
2 6
3 5
4444444
Lets go back to the situation where all cells exist.
In the game of life cells can only have 2 states (live or dead). In the asynchronous version they have 6 states: 2 for dead/alive * 3 for the generation counter. You could view the asynchronous version as another cellular automaton (with more possible states and different update rules).
I think you can write a procedure that takes the rules of a synchronous cellular automaton and returns a new cellular automaton that is the asynchronous version of the original.
So you could structure the program like this:
1) A function to convert an automaton to its asynchronous version
2) An asynchronous cellular automaton simulator. Instead of updating all cells in sync it updates randomly.
Edit: it's not hard actually. If the original has n states then the new one has 3n^2 states. The update rules are straightforward, but you get a huge number of them. E.g. for the game of life the original automaton has 2^9 rules (one for every possible 3x3 grid), and the asynchronous version has 12^9 rules.
The end state of golly and this seem to match up but I only eyeballed it (it seems highly unlikely that the end state would be this similar but not exactly the same).
Almost, the recursion is only used when creating new cells, other than that it is all simple iteration.
Basically the 'cell creation' is a shortcut used because I didn't want to start off with a fixed size array of cells.
Each cell operates independently of its neighbours.
Nice to have a taker!
It's a small enough project that you can do it in a day and it is large enough to get some insight into the various ways of solving things with different languages.
I'm really curious what your code will look like and what language you will write it in.
Please let me know when you're done, email in my profile.
If you start with two disconnected cell groups, how do you know when they collide? It seems like the best way to do this is to have a global cell array (or hash table) such that world[position] returns the cell at position.
If you update separate groups at different speeds you run into problems unless you save the complete history. So you still have to update everything in sync? Then what is asynchronous about this?
> If you start with two disconnected cell groups, how do you know when they collide?
You create 'dead' cells in between that connect the two populations.
That's also why you can't remove them. Remember, this is a simulation of a fabric, the dead cells not being there all the time is an optimization, in a real fabric all cells would exist all the time.
The async component is the fact that there is no global authority supplying a clock, each 'peer' is on its own from the moment of power-up.
Comments
I'm not going to argue with you about my choice of tool, enough bits have been spent arguing the pros and cons of various languages without getting anywhere.
But here's a challenge for you:
I've spent, start to finish less than 10 hour to code that, having the idea (life cells that track time independently by counting generations) was 5 minutes, building it including breaks for dinner and a movie and a nightly session to work out the kinks was 10 hours.
Clone it, in any other language that you care about, as long as the following conditions are still met:
You have this code for a reference, so you really only have to make a port, or you can decide not to look at it and build it from scratch.Report back how long it took and show the source. That way we can all learn something because I'm really curious to see other implementations in other languages.
edit: to make this clear, my 'hangup' had to do with the bit that creates new cells on the fly, I was making them one generation older than the current one, that was a tricky mistake, it seemed like the right thing to do, after all then they could 'catch up' with the current crop and things would continue.
The reason that strategy backfires is that you potentially create a cell that is older than the 2 generation 'window' that you can accommodate in this scheme (because you only hold the state for the current and previous generations in a cell).
It took me a long time to figure that out because I was very much convinced the problem was elsewhere.
If I had chosen to use a statically allocated array of cells (more in line with a hardware simulation) that would have never happened, so as always, premature optimization is the root of all evil.
Here's my solution: http://pastebin.com/f75a9ee
Usage: run and click on the window to get next generation
I used Jython with a Swing GUI. It took me about 1.5 hours in total half of which was spent getting the GUI right :S (I never used Swing before).
The algorithm itself was fairly straightforward. It was buggy and gliders didn't work and I tried fixing the state management in the cells but in the end the bug turned out to be in the update rule of the game of life. I had "cell is alive in the next generation if it has 2 or 3 live neighbors". That should be "a cell is alive if (it is ALIVE and has 2 or 3 neighbors) OR (it is dead and has 3 neighbors)".
I don't know if it's correct now, I only tested a glider.
Features:
Neat !
A good test for 'correctness' is to run the F-pentomino both in some known good program and your own.
It looks like this:
I's a really interesting little pattern that will expand quite a bit before stabilizing, it also fires off a bunch of gliders.edit: I've looked a bit more at your code, and it is almost correct for free-running instances of 'cell'.
The problem is with the generation counter, you only have 1 bit for the generation.
In a synchronous environment that would work, and because you propagate the 'update' signal from the first cell that is hit outward you will (probably) observe correct behaviour.
But that is not the same as having cells completely independent.
The connecting cells are all triggered from the first cell that gets hit. If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
I figure the absolute minimum number of bits in the generation counter is 2, because then you have one 'dead' state in between the 3 possibilities that are current.
A neighbour can be 'ahead', at the same generation or it can be 'behind' and what a cell does should be governed by the states of the neighbours.
In your program you can never get in to the 'behind' state, but in a free-running hardware solution that is a definite possibility.
I hope that's all clear :)
Think of it this way, effectively you've made your cells globally clocked again.
You also can't delete dead cells, two populations that were connected at some point in the past should stay connected or they will drift away from each other.
If a 'cell' is run by a completely independent thread which runs at some arbitrary speed the whole thing should still work.
Simulating asynchronous devices on synchronous devices is quite tricky!
> If multiple cells get triggered simultaneously (not possible in a single threaded program!) then as soon as there was a little bit of speed difference between any two cells things would go wrong.
Say we have two cells next to each other. It would go wrong if one cell is triggered twice in a row without the other cell being triggered in the meantime.
So I think I didn't understand the goal. So the goal is to have the system still behave correctly with any sequence op c.update() calls? E.g. if I choose do do cells[(0,0)].update() 10 times in a row it should still work.
Here's the updated version: http://pastebin.com/f72c576d3
This fix took 5 minutes. I actually used a gen counter and self.state[self.gen%2] before, so changing that to %3 wasn't much work :)
The other change was:
And I removed the code do delete empty cells. I thought about removing empty cells and obviously you can remove them in some cases. But in general it's undecidable I think because life is turing complete and you don't know if some group of cells is going to shoot a glider to another group, so to be safe you have to keep them in sync.Is this version correct now? I'm not sure...it seems to execute the examples correctly but maybe it will go wrong if you call update in just the right pattern.
BTW does the code run on your computer?
That looks better like that.
I can't get it to work though, because of the swing stuff.
I tried running it under jython but that gives me a syntax error, and in regular python the I get an import error. ('No module named javax').
I can't verify if it is correct without being able to run it, but you can try that F pentomino and then use 'hashlife' or 'golly' to verify that it works properly.
The F pentomino is complex enough in its output that I think that if it does that it will work on arbitrary patterns.
As for deletions, since this is only a simulation it is an optimization, in an actual fabric you would not be deleting cells.
The trick to deletions I think is that you can only delete a cell if the neighbours around it are not going to be disconnected by the deletion.
Now you have a problem though, which needs supervision or abtration. This is because if two cells delete themselves at the same time that could cause two populations to become disconnected.
That's exactly the kind of issue I tried to resolve by scheduling the instructions so carefully.
So, I'm curious if it really works for more complex structures.
All you'd need to do is change the default set and let it run for 1116 generations , then it should be stable.
Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
The F-pentomino works, but it is VERY slow because gliders fly away and this increases the number of cells a lot O(generation) space and O(generation^2) time.
> Oh, and I think %3 should be %4, %3 is somewhere between 1 and 2 bits and you really need two bits.
Hmm. Two cells that are next to each other can never be more than 1 generation apart, right? For example if we have cells AB then if A is in generation 10 then B can be in generation 9, 10 or 11. This happens when we call update on A:
- if B is in generation 9 we do nothing
- if B is in generation 10 we use its current value
- if B is in generation 11 we use its previous value
So really you only need to remember 2 generations (current and previous). So that would be gen%2 instead of gen%3 or gen%4...what am I missing?
When two adjacent cells are only 1 generation apart that can lead to a cell being created that is two generations away from a neighbour. It took me a while to clue in to what was happening there.
So you are correct in that you only need the two states stored, that is fine.
But the generation counter needs to have at least two full bits. 1.5 bits isn't a value to begin with in electronics, and when two populations that are synchronized via some tenuous link meet you need to guarantee that there will not be a mis interpretation of the states. For instance (not sure if this will come out ok):
Is consistent. Now if an empty cell is created between the topmost 3 and 0 it would depend on which cell caused the creation how it would interpret the value of its neigbour.In a 'true' fabric this would not occur (because all the dead cells would exist at all times), so in this case it is an artifact of the creation of cells.
But in logic there would be no way to know who is 'ahead' when counting from 0 to 2 only, that's why you need the third possibility (modulo 3 counting), which when you make it simple hardware automatically becomes modulo 4 (otherwise you get a whole pile of gates more to use less state!).
So the generation counters would end up being 2 bits each, or two bits with a 'reset' happing at the fourth state, effectively making them 3 positions, each output from the two bit counters would go in to a 1 selected output for 4 bits input (so 16 outputs, or in your 1.5 bits case 1 out of 9) demultiplexer which would select the right combination of previous/current generation states to be used.
That's quite doable. So the effect would be completely free-running life cells that stay within one step of all their neighbours at all time.
It is very tempting to actually go and wire this up.
edit: hm, I see I'm contradicting myself here, you are right, a count of 3 should be sufficient in actual logic, it is the imperfection of the simulation that causes the problem, if all cells existed at all times 3 would be enough. But it would still require two lines for the generation to be transmitted to the neighbours.
So, in summary: two states, but 3 possibilities for the generation counter. Otherwise you can't tell who is ahead or behind, then 'different' is all you've got and you can't make the decision to wait.
Correct ?
thanks!
Yes I think that's right. If all cells exist 2 possibilities for the generation counter is not enough, but 3 possibilities is. For example this rule works:
If you have non existing cells the generation counter needs to be able to go arbitrarily large (which is why it does in my program): Lets go back to the situation where all cells exist.In the game of life cells can only have 2 states (live or dead). In the asynchronous version they have 6 states: 2 for dead/alive * 3 for the generation counter. You could view the asynchronous version as another cellular automaton (with more possible states and different update rules).
I think you can write a procedure that takes the rules of a synchronous cellular automaton and returns a new cellular automaton that is the asynchronous version of the original.
So you could structure the program like this:
1) A function to convert an automaton to its asynchronous version
2) An asynchronous cellular automaton simulator. Instead of updating all cells in sync it updates randomly.
Edit: it's not hard actually. If the original has n states then the new one has 3n^2 states. The update rules are straightforward, but you get a huge number of them. E.g. for the game of life the original automaton has 2^9 rules (one for every possible 3x3 grid), and the asynchronous version has 12^9 rules.
Super stuff.
Ok, now to go and design the thing, you game ?
If so drop me an email. It's been a long long time since I've done gate level logic but this is a very interesting little project.
Do you mean with real hardware? I have never done any hardware stuff, but I'd like to learn. Where do I start? :)
Can you send me an email please, j@ww.com
This thread is getting overlong and is about to go out of sight for me, it's already on one of the last pages of my comment history.
Here's a screenshot: http://img715.imageshack.us/img715/2976/asynclife.png
The end state of golly and this seem to match up but I only eyeballed it (it seems highly unlikely that the end state would be this similar but not exactly the same).
I'd like to participate, and I don't want to look at your PHP. Can you elaborate on what needs to be implemented?
Do I have this right:
- use linked objects for the cells instead of an array
- a method to bring a cell to the next generation, this method recursively calls itself on the neighbors
- live cells should be created on the fly, growing the "grid" (non rectangular) as necessary
Almost, the recursion is only used when creating new cells, other than that it is all simple iteration.
Basically the 'cell creation' is a shortcut used because I didn't want to start off with a fixed size array of cells.
Each cell operates independently of its neighbours.
Nice to have a taker!
It's a small enough project that you can do it in a day and it is large enough to get some insight into the various ways of solving things with different languages.
I'm really curious what your code will look like and what language you will write it in.
Please let me know when you're done, email in my profile.
Ok, so the main loop is like
And update looks at the values of the neighbors and updates accordingly. Seems straightforward, but I'm sure there will be pitfalls :)I'm going to start in about 4 hours, I have other work to do now.
Yep, you got it.
I see several problems with this:
If you start with two disconnected cell groups, how do you know when they collide? It seems like the best way to do this is to have a global cell array (or hash table) such that world[position] returns the cell at position.
If you update separate groups at different speeds you run into problems unless you save the complete history. So you still have to update everything in sync? Then what is asynchronous about this?
> If you start with two disconnected cell groups, how do you know when they collide?
You create 'dead' cells in between that connect the two populations.
That's also why you can't remove them. Remember, this is a simulation of a fabric, the dead cells not being there all the time is an optimization, in a real fabric all cells would exist all the time.
The async component is the fact that there is no global authority supplying a clock, each 'peer' is on its own from the moment of power-up.