Show HN: Game of Life in 32 bytes of assembler | Hacker News Reader

Show HN: Game of Life in 32 bytes of assembler

pouet.net

267 pointsHellMood36 comments

(source included in the link, writeup will follow) To my knowledge, the first implementation ever in 32 bytes. This builds upon the 65 bytes version of Vladislav Kaipetsky, Tenie Remmel and Mark Andreas from 1998.

Edit: The writeup is now available : http://www.sizecoding.org/wiki/Game_of_Life_32b

Capture : https://www.youtube.com/watch?v=EgqiLf19og4

The modbyte trick is clever.

The writeup sure brought back memories.

Over 20 years ago I made a 2-player graphical worm game for DOS. I still have it in a zip. It is 123 bytes long and back then I couldn't squeeze more out of it.

After reading that writeup I feel like there's so much bloat in that 123 bytes!

Please make it available online!

I can make it available here :)

Here's the binary:

  uBMAzRC6AKCOwovyM/+xAYvp+rraA+yoCHX77KgIdPsmgDWRdDCQkORgityyBDqHawF0C5CQ/sP+
  ynXy6wmQKtzQ44uPcwED+YD0BIf+h+k793W/tAyA9ATA7AKK1IDCQbgDAM0QtALNIcMeIBEfJCYX
  Jf//AQDA/kAB

Copy that to a file and then: "base64 -d blah.txt > worms.com"

Make sure there are no spaces in the beginning of the lines.

This is from the original document:

  "This is a version of the worm game for two players.
  Game objective is to stay alive longer than the other worm!
  You die if you eat yourself, ie. you are going RIGHT and you press LEFT.
  
  Move the worm with the following keys:
     PLAYER A:  (topmost worm)
        W
      A   D
        S
  
     PLAYER B:  (lower worm)
        I
      J   L
        K
  
  Winner is indicated by player letter, "A" or "B".
  An even game is indicated by a "C". An even game means that the worms
  ate each others heads, and nobody won."

Edit: correct base64 formatting

It's online now:

http://twt86.co/?c=uBMAzRC6AKCOwovyM%2F%2BxAYvp%2BrraA%2ByoC...

cool. For OpenBSD:

     cat worms.uue

begin-base64 644 worms.com uBMAzRC6AKCOwovyM/+xAYvp+rraA+yoCHX77KgIdPsmgDWRdDCQkORgityyBDqHawF0C5CQ/sP+ ynXy6wmQKtzQ44uPcwED+YD0BIf+h+k793W/tAyA9ATA7AKK1IDCQbgDAM0QtALNIcMeIBEfJCYX Jf//AQDA/kAB

        b64decode -o worms.com worms.uue

I did the same thing! The year was 1997. There was some kind of online coding competition back then if I recall correctly. Mine is larger (256 bytes) but it has a nice background image (a mandelbrot fractal). Here is the binary:

    M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI+jPJSfOqv0ABscaqUL3C/jPAM9tXvxAAZg+/
    8w+v2GaYZvfoZovQZg+v9mYrxmbB+AcrxS0AAcH7BivZg8NkZgPWZsHqEHUDT3XNi8cEEF+qRXW8
    WKris/u/6Hu+2HyL6rv///7EsQK62gPsqAh1++yoCHT74vGwCSaAPQ+qdoBP/sAmgDwPJogED4Zy
    /wP9A/P+zHXOZmSPBiQAsAPNEMPkYIrgPC11A71AATwRdQO9wP48HnUDvf//PCB1A70BADxQdQO7
    QAE8SHUDu8D+PEt1A7v//zxNdQO7AQCwIOYgzw==

Running on twt86.com:

http://twt86.co/?c=M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI%...

I see the mandelbrot background but then it exits

Not sure why, just tested it in native dosbox and it works.

edit: try pressing any arrow key when the fractal is drawing.

    ~controls :

    Player 1        Player 2 (or arrows)

       W               8
     A + D           4 + 6
       X               2

This is so interesting, VM using a URL for the code.

A bit of hair splitting, but technically it's an emulator, not a VM, since it's just simulating the CPU using javascript in your browser.

It is a base64 encoded highly optimized x86 assembly in DOSBox emulator inside a Javascript VM Chrome browser inside my Windows 10 Sandbox Nested Hyper-V VM inside VMware Workstation inside my Windows 10 machine.

It’s turtles all the way down.

Yeah, and then CPU which translates x86 code into uOPs.

There's always a relevant xkcd: https://xkcd.com/676/

Emulators are VMs too.

Well, depends a bit on what definitions you use.

For example there's VM in the sense of JVM. But there's also in VM in the sense of Xen (VM) vs Docker (not a VM).

And probably a few more slightly different usages.

Those are both VMs in the same sense. A VM creates an abstract, indirect implementation of a computing system. Sometimes that's with a lot of hardware offload as in Xen or picojava. Sometimes that's with a JIT as in HotSpot, orginal VMWare, or Transmeta. Sometimes that's just with an interpreter like the original JVM or Dosbox.

They're all virtual machines whether they're running code originally meant for execution on hardware or not.

That's a pretty wide definition. One that also encompasses any 'bare metal' OS, because they use microcode these days.

I remember that! it was on rec.games.programmer, wasn't it?

It was usenet for sure, probably the rec.games.programmer.

10 years later, I wrote a fractal zoomer in asm, it was 399bytes, with a nice color palette.

https://www.pouet.net/prod.php?which=24447

I have to say, you really are an amazing coder. I read your write up for “memories.” a few days ago and it completely blew my mind. Thanks for sharing your knowledge!

While it absolutely doesn't hold a candle to 32 bytes :) I'm reminded of the 1691-byte IOCCC entry from 1991 which drew the Game of Life on the root X server window without using Xlib.

I'm completely naive about Life implementations, and I've always been curious if the approach used by this entry is especially interesting; it's certainly a fascinating read (https://www.ioccc.org/1991/davidguy.hint):

The algorithm used to compute the next generation is based on the observation that a cell's state in the next generation is a boolean function of its current state, and the states of its 8 neighbors (ie, a boolean function from 9 bits to 1 bit). This function can be computed by a boolean circuit. In addition, intermediate values computed by the circuit can be shared between neighboring cells, reducing the number of gates per cell required.

These ideas have been used before, to compute the next generation through a series of bit blits. Instead of doing this, we map values in the circuit to bits in registers, so that the next generation can be computed efficiently within registers, minimizing memory accesses.

As a result, the computation of the next generation is performed with about 1.6 instructions per life cell, consisting of .125 memory accesses, .17 shifts, and 1.3 logic operations. The net result is that the time to transfer the bits to the X server, and for the X server to draw them on the screen, dominates the time to compute the next generation.

I'm not sure what I did last time I tried to get this working and failed; it works great on Debian 10 with GCC 8.3 etc:

$ wget https://www.ioccc.org/1991/davidguy.fix.c

$ gcc -o davidguy davidguy.fix.c -m32

$ xhost +

$ ./davidguy

If your X server is not :0, change the last character of the ".slo.-W00,tmhw.W/" string to be one less in ASCII to the display number (ie 0 -> /, 1 -> 0, 2 -> 1, etc).

The main reason I added this comment was out of curiosity about the technical competence/interestingness of the implementation.

This general technique is (or was) called SWAR for SIMD-within-a-register, before CPUs had actual SIMD registers and instructions. I played around with bit-parallel Game of Life a while back, calling it LIAR (Life In A Register). If you are doing really fast hashlife then the very low level supercell representations can be small bitmaps for which LIAR works nicely. https://fanf.livejournal.com/93032.html

This comment is more than 32 bytes

Not mine. It's 32 bytes exactly!

Not if you consider it's whole row in the DB!

Depends on the Unicode encoding, no? Although, to be fair, it's probably UTF-8.

I'm blown away. I can't even begin to think how to encode GoL in such a small program.

Jaw dropping.

twt86 link below...

http://twt86.co?c=xSQgswcIBKfALQWRAkFeAkD8AoCcAEt18ooE%2BdLY...

Not the same class because it's a high-level language, but this J version is worth mentioning at 26 bytes, and is beautifully readable if you're familiar with J:

    (]=3+4=*)[:+/(>,{;~i:1)&|.

Disclaimer: I am not the original author of this snippet.

Try it online:

https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NWJtjb...

The terminals connected to my university's Burroughs 6700 mainframe in 1981 had a 8080 processor in them and there was an escape sequence that allowed you to type some hex code into the input buffer and run it. So of course I did Life. It was probably more than 32 bytes but not much larger as I was able to memorize the hex. It wasn't quite right since it used the updated values for half of the neighbors due to the lack of double buffering.

This is truly incredible.

Modbyte tuning is amazing, but I'm still a bit confused how you jump back into the modbytes.

32 bytes = how many jigawatts

Reply on news.ycombinator.com