Show HN: I implemented Pong as a cellular automaton | Hacker News Reader

Show HN: I implemented Pong as a cellular automaton

ericu.github.io

225 pointsuranium33 comments

I'd been explaining sonic booms and high explosives to my kids, and thought that showing them a simulation of wavefront propagation might be a fun way to illustrate how they worked. I figured I could do that with a simple cellular automaton, so I threw something together in a few hours, but my sim didn't have anything like the right behavior. So there I was with a general cellular automaton framework, thinking about wave propagation, and wondering what else I could do with it. Inspiration struck, and I just had to try doing this.

Reminded me of a problem set I was once assigned. https://en.wikipedia.org/wiki/Firing_squad_synchronization_p...

Neat--I hadn't heard of that. The wave propagation makes me think back to the problem I was working on the first place.

The nice property of the “firing squad” is that the number states is independent of the length of the firing squad.

I had that one too. I ended up writing some code for it a few years later with a GUI so I could watch how the state changes propagated.

Very impressive! Congrats on shipping!

Thanks! Most of my fun projects tend to be of the fiddle-for-years type, so it was great to find something small enough to polish off in a few months. And of course I had to resist the urge to keep adding to it, but the constraints helped...there are only so many bits to use.

I wish I could give you an award for this. I've been working on developing cellular automata for solving sudoku, but you're lightyears beyond what I've so far been able to do.

Wow, how would that work? Do you have any code up where I could see it? That's an amazing idea!

You start with the von Neumann existence proof and work your way backwards to a universal constructor that spits out sudoku-solving machines.

No, I haven't pushed any of my code yet. First steps have just been getting automata working (which I'm struggling with because I wanted to do this in python) and generating solved sudoku (finished that).

The second step is to build an array for all the 'cells' in a sudoku board. Really, all the information for every 'cell' is 3 matrices of 8 other cells (row cells, column cells, major cells). Then, another `TODO`, enumerating all of the 'conditionals' for the automata? If you want to DM me, I'd love to pick your brain on this. How to define the conditionals for the rules, etc.

Then the plan was to just push DL compute at it: generate a set of conditionals; sets of random sudoku boards; allow the algorithm to run GoL-Sudoku flavor; score them based on their performance; feed this back as the response in the DL model; rinse; wash hands; compute.

Ah, I see. I'm afraid I don't have any advice on how to define the conditionals because I don't know a distributed algorithm for solving sudoku. Presumably you'll need some sort of guarantee that the sudoku has a unique solution, otherwise things could get very messy and/or slow. And you won't be able to fit the board state in 32 bits, even if you can somehow take out rotations and such, so you can't have the full current state available to a given cell.

I suspect just throwing DL at it without giving it more to go on won't find a solution in a reasonable amount of time.

When I say conditionals, I mean the particular rules for the automata. So like GoL the data going into a state change is a count of the neighborhood in the area of the cell. There are some thresholds (number of neighbors), and then based on the conditionals, the state is updated.

So one conditional is the size/ dimensionality of the neighborhood. Another, in your case, is the class of the pixels.

I meant to take some time this weekend to dig into your code and look at how you've structured your conditionals.

That is pretty dang incredible. I love the debugging colors etc.

Maybe someone has already done this but I'm surprised someone hasn't made an LLVM -> Life compiler just because. Might as well do LLVM -> sh while they're at it.

This is super cool! By any chance have you seen Dave Ackley's Movable Feast Machine and related projects? He's working on some similar ideas – cellular automata with different classes of cell that pass local state around to build large-scale systems.

Here's "demon horde sort", which is a kind of stochastic self-healing bubble-sorting automaton: https://www.youtube.com/watch?v=lbgzXndaNKk

I hadn't seen that; thanks for the pointer.

This is remarkably beautiful. Could you, perhaps, give some detail as to how it functions? I see wave propagation, but I'm interested in the state dynamics of a particular cell.

There's some general background at https://github.com/ericu/CellCulTuring/blob/master/README.md but basically I've got a number of different general classes of cell [background, counter, wall, ball, paddle, etc.] and each knows the kinds of situations that will cause it to change into something else. Within each class of cell, there's further state, so e.g. the ball's a different color when it's moving up and to the right than when it's moving down and to the left. Each cell is basically its own state machine, taking its state and the states of its neighbors into account, and progressing through the substates of its class until it turns into something else.

Say a blank background cell sees a ball cell to its left. It looks at the precise color of the ball to determine that the ball's moving to the right, so the next cycle, the background cell must become a ball cell with the same motion. It's a bit more complicated than that because balls only move every other cycle, they've got internal counters [colors] to deal with moving diagonally, bouncing off walls, hitting the paddle, etc., but that's basically it.

The actual state machine code takes thousands of lines of JavaScript to express.

Is the score and game over message part of the automaton? Couldn't quite tell from the debug pixels output.

Yes, everything inside the canvas is part of the same giant automaton, and follows the same rules.

In fact, @imode, if you want to look at one of the smaller state machines, look at the scoreboard code in https://github.com/ericu/CellCulTuring/blob/master/scoreboar.... It's a seven-segment display with some tweaks and a hack to show the game-over message. I initialize the scoreboards by drawing the segments in hard-to-see colors so that they're invisible when they're turned off. Each cell of the scoreboard always knows the current score; they propagate the updates to each other as fast as the find out about them. Each segment has an ID [a different color field] and a lookup table that tells for which scores e.g. ID 3 should be visible. So then when each segment is supposed to be visible, it sets a high-order color bit to show up. That's one of the few places that I actually have to set bits just for visibility. For the ball, wall, paddle, and such I just chose the bits such that you could see what the cells were naturally--I didn't have any bits to spare. For the sub-space of bits allocated to the scoreboard, I've got plenty extra. I was considering doing a fancier font using a 1-hot encoding instead of 7-segment, but I wanted to get this done.

Wow, that's awesome. The score display makes me think of some of the stuff that's been done in Wireworld: https://unnikked.ga/simulate-logic-circuits-using-wireworld-...

(There was a similar thing posted here a while back, too, that used modified rules to make it a bit quicker and simpler, but I can't remember what it was called...)

The Powder Toy includes Wireworld elements, among other electronic bits: https://powdertoy.co.uk/Wiki/W/Elements:Electronics.html#Wir...

That's really cool, I'd never encountered Powder Toy before. Thanks!

Ah thanks, and I see the state change crawl up the border of the canvas that I missed before - I was looking for another 'wave' across the whole field.

Is the AI part of the automaton too? I assumed that was programmed separately and I was a bit disappointed.

Nevermind, I just found the more revealing colors. That's great!

So, could we get a second paddle near the net for doubles play, a second ball, extra scoring zones, just by changing the initial state?

In theory yes, but in practice the game is pretty constrained, so it likely wouldn't work. For example, I assume that the AI message never reaches an AI-controlled paddle while it's moving. If it did, the paddle might tear in half, trying to go 2 places at once. With only one ball, it's a safe assumption--the speed of the ball and message guarantee it. With more than one, it would probably get broken quite quickly.

If you wanted to support doubles play, it might be possible with enough tweaks to the rules, but it would not be as simple as just drawing more paddles.

This is awesome. Now I am wondering if you could do effectively the same thing in Conway’s game of life, where if you zoomed out far enough you would see the game’s graphics.

You mean something like this?

If you don't want to be "spoiled" as to what exactly the video is going to show as it zooms out, use this link.. and don't pay attention to the browser tab title, or the video title in the top left corner, until it disappears in about 3 seconds along with the rest of the UI:

https://www.youtube.com/embed/xP5-iIeKXE8?autoplay=1 [1:29]

Canonical link:

https://www.youtube.com/watch?v=xP5-iIeKXE8 [1:29]

Yep, the OTCA metacell was exactly what I was thinking of. We know that the game of life is Turing complete, so the only challenge is figuring out how to make the graphics look presentable when zoomed out. Someone must have just implemented a 2d graphics environment on top of game of life.

Whoa--I'd heard of that computation, but I thought the resulting output was single-cell, not big obvious blocks like that. That's beautiful.

If you zoom out far enough you can do anything, I recall somebody made a whole system with pixels to display arbitrary data.

Reply on news.ycombinator.com