6 ms·

Show HN: I implemented Pong as a cellular automaton

225 points by uranium 8y ago

uranium 8y ago
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.
- sansnomme 8y ago
  Very impressive! Congrats on shipping!
  - uranium 8y ago
    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.
- RosanaAnaDana 8y ago
  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.
  - uranium 8y ago
    Wow, how would that work? Do you have any code up where I could see it? That's an amazing idea!
    - pvg 8y ago
      You start with the von Neumann existence proof and work your way backwards to a universal constructor that spits out sudoku-solving machines.
    - RosanaAnaDana 8y ago
      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.
      - uranium 8y ago
        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.
        RosanaAnaDana 8y ago
        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.
- basementcat 8y ago
  Reminded me of a problem set I was once assigned. https://en.wikipedia.org/wiki/Firing_squad_synchronization_problem https://en.wikipedia.org/wiki/Firing_squad_synchronization_p...
  - uranium 8y ago
    Neat--I hadn't heard of that. The wave propagation makes me think back to the problem I was working on the first place.
    - basementcat 8y ago
      The nice property of the “firing squad” is that the number states is independent of the length of the firing squad.
  - daveFNbuck 8y ago
    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.
imode 8y ago
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.
- uranium 8y ago
  There's some general background at https://github.com/ericu/CellCulTuring/blob/master/README.md 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.
  - Someone 8y ago
    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?
    - uranium 8y ago
      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.
tokyodude 8y ago
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.
baddox 8y ago
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.
- himlion 8y ago
  If you zoom out far enough you can do anything, I recall somebody made a whole system with pixels to display arbitrary data.
- Cyphase 8y ago
  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 https://www.youtube.com/embed/xP5-iIeKXE8?autoplay=1 [1:29] Canonical link: https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8 [1:29]
  - uranium 8y ago
    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.
  - baddox 8y ago
    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.
sgentle 8y ago
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 https://www.youtube.com/watch?v=lbgzXndaNKk
- uranium 8y ago
  I hadn't seen that; thanks for the pointer.

225 points by uranium 8y ago

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.

sansnomme 8y ago
Very impressive! Congrats on shipping!
- uranium 8y ago
  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.
RosanaAnaDana 8y ago
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.
- uranium 8y ago
  Wow, how would that work? Do you have any code up where I could see it? That's an amazing idea!
  - pvg 8y ago
    You start with the von Neumann existence proof and work your way backwards to a universal constructor that spits out sudoku-solving machines.
  - RosanaAnaDana 8y ago
    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.
    - uranium 8y ago
      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.
      - RosanaAnaDana 8y ago
        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.
basementcat 8y ago
Reminded me of a problem set I was once assigned. https://en.wikipedia.org/wiki/Firing_squad_synchronization_problem https://en.wikipedia.org/wiki/Firing_squad_synchronization_p...
- uranium 8y ago
  Neat--I hadn't heard of that. The wave propagation makes me think back to the problem I was working on the first place.
  - basementcat 8y ago
    The nice property of the “firing squad” is that the number states is independent of the length of the firing squad.
- daveFNbuck 8y ago
  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.

imode 8y ago

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.

uranium 8y ago
There's some general background at https://github.com/ericu/CellCulTuring/blob/master/README.md 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.
- Someone 8y ago
  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?
  - uranium 8y ago
    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.

tokyodude 8y ago

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.

baddox 8y ago

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.

himlion 8y ago
If you zoom out far enough you can do anything, I recall somebody made a whole system with pixels to display arbitrary data.
Cyphase 8y ago
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 https://www.youtube.com/embed/xP5-iIeKXE8?autoplay=1 [1:29] Canonical link: https://www.youtube.com/watch?v=xP5-iIeKXE8 https://www.youtube.com/watch?v=xP5-iIeKXE8 [1:29]
- uranium 8y ago
  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.
- baddox 8y ago
  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.

sgentle 8y ago

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 https://www.youtube.com/watch?v=lbgzXndaNKk

uranium 8y ago
I hadn't seen that; thanks for the pointer.