Conway's Game of Life Implemented in Conway's Game of Life (opens in new tab)

(youtube.com)

68 pointsZhuanXia5y ago5 comments

5 comments

Lots of interesting software around Conway's Game of Life. Here is Hashlife [1], where the states of living organisms are hashed; sometimes enabling prediction of all future states.

It helps trading-off computation with space, sort of like Halide [2] does.

I've been playing a bit of Factorio with the social distancing recently. The bottleneck of mega-bases is often compute power. I wish the developers could implement something akin to Hashlife. The bases are made of the same repeated patterns, all possible states of which could be memoized. This could be the next step in automating to a higher scale.

[1] https://en.wikipedia.org/wiki/Hashlife

[2] https://halide-lang.org/

klyrs5y ago

Factorio has some real challenges to it -- ticks are extremely fine, and for example, the speed of an inserter is dependent on availability of electricity. Combine such aspects with, say, the plurality of materials which may be on a belt. I fear that the plurality of possible states would move the problem from being compute-bound to being memory-bound.

BenoitP5y ago

Yep, such details would eat memory at a fast pace. However, non 100% electricity and non backed up belts could be considered an "off the main path", and be resolved computationally; sort of like the Java JIT deoptimizing an edge case and going back to the interpreter mode.

Players would then strive to make stable, robust bases with as few states as they can. Failing to do so would mean the slow path, and their factory struggling to progress in IRL time.

The optimizing limit doesn't have to be a hard-coded threshold, it could be defined as a cache with a limited capacity.

_56595y ago

The way I understand why this is possible is due to the fact that Game of Life is Turing Complete, and can therefore construct a Universal Turing Machine capable of simulating itself.

3pt141595y ago

Well, kinda. This is an intentionally visual representation, but it could just have been a rules set that builds a series of gates that create a computer that does the calculations for the game without actually rendering it. Basically seeing the game isn't necessary, though this is pretty awesome.

j / k navigate · click thread line to collapse

5 comments

BenoitP5y ago

Lots of interesting software around Conway's Game of Life. Here is Hashlife [1], where the states of living organisms are hashed; sometimes enabling prediction of all future states.

It helps trading-off computation with space, sort of like Halide [2] does.

[1] https://en.wikipedia.org/wiki/Hashlife

[2] https://halide-lang.org/

klyrs5y ago

BenoitP5y ago

Players would then strive to make stable, robust bases with as few states as they can. Failing to do so would mean the slow path, and their factory struggling to progress in IRL time.

The optimizing limit doesn't have to be a hard-coded threshold, it could be defined as a cache with a limited capacity.

_56595y ago

The way I understand why this is possible is due to the fact that Game of Life is Turing Complete, and can therefore construct a Universal Turing Machine capable of simulating itself.

3pt141595y ago

j / k navigate · click thread line to collapse