11 ms·

Show HN: Game of Life in 32 bytes of assembler

267 points by HellMood 6y ago

HellMood 6y ago
(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 http://www.sizecoding.org/wiki/Game_of_Life_32b Capture : https://www.youtube.com/watch?v=EgqiLf19og4 https://www.youtube.com/watch?v=EgqiLf19og4
- jnurmine 6y ago
  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!
  - zorbash 6y ago
    Please make it available online!
    - jnurmine 6y ago
      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
      - gregschlom 6y ago
        It's online now: http://twt86.co/?c=uBMAzRC6AKCOwovyM%2F%2BxAYvp%2BrraA%2ByoCHX77KgIdPsmgDWRdDCQkORgityyBDqHawF0C5CQ%2FsP%2BynXy6wmQKtzQ44uPcwED%2BYD0BIf%2Bh%2Bk793W%2FtAyA9ATA7AKK1IDCQbgDAM0QtALNIcMeIBEfJCYXJf%2F%2FAQDA%2FkAB http://twt86.co/?c=uBMAzRC6AKCOwovyM%2F%2BxAYvp%2BrraA%2ByoC... :)
      - anthk 6y ago
        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
  - adhoc32 6y ago
    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==
    - gregschlom 6y ago
      Running on twt86.com: http://twt86.co/?c=M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI%2BjPJSfOqv0ABscaqUL3C%2FjPAM9tXvxAAZg%2B%2F8w%2Bv2GaYZvfoZovQZg%2Bv9mYrxmbB%2BAcrxS0AAcH7BivZg8NkZgPWZsHqEHUDT3XNi8cEEF%2BqRXW8WKris%2Fu%2F6Hu%2B2HyL6rv%2F%2F%2F7EsQK62gPsqAh1%2B%2ByoCHT74vGwCSaAPQ%2BqdoBP%2FsAmgDwPJogED4Zy%2FwP9A%2FP%2BzHXOZmSPBiQAsAPNEMPkYIrgPC11A71AATwRdQO9wP48HnUDvf%2F%2FPCB1A70BADxQdQO7QAE8SHUDu8D%2BPEt1A7v%2F%2FzxNdQO7AQCwIOYgzw%3D%3D http://twt86.co/?c=M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI%... I see the mandelbrot background but then it exits
      - adhoc32 6y ago
        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
      - mycall 6y ago
        This is so interesting, VM using a URL for the code.
        gregschlom 6y ago
        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.
- neotek 6y ago
  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!
deleted 6y ago
[deleted]
deleted 6y ago
[deleted]
eps 6y ago
This is truly incredible.
- deleted 6y ago
  [deleted]
basementcat 6y ago
twt86 link below... http://twt86.co?c=xSQgswcIBKfALQWRAkFeAkD8AoCcAEt18ooE%2BdLY6%2BE%3D http://twt86.co?c=xSQgswcIBKfALQWRAkFeAkD8AoCcAEt18ooE%2BdLY...
exikyut 6y ago
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 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 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.
- fanf2 6y ago
  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 https://fanf.livejournal.com/93032.html
Marazan 6y ago
I'm blown away. I can't even begin to think how to encode GoL in such a small program. Jaw dropping.
BubRoss 6y ago
This comment is more than 32 bytes
- MaxBarraclough 6y ago
  Not mine. It's 32 bytes exactly!
  - loa_in_ 6y ago
    Not if you consider it's whole row in the DB!
  - cjg 6y ago
    Depends on the Unicode encoding, no? Although, to be fair, it's probably UTF-8.
dvt 6y ago
Modbyte tuning is amazing, but I'm still a bit confused how you jump back into the modbytes.
modzu 6y ago
32 bytes = how many jigawatts
jonahx 6y ago
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/NWJtjbVNbLU0o6209TXsdKqt6zKtDDXVavT@a3Jx5drqWSpYKqgANRgCMTo0ROMZYlVFF8jFlZqcka9gra9Qraaup6WukBZnpZGpZ6mpkPsfAA https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NWJtjb...
jecel 6y ago
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.

267 points by HellMood 6y ago

(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 http://www.sizecoding.org/wiki/Game_of_Life_32b Capture : https://www.youtube.com/watch?v=EgqiLf19og4 https://www.youtube.com/watch?v=EgqiLf19og4

jnurmine 6y ago
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!
- zorbash 6y ago
  Please make it available online!
  - jnurmine 6y ago
    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
    - gregschlom 6y ago
      It's online now: http://twt86.co/?c=uBMAzRC6AKCOwovyM%2F%2BxAYvp%2BrraA%2ByoCHX77KgIdPsmgDWRdDCQkORgityyBDqHawF0C5CQ%2FsP%2BynXy6wmQKtzQ44uPcwED%2BYD0BIf%2Bh%2Bk793W%2FtAyA9ATA7AKK1IDCQbgDAM0QtALNIcMeIBEfJCYXJf%2F%2FAQDA%2FkAB http://twt86.co/?c=uBMAzRC6AKCOwovyM%2F%2BxAYvp%2BrraA%2ByoC... :)
    - anthk 6y ago
      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
- adhoc32 6y ago
  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==
  - gregschlom 6y ago
    Running on twt86.com: http://twt86.co/?c=M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI%2BjPJSfOqv0ABscaqUL3C%2FjPAM9tXvxAAZg%2B%2F8w%2Bv2GaYZvfoZovQZg%2Bv9mYrxmbB%2BAcrxS0AAcH7BivZg8NkZgPWZsHqEHUDT3XNi8cEEF%2BqRXW8WKris%2Fu%2F6Hu%2B2HyL6rv%2F%2F%2F7EsQK62gPsqAh1%2B%2ByoCHT74vGwCSaAPQ%2BqdoBP%2FsAmgDwPJogED4Zy%2FwP9A%2FP%2BzHXOZmSPBiQAsAPNEMPkYIrgPC11A71AATwRdQO9wP48HnUDvf%2F%2FPCB1A70BADxQdQO7QAE8SHUDu8D%2BPEt1A7v%2F%2FzxNdQO7AQCwIOYgzw%3D%3D http://twt86.co/?c=M8CO4LATzRC7JABmZP83ZMcHvwFkjE8CaACgB7AI%... I see the mandelbrot background but then it exits
    - adhoc32 6y ago
      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
    - mycall 6y ago
      This is so interesting, VM using a URL for the code.
      - gregschlom 6y ago
        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.
neotek 6y ago
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!

deleted 6y ago

[deleted]

deleted 6y ago

[deleted]

eps 6y ago

This is truly incredible.

deleted 6y ago
[deleted]

basementcat 6y ago

twt86 link below... http://twt86.co?c=xSQgswcIBKfALQWRAkFeAkD8AoCcAEt18ooE%2BdLY6%2BE%3D http://twt86.co?c=xSQgswcIBKfALQWRAkFeAkD8AoCcAEt18ooE%2BdLY...

exikyut 6y ago

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 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 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.

fanf2 6y ago
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 https://fanf.livejournal.com/93032.html

Marazan 6y ago

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

BubRoss 6y ago

This comment is more than 32 bytes

MaxBarraclough 6y ago
Not mine. It's 32 bytes exactly!
- loa_in_ 6y ago
  Not if you consider it's whole row in the DB!
- cjg 6y ago
  Depends on the Unicode encoding, no? Although, to be fair, it's probably UTF-8.

dvt 6y ago

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

modzu 6y ago

32 bytes = how many jigawatts

jonahx 6y ago

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/NWJtjbVNbLU0o6209TXsdKqt6zKtDDXVavT@a3Jx5drqWSpYKqgANRgCMTo0ROMZYlVFF8jFlZqcka9gra9Qraaup6WukBZnpZGpZ6mpkPsfAA https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/NWJtjb...

jecel 6y ago

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.