Conway's Game of Life, using floating point values instead of integers(jwz.org)
jwz.org
Conway's Game of Life, using floating point values instead of integers
http://www.jwz.org/blog/2012/10/smoothlifel/
27 comments
Very cool, thanks for the links! Are you affiliated with the project?
I made an implementation of SmoothLifeL in Ready and this video. Stephan Rafler created the SmoothLife rules and has his own software. Ready is designed to let the user play with a large range of systems like this one, connecting a field of floats to an OpenCL kernel that the user can rewrite on the fly. Check out Ready for some similar patterns, like Robert Munafo's U-Skate world.
http://code.google.com/p/reaction-diffusion
There's a deep motivation behind all this, which is to try to understand the pattern formation mechanisms that appear in nature and get harnessed by organisms.
http://code.google.com/p/reaction-diffusion
There's a deep motivation behind all this, which is to try to understand the pattern formation mechanisms that appear in nature and get harnessed by organisms.
Does anyone have a JavaScript implementation of the paper? It looks like it would be really fun to play with in <canvas>.
Edit Quoth YouTube: "74 minutes on an nVidia GeForce GTX 460" ... maybe not so fun.
Edit Quoth YouTube: "74 minutes on an nVidia GeForce GTX 460" ... maybe not so fun.
Here you go: http://jsfiddle.net/CSyUb/
Good job. Any idea why using the parameters specified in the video description of https://www.youtube.com/watch?v=KJe9H6qS82I do not seem to replicate the output of the video? http://jsfiddle.net/CSyUb/45/
I tried the same parameters in the version downloadable at http://sourceforge.net/projects/smoothlife/ and it did not seem to produce similar output to the video either.
I tried the same parameters in the version downloadable at http://sourceforge.net/projects/smoothlife/ and it did not seem to produce similar output to the video either.
The SmoothLifeConfig.txt doesn't have a line for SmoothLifeL - it should, Stephan!
Here it is:
2 1 10.0 3.0 10.0 0.100 0.257 0.336 0.365 0.549 2 4 4 0.028 0.147 // SmoothLifeL
Put this at the top of SmoothLifeConfig.txt and run the exe.
You'll notice that some of the parameters (the 2 4 4) control the transition function. This is different to the version in the paper which is smoothglider (which is in the config file) which uses 4 4 4.
Here it is:
2 1 10.0 3.0 10.0 0.100 0.257 0.336 0.365 0.549 2 4 4 0.028 0.147 // SmoothLifeL
Put this at the top of SmoothLifeConfig.txt and run the exe.
You'll notice that some of the parameters (the 2 4 4) control the transition function. This is different to the version in the paper which is smoothglider (which is in the config file) which uses 4 4 4.
They are using smooth time integration, where I am using the discrete scheme described in the arxiv paper. The switch isn't that difficult though, since it just involves modifying a single line of the shader.
Another thing about the 74 minutes. That was for a larger radius than necessary and a smaller timestep than necessary - for a high quality video.
With a radius of 10.0 and a timestep of 0.1 I get 186fps on the same graphics card - visually about the same speed as the youtube video.
With a radius of 10.0 and a timestep of 0.1 I get 186fps on the same graphics card - visually about the same speed as the youtube video.
But you missed the most important part of that quote.
>"(in Ready, Stephan's software at the sourceforge link above runs much faster)"
So using Ready it took a long time, but the actual code is much faster. I'd imagine you could write something in CUDA that would run this (and only this, not something generalized like Ready) plenty fast to do real time rendering on a new system, especially considering a GTX 680 has almost 5x the horsepower of a GTX 460.
Admittedly not in a web browser though.
Admittedly not in a web browser though.
"Admittedly not in a web browser though."
HTML5 gives you WebGL support, which allows you to compile and run GLSL shaders from JavaScript. For something that is heavily shader-oriented like this, it might be possible in the browser.
HTML5 gives you WebGL support, which allows you to compile and run GLSL shaders from JavaScript. For something that is heavily shader-oriented like this, it might be possible in the browser.
Ready is using OpenCL. But Stephan is using FFT for the convolution with a disk filter, which is a big win for large radii.
As far as I'm aware OpenCL performance, while portable, is still somewhat inferior to that of straight CUDA on NVIDIA GPUs, hence my CUDA suggestion. I didn't actually look at the algorithms used in either so I can't comment, perhaps I'll do that tomorrow. What do you mean by using an FFT "for" a convolution? The algorithm is convolving the (presumably 2D) FFT of the game board with a disk filter?
SmoothLife uses two disks around each point to determine the instantaneous rate of change. Inside each disk the values are summed. This is a convolution with a disk filter.
http://en.wikipedia.org/wiki/Convolution
As it says on that page, FFT is often used for convolution because it is fast: after applying a discrete Fourier transform to the kernel and the image, the resulting images must only be multiplied together before applying an inverse FFT.
http://en.wikipedia.org/wiki/Discrete_Fourier_transform
http://en.wikipedia.org/wiki/Convolution
As it says on that page, FFT is often used for convolution because it is fast: after applying a discrete Fourier transform to the kernel and the image, the resulting images must only be multiplied together before applying an inverse FFT.
http://en.wikipedia.org/wiki/Discrete_Fourier_transform
Ah, thanks for the information. I'm familiar with signal processing, so the only way I'm used to seeing convolutions is through the multiplication of FFTs. I wasn't even considering the "regular" way.
That's so cool. I love to see real world applications of convolutions.
I wonder if there is an application of Gershgorin's Disc theorem here?
I wonder if there is an application of Gershgorin's Disc theorem here?
I see something about a circle that contains the eigenvectors of a matrix. How does that apply here?
WebCL?
Fascinating, totally mesmerizing video. That's reminiscent of something that you could be observing under a microscope.
I wonder what a 3D version (http://www.ibiblio.org/e-notes/Life/Game.htm) of a continuous game of life would look like... could similar cell-like structures emerge with these kind of rules also in 3D.
SmoothLife has been generalized to 3D too: http://www.youtube.com/watch?v=7RsEyu8Ol-Q&NR=1
Possibly of similar interest - Ready, a program for exploring continuous valued cellular automata: http://code.google.com/p/reaction-diffusion/
Aren't cellular automata in continuous space just PDE's? If so, what is the equation being integrated?
EDIT: found the paper: http://arxiv.org/pdf/1111.1567v2.pdf
EDIT: found the paper: http://arxiv.org/pdf/1111.1567v2.pdf
Not quite; the values at every point are boolean, not floats.
(From the link) The algorithm is explained here: http://www.youtube.com/watch?v=iyTIXRhjXII
(From the link) The algorithm is explained here: http://www.youtube.com/watch?v=iyTIXRhjXII
It's confusing because several algorithms are explained, but I believe they're actually floats in this version.
Also it's not a normal PDE because ∂f/∂t is permitted to be an arbitrary functional of f restricted to a fixed-diameter neighborhood of the point, not just an infinitesimal neighborhood.
Also it's not a normal PDE because ∂f/∂t is permitted to be an arbitrary functional of f restricted to a fixed-diameter neighborhood of the point, not just an infinitesimal neighborhood.
That's the case for our universe as well, for example d^2x/dt^2 due to gravity for a piece of material is dependent on all other material in the universe.
Not instantaneously: https://en.wikipedia.org/wiki/Speed_of_gravity
So the Schrodinger equation isn't quite accurate then?
Does the Dirac equation take this into effect?
Does the Dirac equation take this into effect?
You can think of modern physics as a bit like a cube:
It branches out along the three axes:
1) Add mutual gravitation, giving you the theory of Newtonian celestial mechanics (in which gravity acts instantaneously)
2) Add relativistic effects, giving you Einstein's theory of special relativity (there is a finite upper limit to all communication, the speed of light)
3) Add quantization, giving you 1920s era quantum mechanics, as described by the Schrodinger equation.
We know how to combine any two of these:
1/2) Combining gravitation and relativistic effects gives you Einstein's theory of General Relativity. In this theory, gravitational effects travel at the speed of light.
2/3) Combining relativity and quantum mechanics gives you quantum field theory and the Standard Model. This encompasses the Dirac equation, which is a quantum relativistic theory of fermions (i.e. matter particles).
1/3) Combining gravity and quantum mechanics gives you... well, it's kind of boring and we don't talk about it much, but you get a quantum theory with gravitation, but no relativistic effects. No one really studies this.
Combining all three is the holy grail of physics:
1/2/3) Often called `quantum gravity` or the `theory of everything`, this is the as yet nonexistent theory that can explain both very small and very massive (in the sense of having a large mass) objects, like black holes or the early universe.
1/3_____1/2/3
/| /|
/ | / |
1------1/2 |
| 3____|__2/3
| / | /
|/ | /
0-------2
It branches out along the three axes:
1) Add mutual gravitation, giving you the theory of Newtonian celestial mechanics (in which gravity acts instantaneously)
2) Add relativistic effects, giving you Einstein's theory of special relativity (there is a finite upper limit to all communication, the speed of light)
3) Add quantization, giving you 1920s era quantum mechanics, as described by the Schrodinger equation.
We know how to combine any two of these:
1/2) Combining gravitation and relativistic effects gives you Einstein's theory of General Relativity. In this theory, gravitational effects travel at the speed of light.
2/3) Combining relativity and quantum mechanics gives you quantum field theory and the Standard Model. This encompasses the Dirac equation, which is a quantum relativistic theory of fermions (i.e. matter particles).
1/3) Combining gravity and quantum mechanics gives you... well, it's kind of boring and we don't talk about it much, but you get a quantum theory with gravitation, but no relativistic effects. No one really studies this.
Combining all three is the holy grail of physics:
1/2/3) Often called `quantum gravity` or the `theory of everything`, this is the as yet nonexistent theory that can explain both very small and very massive (in the sense of having a large mass) objects, like black holes or the early universe.
Could you elaborate a bit on your point 1/3? How come the little interest in this subject? Even though it contains no relativistic effects it would seem to have some importance in filling out the complete 'cube' of theories?
The equations you end up with are called the Schrodinger-Newton equations [1]. These are the same as Schrodinger's equation, but with an extra term that couples the wavefunction to a global gravitational field via its mass.
I'm not an expert, but possible reasons for the relative lack of interest in these equations include:
1. It doesn't produce many interesting predictions (possible exception: it might be useful for explaining how gravitational effects can induce wavefunction collapse, but this appears to be highly speculative.)
2. There isn't a natural domain of applicability. For example, combining 1/2 (gravity and relativity) has a natural applicability to things that are heavy and move fast (i.e. stars, galaxies, the universe). Combining 2/3 (relativity and quantum mechanics) applies to things that are small and move fast (electrons and other fundamental particles). The domain of applicability of 1/3 would be things that are small and heavy, but move slowly. I can't think of any examples of things that fit the bill (note that 1/2/3 applies to things that are small, heavy and move quickly, i.e. black holes).
When I say "move quickly" here I don't necessarily mean that the object you're modelling must be moving quickly - just that there are speeds in the problem that are appreciable fractions of the speed of light.
[1] http://en.wikipedia.org/wiki/Schr%C3%B6dinger%E2%80%93Newton...
I'm not an expert, but possible reasons for the relative lack of interest in these equations include:
1. It doesn't produce many interesting predictions (possible exception: it might be useful for explaining how gravitational effects can induce wavefunction collapse, but this appears to be highly speculative.)
2. There isn't a natural domain of applicability. For example, combining 1/2 (gravity and relativity) has a natural applicability to things that are heavy and move fast (i.e. stars, galaxies, the universe). Combining 2/3 (relativity and quantum mechanics) applies to things that are small and move fast (electrons and other fundamental particles). The domain of applicability of 1/3 would be things that are small and heavy, but move slowly. I can't think of any examples of things that fit the bill (note that 1/2/3 applies to things that are small, heavy and move quickly, i.e. black holes).
When I say "move quickly" here I don't necessarily mean that the object you're modelling must be moving quickly - just that there are speeds in the problem that are appreciable fractions of the speed of light.
[1] http://en.wikipedia.org/wiki/Schr%C3%B6dinger%E2%80%93Newton...
There are a few experiments that combine Newtonian gravity and quantum mechanics (1/3).
For example you can split a ray of neutrons, direct each beam throu a different path with different height and then make them collide and see the interference pattern. (The details are in the book of Sakurai "Modern Quantum Mechanics" pp127-129, with data from an experiment of Colella, Overhauser, Werner (1975).)
It is possible to create systems that combine 1/3, but they are almost corner cases and most of the time the other combinations are more useful.
For example you can split a ray of neutrons, direct each beam throu a different path with different height and then make them collide and see the interference pattern. (The details are in the book of Sakurai "Modern Quantum Mechanics" pp127-129, with data from an experiment of Colella, Overhauser, Werner (1975).)
It is possible to create systems that combine 1/3, but they are almost corner cases and most of the time the other combinations are more useful.
That's awesome! My project inspired by the Game of Life is quite a bit less ambitious (and still incomplete) - http://nickknowlson.com/projects/conways-revenge/
It lets multiple cell colonies fight against each other using a modified ruleset.
It lets multiple cell colonies fight against each other using a modified ruleset.
Cool! I've been wanting to do this for some time and haven't gotten around to it.
Pinchyfingers submitted this link:
(http://news.ycombinator.com/item?id=4642628) which goes to a Youtube video of a game of life in a single line of APL. It's a really nice description of the code too. (It's a sale pitch for dynalog - but the best kind where they're just using the tool to do something neat and not pushing their URLs at you.)
(http://news.ycombinator.com/item?id=4642628) which goes to a Youtube video of a game of life in a single line of APL. It's a really nice description of the code too. (It's a sale pitch for dynalog - but the best kind where they're just using the tool to do something neat and not pushing their URLs at you.)
I've watched that video several times and it never occurred to me that it was a sales pitch.
That's the best kind of sales pitch. Don't sell it. Just show it. People who want it will be grateful not to have it pushed at them, and people who don't want it will watch it and share it with others, and those other people might want it.
Have you googled "conway's game of life" recently?
Yes. Google has nice animation =)
https://www.google.com/search?q=Conways+Game+of+Life&sug...
https://www.google.com/search?q=Conways+Game+of+Life&sug...
It looks like cells under the microscope. Very interesting stuff.
Awesome, but the results/behaviour (in the video) don't seem very complex like the original Conway's game of life.
It does seem more "organic", if you will.
It does. Still I think the point of game of life is not to look organic but to make complex thing from very simple rules. Like supposedly the universe we live in. Conway's game of life would look organic if you zoomed out enough, no computer can do that of course.
Well, generations don't have to be rendered in realtime, so you could just grab some high cpu instances on AWS and compute really large sizes. For example, this guy made a turing machine, and it's pretty huge: http://rendell-attic.org/gol/tm.htm
And that was in 2000. I'm sure we could do extremely large boards now.
And that was in 2000. I'm sure we could do extremely large boards now.
> Conway's game of life would look organic if you zoomed out enough,
Are you sure? This isn't obvious to me.
Are you sure? This isn't obvious to me.
check out hashlife and some of the larger landscapes.
Thank you, mind blown! Downloaded "Golly" (http://golly.sourceforge.net/) and ran HashLife/metapixel.
Life simulating life, and it runs in real time.
Life simulating life, and it runs in real time.
Mind blown pretty much describes what I felt like when I first came upon it.
After spending a good bit of time optimizing 'life' having your ass handed to you by a large number of orders of magnitude courtesy of mr. Norvig is a good lesson in humility.
After spending a good bit of time optimizing 'life' having your ass handed to you by a large number of orders of magnitude courtesy of mr. Norvig is a good lesson in humility.
hashlife is a pretty brilliant algorithm. basically it sort of memoizes patterns at different scales. highly recommended to check out the details of how it works.
> no computer can do that of course
Just check the frontpage again in a few years.
Just check the frontpage again in a few years.
"Make complex things from simple rules" - that's pretty much defining organic in this sense.
no computer can do that of course.
we are getting there - http://www.youtube.com/watch?v=xP5-iIeKXE8
we are getting there - http://www.youtube.com/watch?v=xP5-iIeKXE8
Outstanding, thank you for this. Worth a post on its own don't you think?
It had one, 4 months ago. No comments, only 4 points.
(http://news.ycombinator.com/item?id=4014078)
I think I've seen it before that too, from HN.
(http://news.ycombinator.com/item?id=4014078)
I think I've seen it before that too, from HN.
That's the video in the same blog if you click "Previous": http://www.jwz.org/blog/2012/05/turtles-all-the-way-down-or-...
And you can run that in real time on a desktop. The secret is a hash life approach.
>It does. Still I think the point of game of life is not to look organic but to make complex thing from very simple rules.
Em, it's called "Game of Life" because the whole point was for it to look and behave _organic (Wikipedia: "Conway was interested in a problem presented in the 1940s by mathematician John von Neumann, who attempted to find a hypothetical machine that could build copies of itself").
Em, it's called "Game of Life" because the whole point was for it to look and behave _organic (Wikipedia: "Conway was interested in a problem presented in the 1940s by mathematician John von Neumann, who attempted to find a hypothetical machine that could build copies of itself").
Lifelike might be the term you're looking for... :)
It seems to have much simpler behavior - gliders, bridges, and bricks. Don't think we're going to discover any prime number generators with this version of Life.
Right - can you still build a UTM in this?
If you could, I imagine that the hard part would be proving it correct.
Huh? It looks even more complex --organic even.
You don't confuse the fast rate of change in some Conway implementations (which is a detail) with actual complexity.
You don't confuse the fast rate of change in some Conway implementations (which is a detail) with actual complexity.
I'm not sure if this is as cool as it looks. I guess it's yet to be seen what the larger-scale behavior might be, but it looks like it's just a lot of the same gliders, orbits, and strands between them.
Watching this video makes me wonder if Wolfram's "New Kind of Science" is more worthy of study. There was so much controversy about the book and Wolfram's claims, that I didn't bother with it.
Watching this video makes me wonder if Wolfram's "New Kind of Science" is getting old (like Tetris).
I was actually reading that book at the book store for hours, getting quite intrigued, but at the same time deterred by its size. Perhaps I should give it another shot some day.
I was actually reading that book at the book store for hours, getting quite intrigued, but at the same time deterred by its size. Perhaps I should give it another shot some day.
The general criticism of Wolfram's book is that it's heavy on pictures and self-praise and comparatively light on content. It's certainly very pretty, and has some interesting results (e.g. that Rule 110 is Turing-complete) but a lot of the work is summary or rehash of other extant (and often non-cited) material. There are often more thorough, more concise, and more lucid resources on cellular automata from other research; I'd cite Zuse's Rechnender Raum (Calculating Space) off the top of my head for a work that comes to many of Wolfram's conclusions several decades prior to Wolfram.
In fact, a good strategy for becoming familiar with cellular automata as a field is to read reviews of ANKOS by people with degrees[1], collect the works and authors mentioned, and trawl them. You'll learn a lot about a lot that way.
[1]: http://shell.cas.usf.edu/~wclark/ANKOS_reviews.html has an extensive selection of such reviews.
EDIT: It's also worthy of note here that Wolfram would reject the original post's model as not worthwhile, as ANKOS explicitly argues that we should reject continuous models in favor of discrete models; indeed, that is the very definition of his "new kind of science."
In fact, a good strategy for becoming familiar with cellular automata as a field is to read reviews of ANKOS by people with degrees[1], collect the works and authors mentioned, and trawl them. You'll learn a lot about a lot that way.
[1]: http://shell.cas.usf.edu/~wclark/ANKOS_reviews.html has an extensive selection of such reviews.
EDIT: It's also worthy of note here that Wolfram would reject the original post's model as not worthwhile, as ANKOS explicitly argues that we should reject continuous models in favor of discrete models; indeed, that is the very definition of his "new kind of science."
Note that the proof that Rule 110 is Turing-complete was actually invalid.
(Also, like much of the work in the book, it was written by an uncredited employee rather than Wolfram)
(Also, like much of the work in the book, it was written by an uncredited employee rather than Wolfram)
I knew that the proof was actually Matthew Cook's work, but I didn't realize it was invalid. Can you point me to a citation for that?
I was thinking of http://science.slashdot.org/story/07/10/29/2212226/wolframs-... ; looking again it seems that's a different proof, apologies.
I own the book and have read most of it (not deeply). I'll need to actually study it and have reserved a decent time slot for that next year.
I think the concepts are fascinating but the representation is somewhat meh. Wolfram seems to be quite fond of himself. That ebing said I don't understand why people would not want to read the book because they "don't like" Wolfram.
I recommend it to anyone really it got me thinking about some pretty interesting ideas. Just be open minded and treat it as a "creative tickler" and not a ridid new science :)
I think the concepts are fascinating but the representation is somewhat meh. Wolfram seems to be quite fond of himself. That ebing said I don't understand why people would not want to read the book because they "don't like" Wolfram.
I recommend it to anyone really it got me thinking about some pretty interesting ideas. Just be open minded and treat it as a "creative tickler" and not a ridid new science :)
I need this as a screensaver, asap!
Considering this is the XScreenSaver creator's blog, you might just get your wish.
If you're on a Mac I guess you could hack it rather quickly in Quartz Composer using this as a starting point.
http://quartzcomposer.com/compositions/135-conway-s-game-of-...
Is it Turing complete?
I'd bet it is, but I imagine it would be really hard to prove. The original turing-completeness proof [1] for discreet cellular automata worked by setting up some predictable repeating patterns and then using these to encode a representation of some other simple machine that was known to be turing-complete. Getting anything repeatable out of this would obviously be much harder, as any slight perturbation would cause unpredictable effects (see: chaos theory). However, I haven't read the paper so maybe they have some way of setting up the system that enables repeatability.
1. http://www.complex-systems.com/pdf/15-1-1.pdf
1. http://www.complex-systems.com/pdf/15-1-1.pdf
This is one of the most beautiful things I think I've ever seen simulated. Kudos!
[deleted]
HTML5 implementation in 3, 2...
Surely you mean "pure CSS3 implementation".
How about doing an implementation of smoothlife in conway's life? Might run a bit slow.
[deleted](1)
Well I can't seem to find the rules, but that shouldn't be very difficult.
Might even be able to do it in a way that works without canvas.
Might even be able to do it in a way that works without canvas.
[deleted]
This is fantastic both intellectually and from an artistic point of view.
I'm not a fan of electronic music but the music that was picked for the video was perfect.
I'm not a fan of electronic music but the music that was picked for the video was perfect.
Someone's gonna package this up and sell it as a product, for sure! A 21st century lava lamp.
how close are the rules running here to the standard rules of Conway's Life? I know some of those are supposed to be "gliders" - is it possible to port other shapes from Life into SmoothLife?
Wish the music were as interesting.
Now to try it with complex numbers and/or 3D coordinates.
Hey guys, check out the Conway's Game of Life Code Garage project on LearnStreet: http://www.learnstreet.com/cg/simple/project/conways
I'm not logging in with Facebook to see your site, about which I know nothing, when you haven't even sold me on its relevance to the topic under discussion.
Did you, um, click the links at the top?
I was following a URL that apparently was supposed to go to a specific subpage, not to the site homepage. And apparently there was a loginwall in front of that subpage. What good would clicking around the site have done?
If you think I was going to read all the pages I could access on the site, so that I could ascertain whether it was worth my while to log in, then you grossly overestimate my commitment to a poorly-explained link I clicked speculatively in a comment.
If you think I was going to read all the pages I could access on the site, so that I could ascertain whether it was worth my while to log in, then you grossly overestimate my commitment to a poorly-explained link I clicked speculatively in a comment.
[deleted]
https://plus.google.com/110214848059767137292/posts/WtPBhYJs...
Technical details on the YouTube page:
https://www.youtube.com/watch?v=KJe9H6qS82I
(Two lots of source code available: Stephan's and mine)
Other discussions about this:
Reddit: http://www.reddit.com/r/compsci/comments/118svz/smoothlife_a...
Metafilter: http://www.metafilter.com/120749/Smoothlife