Google Writing Drone AIs

Re this: https://www.theverge.com/2018/4/4/17199818/google-pentagon-project-maven-pull-out-letter-ceo-sundar-pichai

I’m of two minds on this story. On one hand, I get the that the programmers are unhappy about it, but on the other that algorithm will get written no matter what, so people who are good at implementation may have some sort of obligation to minimize civilian casualties by making sure it does its job well.

That and they’re working for Google. It’s not like they really have some sort of moral high ground just because what they do is starting to feel viscerally wrong as opposed to just wrong in the abstract.

Yeah ok, I’m not really in two minds about it as you might tell, I just said that to try and be less antagonistic about stuff. People just blanche when they can see the results of their actions clearly enough to make it impossible to deny them away. Shut up and write the war machine, Googlers, it’s probably the least damage you’ll do humanity all day.

TIS-100, ranty review

I just ‘finished’ the puzzle game TIS-100, meaning I wrote a code that solves the final task of the game and saw all of the plot (other than the hidden puzzle. I’m not ready to tackle that mentally), so please listen to me rant why this is probably my favorite puzzle game of the 2010s, if not of all time.

First of all: what is it? It’s a game that tells you that you inherited a weird old time-y computer from your missing uncle and are trying to run some debuggers on it to figure out what it is. It comes with an ancient looking manual and very little else. If it sounds like a mystery game, it’s cause it is.

(Throughout this post, feel free to click to embiggen the images)

Blank TIS-100 screen
Blank TIS-100 screen

The game is really about designing algorithms in the mathematical sense: converting inputs into outputs. To do so you’re given a pretty simple assembly language architecture with one feature, and one huge caveat. The feature is that you have access to multiple chips that all run in parallel and can talk to each other. The caveat is that each only has a single register that can do storage, math, and logic, and a second register that can only be used as long term storage.

Got it? Ok, so let’s go over a solution to a puzzle, or more precisely my thought process of solving one. Spoiler warning obviously, if you want to solve each one yourself, don’t read this.

The TIS-100 in later levels includes a ‘graphics’ module that allows you to display pixel data that is being sent to the output. The format is a string of integers formed as

( Starting X coordinate, Starting Y coordinate, <series of integers representing colors to draw 1 square of>, -1 )

In this task we are given a length of a line, then a color to use for it. We have to figure out how to wrap at the edge of the screen if the line is longer than the screen width. Here’s what the tasks look like, along with my initial solution:

Parts of the screen
Parts of the screen

So how does a guy who loves nothing more than clean logical order and Object Orientation handle this? Simple, by creating treating each node as a make-shift object. Let me walk you through the code above.

First, we got to keep track of where we are on the screen:

screen2
The column and row trackers

The upper circled node iterates from 0 to 30 (screen width), then sends that data to the right. It also sends either 0 or -1 down to the node that keeps track of rows. The row tracking node (circled below) returns it’s stored value, and whenever it receives a -1 it increments the stored value. So now we got a steady generator that spits out

(0,0), (0,1), (0,2) ... (29,0), (30,0), (0,1), (1,1) ...

etc etc.

Now we have to keep track of what color we’re on. We got a third node for that:

screen3
The color tracker

This one stores the length of a color and the value of the color, then by swapping those in and out of the long term register it decrements the length and constructs a little quad packet like (0, 0, 2, -1). That particular packet would draw a grey square in top left for instance. The node then passes this packet down into the chain of helper passing nodes and off they go to the output off the bottom row.

I make this sound trivial, but in reality it took the better part of an hour to come up with this solution, and then a better part of a second hour debugging a bunch of silly deadlocks and memory corruption mistakes (having two nodes get out of sync and wait for input from each other so that they hang indefinitely, forgetting to swap memory contents before displaying, stuff like that).

So what kind of performance do we get on that? Well, this:

speed1
Initial score

Not great compared to the average other user. So now we get to the second part of TIS-100. Optimizing to compete with the ‘others’ of the internet. So how can we optimize this?

Well, first thing that jumps out at me is that the bottom right node seems to be sending stuff pointlessly far. Look:

A regular Marco Polo this guy
A regular Marco Polo this guy

It really doesn’t have to go that far. What if instead of going all the way around, it just goes right? Now the top right packet constructor will only do 3 of the numbers, and the node below him will just plug in the row number from the left as we go. That should skim off a cycle or two, no? And skim them off the innermost loops too. Always good.

More to the point, this route
More to the point, this route

So now we’re just going straight right, though we needed to add a tiny bit of logic to the right to build the packet. 3 cycles less per each loop. Nice.

We can do better though, can’t we. I mean, what if we reärrange the nodes so that instead of the top right node acting as a packet constructor the packet gets constructed “as needed” and only in the last moment. A Just-In-Time packet, if you forgive the borderline archaic term. It would require moving the two “storage” nodes to below the input and then setting up an assembly line to the right of them. And oh look, the output is already set up exactly in the perfect spot for it. Hm. It’s like the designers knew this.

It's so beautiful
It’s so beautiful

So at time A the packet is (?, ?, Color, ?).

At B we get (X, ?, Color, ?)

And only at C do we get (X, Y, Color, -1)

Now, how much of an improvement do we get?

A whole freaking lot it turns out
Quite a bit, it turns out

Down from 7684 to 4898, so 36%. Not too shabby considering all we did was move some nodes around. Now, if we really wanted to make this mother fly, we would use that feature that lets us create longer packets. I mean, why send

(0,0,1,-1), (1,0,1,-1), (2,0,1,-1), (3,0,1,-1), ...

When we can send

(0,0,1,1,1,1 ... 1,1,-1)

I mean, it can’t be that difficult can it?

And before you know it, you’ve sunk another few hours into TIS.

 

Quick perl tip:

Quick perl tip, don’t confuse

if( $a >= 3 ) {

and

if( $a => 3 ) {

the first one is “Greater than or equal to”. The second is “set it equal to 1 or 0 depending on whether it’s greater than”. You don’t want that. If you do want that, you shouldn’t want that.

Yes that just cost me like 10 minutes.

Dragon Slayer review

UPDATE ON BOTTOM

A kickstarter micro from Joe (thank you Joe), and another fun travel game.

IMG_3120
Dragon Slayer at Tea-n-more

Roll dice to kill dragons. Blue is easy to kill, green is hard to kill, red is hard to kill. Very push your luck with one minor complication of “challenging” where you can force someone to fight 1 more dragon. I think this is one of those games that I’ve never won against anyone, cause for a mathematician I am surprisingly bad at anything push-your-luck.

No fear though. I am also a problem solver. I wrote a perl script to try every possible strategy of this game to find the ultimate path: http://www.codesend.com/view/27b4c6737ffb0f258d21f0870ef40f39/ (note, that page apparently stripped the slash from \n turning them into n, putting the slashes back in is left as an ‘exercise to the reader’)

Ran the above a million times as it plays the game against itself, and dumped out the results split first into 3 bravery strategies, then per line as to what dragons to fight first and when to stop: G is green, B is blue, R is red:

BRAVE HUNTERS (NEVER STOP):
G: 3.55582724284349
GB: 4.83913016118448
GR: 5.93901419466194
GBR: 5.88304461564739
GRB: 6.12547757531082
B: 1.9422564628113
BR: 5.43162020514388
BG: 4.73947086902975
BGR: 5.8079270759356
BRG: 5.91094849827848
R: 4.72113197709436
RB: 5.62512548057186
RG: 6.04521196103285
RGB: 6.19196504822949
RBG: 6.08984259117755

SORTA COWARDLY HUNTERS (STOP AFTER LOSING 2 DICE):
G: 3.55736209937724
GB: 4.83183743505442
GR: 6.01160921057368
GBR: 6.29789774295348
GRB: 6.53803741345588
B: 1.94158197242587
BR: 5.36629909166177
BG: 4.64798593695629
BGR: 6.12940520044637
BRG: 6.2615042177132
R: 4.71602131055088
RB: 5.71132962958519
RG: 6.22440274061364
RGB: 6.74595327517729
RBG: 6.64300027598123

VERY COWARDLY INDEED HUNTERS (STOP AFTER LOSING 1 DIE):
G: 3.55764476897338
GB: 4.48069396594449
GR: 5.52641870440066
GBR: 5.59525061049419
GRB: 5.86873999405275
B: 1.94178904084078
BR: 4.67586588050834
BG: 4.05631865243732
BGR: 5.16761932796078
BRG: 5.34570040879832
R: 4.71543010930324
RB: 5.43283062052642
RG: 5.88802350064729
RGB: 6.23849672751084
RBG: 6.13399333787887

So the optimal strategy is “Fight Red, then Green, then Blue, stop if you’re ever down to 1 die”. Ready to play this again now 😛

UPDATE:

Someone pointed out that this forgets that it’s possible to start over after killing 3 dragons. Went ahead and wrote a mini script to solve 4+ dragons and dropped it on gist here.

Chart for the 4+ goes:

RGBB:2		8.95587161894434
RGBG:2		8.1855250370825
RGBB:1		7.83691944708024
RGBR:2		7.2969944065635
RGBG:1		6.79607331108854
RGBGB:1		5.9229677180421
RGBR:1		5.82409754092746
RGBBG:1		5.67912411832824
RGBRB:1		5.56045424181697
RGBRG:1		5.39682940693488
RGBBR:1		5.20002033243532
RGBGR:1		5.10485791835152
RGBRBG:1	4.27486930828093
RGBBGR:1	4.1413477013505
RGBBRG:1	4.07694637988488
RGBGBR:1	4.00618498734889
RGBRGB:1	3.99050347932869
RGBBR:2		3.86899117368152
RGBGRB:1	3.86877828054299
RGBBG:2		3.81470911086718
RGBGR:2		3.58723111077088
RGBGB:2		3.43148089674771
RGBRG:2		3.26223520818115
RGBRB:2		3.07526703651569
RGBRGBB:1	2.81118143459916
RGBBGRB:1	2.75342465753425
RGBGBRB:1	2.73006774361647
RGBRBGB:1	2.67808219178082
RGBGRBG:1	2.66980146290491
RGBRBGG:1	2.61403040810883
RGBRGBG:1	2.52007347152978
RGBBRGB:1	2.49118188997104
RGBBRGG:1	2.47904524007771
RGBGRBB:1	2.46516500785752
RGBGBRG:1	2.3903355704698
RGBGBRR:1	2.3730625334046
RGBGRBR:1	2.30893433799785
RGBBGRG:1	2.28329361927456
RGBRBGR:1	2.27629513343799
RGBRGBR:1	2.24063009234112
RGBGBR:2	2.2267829656234
RGBBGRR:1	2.18224789915966
RGBBGR:2	2.17974814559255
RGBBRGR:1	1.96322336398053
RGBBRG:2	1.89581278579754
RGBRBG:2	1.87088653119942
RGBRGB:2	1.74605504587156
RGBGRB:2	1.67498388730319
RGBGRBG:2	0.8984375
RGBRBGR:2	0.89143865842895
RGBBRGG:2	0.86304158185519

Requiem 32

Requiem 32 is a series of virus genotypes, starting with a simple repeated ‘c’ which then in 31 iterations becomes the HIV genotype. Each of these iterations is then analyzed using a process based on biological DNA parsing which change the music created into a different piece, slowly more and more different from the original, until the original state is completely unrecognizable. I hope the piece gives helps create emotional understanding of the idea of a virus and how something that is so simple can have such an incredible impact, hopefully bridging the very real mental chasm between the biology of infection, and it’s effect on the infected.

For best experience, please make your browser window as large as possible and use headphones. To interact with the piece click the circles at the top. The RNA sequence clicked on and matching sheet music will be loaded and the piano performance encoded by that RNA string will start. 1 represents a starting state, and encodes the 4 E chords with a repeated E note 4 times. Each of the other states adds a tiny bit more complexity to the virus, creating progressively more and more changes to the music piece.

A visual guide for the RNA parsing is provided at left. The darker color is the header for a particular function, while the lighter color is the actual data processed by it. Each of the biological parsers, each represented by one color, begins at the top of the genotype, reads until it finds its starting trigger, and then starts reading while getting ready to apply a modification. Upon hitting the terminator (always “cc”), it applies the change to the music. It then keeps reading looking for a new starting condition.

The piece involves intrinsic looping in the structure of the music, similarly to how the biological processes do not function in a vacuum, but rely on a host organism to provide context to the RNA intrusion.

The installed piece can be found at http://miriku.com/requiem, while the source code is available at https://github.com/miriku/requiem.

Technical notes: the majority of the code is written in python, with the exception of the text parser which creates the 30 intermediate states which is written in perl. When ran using the ./go shell command, the python code will open all rna files, processes them, then output both a color coded html file and the midi file represented. The file ‘models.py’ contains the actual structure of the music: repeated sequences that contain a chordal structure, and a melody played on top; while the file ‘driver.py’ contains the actual mechanism of parsing of the text into midi. The final mp3s and pngs of the sheet music were both created by hand and are currently not automated.

Finally, I genuinely apologize for any possible layout issues with your particular hardware/software setup. This was designed under time constraints as a standing installation using Safari in full-screen mode, and unfortunately cross-platform compatibility was not a priority. I welcome any pull requests with improvements.

I genuinely thank you for your time.

Starting a Programming Project

This is what programming looks like to me, step 1

IMG_2737
Programming Sketches

If I start coding before I sit down and make one of these, I’ll never get anywhere. I need to have a mental visual relationship between everything, before I can start.

Visual memory is very important in programming for me. I really value IDEs that have one of those sublime-style “code maps” on the side, and ones that let me skip to bookmarks and function definitions easily, preferably with a single click. Not having to think about where I am in the file lets me concentrate on more useful things.

Code map example, it's the thing on the right
Code map example, it’s the thing on the right

Another weird thing is that sketching process is so far it only works for me with pen and paper. I’d love to have an iPad with enough input resolution to properly let me sketch but so far none of the tools are good enough at it.