'Tetris' Recreated In Conway's 'Game of Life' (stackexchange.com) 87
In 1970 mathematician John Conway created rules for the "Game of Life," a now famous "zero-player game" where a grid of cells evolves (following Conway's rules) from an initial state proposed by the player. In 2013 someone challenged readers of StackExchange's "Programming Puzzles & Code Golf" section to devise an initial state "that will allow for the playing of a game of Tetris."
An anonymous Slashdot reader reports that "This challenge sat around, gathering upvotes but no answer, for four years. Then, it was answered." Citing the work of seven contributors, a massive six-part response says their solution took one and a half years to create, and "began as a quest but ended as an odyssey." The team created their own assembly language, known as QFTASM (Quest for Tetris Assembly) for use within Conway's mathematical universe, and then also designed their own processor architecture, and eventually even a higher-level language that they named COGOL. Their StackExchange response includes a link to all of their code on GitHub, as well as to a page where you can run the code online.
One StackExchange reader hailed the achievement as "the single greatest thing I've ever scrolled through while understanding very little."
An anonymous Slashdot reader reports that "This challenge sat around, gathering upvotes but no answer, for four years. Then, it was answered." Citing the work of seven contributors, a massive six-part response says their solution took one and a half years to create, and "began as a quest but ended as an odyssey." The team created their own assembly language, known as QFTASM (Quest for Tetris Assembly) for use within Conway's mathematical universe, and then also designed their own processor architecture, and eventually even a higher-level language that they named COGOL. Their StackExchange response includes a link to all of their code on GitHub, as well as to a page where you can run the code online.
One StackExchange reader hailed the achievement as "the single greatest thing I've ever scrolled through while understanding very little."
Re: (Score:2)
It will provide insight into development of other more advanced projects.
Re: (Score:2)
I think CA is by far the most interesting thing being done today in math and physics.
Re: (Score:2)
I agree. Life was a popular topic even back in the 1970's with low res screens. Writing simulators using VGA graphics modes and graphics accelerators was always the first things I did. Going beyond CA, there are 3D reaction diffusion equations.
Re: (Score:2)
Re: (Score:1)
The people involved have gained insight and experience, but the state of the art has not advanced significantly to have an assembly language implemented in Life metacells. It was already widely known that it could be done. It's a curiosity, like writing a Brainfuck JIT compiler or a .mod player in bash, both of which I've done just to see if I could.
Why climb a mountain? Because it's there.
What is useful? (Score:5, Interesting)
Eventually entropy will destroy the universe. Even if you've survived normal human mortality, the end of the Earth, and the end of the Sun (etc, etc, etc)... ultimately absolutely nothing you've ever achieved will have any significance whatsoever.
These guys had fun doing something difficult just to do it, and they didn't hurt anybody else in the process. THAT is actually the most significant thing you can manage in our universe. Just deal with the fact that you're less important than they are and get on with the remainder of your meaningless existence.
Re:What is useful? (Score:5, Interesting)
I wasted thousands of hours writing simulations on a computer as a kid with no money to buy games and it landed me many very lucrative jobs throughout my life. If I was 30 years younger, this is exactly the type of stuff that I'd be doing.
Re: What is useful? (Score:1)
What the hell are you talking about? This is nothing like the invention of the transistor, and is rather different than any physical invention/construction in general.
With math and many computer topics, if some one shows you can get from A to B, and someone else shows you can get from B to C, then it is obvious you can get from A to C. In this case, it has already been well demonstrated that you can make a general purpose computer in GoL with displays, and we know Tetris can be implemented on a computer. Co
Re: (Score:3)
it was a tremendous waste of time
Americans collectively spend about 800 billion hours per year watching TV. If you want to criticize people for wasting time, there are better targets than this handful of coders.
They are doing nothing to help cure cancer, but neither is any artist, poet, dancer, novelist, or musician. Should we also criticize those people for "wasting time"?
Re: (Score:2)
It's arguably not more useless than stamp collecting...
Re: (Score:2)
One fascinating aspect of Conway's Game of Life is that it's DNA-like in that introducing mutations (flip a few cells at random) can have both small and very wide reaching consequences, and even a chance of causing unintentional improvements. If bundled with a reproductive system and evolutionary pressure, it could be the basis for a new type of actual life. Even supporting parasites and symbiosis. That's what's fascinating, and makes this prime AI material.
Re: (Score:2)
Re: (Score:3)
Eventually entropy will destroy the universe. Even if you've survived normal human mortality, the end of the Earth, and the end of the Sun (etc, etc, etc)... ultimately absolutely nothing you've ever achieved will have any significance whatsoever.
Can entropy be reversed? [multivax.com]
Re: (Score:1)
Re: (Score:2)
Eventually entropy will destroy the universe.
[...]
These guys had fun doing something difficult just to do it, and they didn't hurt anybody else in the process.
This is an incredibly wasteful use of CPU time (as you can play tetris without all that stuff) which consumes energy, which means that this project contributes to the heat death of the universe. Mind you, bitcoin is much worse...
Re: (Score:2)
Eventually entropy will destroy the universe.
(Not that it makes any difference to your argument), but when this particular embodiment of entropy comes up (inexorable fate of all matter) I can no longer help but can't help but think about the interesting fact that our existence (biology) contradicts the idea of entropy as a rule that dictates all matter absolutely: biology distils information; a book of tricks, to reduce entropy like Maxwell's demon. https://www.wired.com/2017/02/... [wired.com]
In full relevance to this exploration of CA: The article goes full ci
Re: (Score:2)
contradicts the idea of entropy as a rule that dictates all matter absolutely:
Life doesn't contradict any of the principles of entropy that govern all matter
I know this seems pedantic but: to be clear i did not say it contradicts the principle, but that it contradicts the notion that it dictates the behaviour of matter absolutely. The point being that entropy is simple a description of one if the behaviours of matter and energy, but matter an energy are not simple and so this behaviour can be manipulated through other characteristics. If you read the article which can probably explain the point far better than me, maxwells demon is only lacking in one detail to
Re: (Score:2)
Re: (Score:2)
"something useful"
that is a bad criteria for judging anything, for several reasons. such judges assume too much and are hubristic.
who defines "usefulness"? you? society? based on what data, given there are lots of unknowns and knowledge is never complete? how to decide? majority? will of powerful? those who pay? known immediate needs? speculative long term needs? etc etc.
rather let individuals exercise their free will as they see fit , even if they do something that seems "useless", or in some cases even "
Re: (Score:3)
Just think of what could have been achieved if they had put that effort into something useful.
Like posting on Slashdot? You really showed them.
Life is Turing complete (Score:4, Interesting)
Conway's game of Life has been shown to be Turing Complete [wikipedia.org], so it can do anything any computer can do. You can use glider generators to construct a NAND gate, and then use NAND gates to construct any logic circuit, including a CPU.
Someone should write a compiler to run arbitrary software inside the automaton system.
Re: (Score:2)
Someone should write a compiler to run arbitrary software inside the automaton system
...maybe you could run a Game of Life in it? You know, just for fun.
Re:Life is Turing complete (Score:4, Interesting)
https://www.youtube.com/watch?v=xP5-iIeKXE8
Re: (Score:2, Funny)
No, no. They need to run The Game Of Life [hasbro.com].
Re: (Score:1)
I'd like to see it nested a few times. Turtles allll the way down.
Re: (Score:2)
Re: Life is Turing complete (Score:2)
Re: (Score:3)
They're already working on a gcc backend, so the languages GCC can compile could be compiled to run on their architecture.
Re: (Score:2)
You can use glider generators to construct a NAND gate, and then use NAND gates to construct any logic circuit, including a CPU.
You should read the stack exchange post. They go through all of that including wires, delays, muxes, ROMs, latches, with those you then make RAM, ALUs, and finished with an entire RISC processor.
Re: (Score:2)
Someone should write a compiler to run arbitrary software inside the automaton system.
That's exactly what they did do... built up layers of abstraction, it's an interesting project.
The building blocks of our logic gates (transistors) are a particular kind of abstraction that we don't usually have to delve into with electronics, and even than are logically simple and more statistically squishy inside... whereas with CA there is none of the same science, it's a strange logical challenge to built a transistor, a transistor might not even be a particularly productive abstraction to make - buildi
Re: (Score:2)
They made all the standard logic gates, but implementing a NOT with CA is tricky because there is no signal coming down. If a glider is the 1 bit, then no glider is the 0 bit, so you need something that acts as a timer and sends out a glider if no bit is received.
There were some designs for hardware that made use of incremental changes or even asychronous updates and thus eliminate the need for clock lines.
NERDS (Score:2)
How can I see the underlying Game-of-Life? (Score:3)
I'd also love to see their VM running!
Re:How can I see the underlying Game-of-Life? (Score:4, Informative)
Re: (Score:1)
Well, the problem is the scale. The final Tetris running Game of Life has a bounding box of 2,940,928 x 10,407,936 cells. And it's just a regular grid of OTCA metapixels. Basically looking at the low level GoL is like looking at a microprocessor at the atom level.
You can see an OTCA cell working here:
http://www.conwaylife.com/wiki/OTCA_metapixel
The whole thing is just this multiplied by 1,221,941 OTCA cells being actively used in the final version.
Re: (Score:2)
Re: (Score:2)
It's interesting to see the use of hashing to optimize the computations of the Life grid, especially the metapixels (which are like FPGA cells). Which basically reduces everything down to lookup tables.
Re: (Score:2)
Running it in Golly on my PC right now it maxes out at 4-5 million generations/second with a step size of 8^6, periodically slowing down presumably to hash some new cell configuration. It uses ~550MB of RAM. I've run the other metapixel patterns that come with Golly, but this one is mind blowing to see.
Ironically, there's not much to look at, since there doesn't seem to be a display of the Tetris board built in.
Obligatory XKCD... (Score:3)
https://xkcd.com/505/ [xkcd.com]
Conway's Game of Life is indeed Turing Complete (see also: A New Kind of Science [amazon.com]) and this is indeed pretty awesome that they were able to do this...
Re: (Score:2)
Yes, I took a look at TFA and although they didn't go about simulating the "universe" from basic laws (not that we have a theory of everything yet :) they DID start at the (sort of) particle level using something called OTCA megapixels. From these they built the fundamental logic gates and from that a (simple?) computer and from that a (simple?) language and (simple?) compiler and then wrote and compiled and ran a (simple, no colors or audio?) Tetris program!
So if anyone tells you they don't believe that w
Re: (Score:2)
Graduation from Redstone University (Score:2)
This is the next step on the career ladder for enterprising redstone engineers everywhere. Anyone who can design a CPU in Minecraft should be able to do it in GoL, if they have all the extensions. The lack of a NOT gate is a bit of a pisser, but can be worked around. It seems to me if you really want a NOT gate, you can use an XOR gate and constantly pull one line high. Maybe they don't have any ways to constantly pull a line high either.
Seriously though, I would not be surprised at all if the major contrib
The next challenge.... (Score:2)
OK, time for the next challenge. Once GCC is done, port Doom to the GoL, it is open sourced so.... Since speed is indeed an issue, part 2 of this challenge is to compile it to an FPGA so it runs at a decent speed. :)
Please note there is no rush for this challenge, next week will be just fine.
How long till the lawsuit? (Score:2)
I thought using the 7 standard pieces in a Tetris clone was ruled in 2012 to be a copyright infringement [slashdot.org].
Re: (Score:2)
Stack Exchange gives credit to the author of every question and answer. It's a requirement of the Creative Commons Attribution-ShareAlike license under which contributors offer their work.
As for "profit", are you talking about a paywall? Because people use tracking blockers nowadays to keep ad networks from stalking them with "retargeting", and unless you sell your own site's ad space directly to advertisers, you won't see a dime from them. Or what am I missing?
Re: (Score:1)
This comment has been closed as non-constructive. Due to the number of low quality replies, over 9000 internet points are required to post reply.
Tetris' ? (Score:2)
> 'Tetris' Recreated In Conway's 'Game of Life'
OK, it is late, but I have read that a dozen times now and I don't quite understand. "Recreated" belongs to one or possibly more than one Tetris? What kind of English is that? Are they trying to make a contraction like "Tetris is" by adding a trailing apostrophe?
Re: (Score:3)
>"OK, it is late, but I have read that a dozen times now and I don't quite understand."
And now I see the problem- the freaky font blended the leading apostrophe into the "T." I wish I could post a screenshot of it; it really is quite amazing.
I need to go to bed :)
If they can do all that (Score:1)
Sharks and Fish (Score:2)
Does anyone else remember the game "Sharks and Fish", source came out in Byte Magazine I think back in the 80's. Very interesting, and turns out it replicates the ebb and flow of the populations of lynx and rabbits as tracked by Canadian Fur Company trapping statistics back in the 1700's :-)
Much more interesting than Conway's Life, I always thought. I hacked it, of course, to add plankton, whales, porpoises, and things got quite interesting then :-)
Re: (Score:2)
There's an old game called "matrem" out there that can create those graphs pretty well, I think. It's lions eating cows.
Re: (Score:2)
One of the demo programs on the Sinclair Spectrum was Foxes & Rabbits. Sounds like a similar concept.
How do you control the blocks? (Score:1)
I couldn't figure out how to actually move or rotate the blocks. Arrow keys, WASD,...? No effect. So the blocks just seem to scroll down in the middle and stack up.
The authors don't seem to mention the controls, except something about "manually editing the contents of RAM address".... ??
Doesn't "allow for the playing of a game of Tetris" mean that you can actually, y'know, *play* Tetris?
Re: (Score:2)
The controls are that you enter a value into a specific RAM address. The game reads then clears that value, and moves or rotates the block based on the value.
Clunky, but somewhat easier than writing a keyboard driver.
Totally disappointed (Score:2)
Systemd (Score:1)
Can't systemd play tetis and life already?
well someone had to say it.
Impressive feat of programming (Score:2)
This is really awesome. Now that you are started, could you switch to the Game of Half-Life? Some people are waiting.