A Return to Go

I’ve switched jobs and am using even more Go. While I previously talked about Go, it was a while ago, and I was using it inside Google, with a vastly different build system than is inflicted on the wild. So I have a new perspective on it, and I’m updating my opinion.


Concurrency is why you write code in Go rather than any other language, right? It’s Go’s shining feature. Aside from goroutines, you’re pretty much left with C with a facelift and garbage collection, and that’s probably not the thing you most want for application or service development.

Go’s not concurrent. It’s as concurrent as Node.js, just you don’t need to structure your code with callbacks. That’s it.

In Java, I have true concurrency. I’m not saying this because of OS threads versus cooperative multitasking. No, the problem with Go’s concurrency is that it’s entirely hidden from you. Java actually gives you thread objects. It lets you cancel the execution of a thread and check on its status. And that’s what I need, much of the time.

In my spare time, I’m writing a MUD. This involves a ton of AI routines, scripts, and user input handlers, each of which is easier to write as a sequential operation. So I want some sort of multitasking, and since I’m estimating a huge MUD world might need over half a million threads, OS threads won’t do. Can I use goroutines?


I need a reliable system. That means a process that checks over each scripted object to ensure it’s actually running its script. How do I do that in Go? …well, I have zero access to the default scheduler, so I can’t ask it for a list of running goroutines. I can’t get a goroutine object and ask it whether it’s running. I could use a waitgroup for each scripted object and deferred execution so that when that object’s goroutine exits for whatever reason I can see it, which is slightly annoying and has to be repeated everywhere.

I need actions to happen on schedule. I can handle the whole MUD being 50ms slow for one scheduling tick (which is planned to be 250ms); I could handle one script being slightly late for one tick; but I can’t handle long-term clock drift. Also, the order of execution might be dictated by game rules — players always go first, ordered by their speed stat; NPCs go second, ordered similarly; items and rooms go last in arbitrary order. This is much easier to handle if I write my own scheduler.

I need to suspend tasks. I wrote a script for an NPC sailor to wander around, singing and quaffing ale, but halfway through, a player attacks her. I need to be able to suspend this singing and quaffing task to handle combat. In Go’s world, I need to check whether the NPC is currently in combat after every yield. This is unusable.

What language does this stuff right? Well, the best I’ve seen is D. Fibers in D are much more of an afterthought than in Go, yet in D I can write my own scheduler, get a reference to a Fiber object to check on its status, and even cancel further execution of a fiber all in the standard library.

What if you’re stuck with Java? Well, most of the time, you aren’t manipulating shared state anyway. You need to ensure that your database library is threadsafe or just instantiate a new adapter with each task, and probably similarly with a couple other things, but you can pretty much ignore the fact that things are running in multiple threads and be okay 95% of the time. Just use a threaded ExecutorService and be done.

Type system

I thought the type system was a bit anemic before. Now I view it as an enemy.

Interfaces are not met by accident. They are planned. People write code to match an interface. Go doesn’t realize that. There is no way to say to the language: here’s this type, and oh by the way, just ensure for me that it matches the io.Reader interface. So you get compilation errors at call sites because the type doesn’t match the interface you designed it to match. This is the opposite of what I want.

There is no virtual dispatch. People do not use interfaces by default. They use concrete types by default. This means testing is ugly. I end up having to write interfaces for other people’s code a lot.

Covariant return types are not allowed. Interfaces operate on exact match only. I wrote an interface for a Redis client for testing. Then I realized that I couldn’t instantiate the return type for one of the methods with sensible values — it had private fields with public getters. So I had to write a wrapper struct for the Redis client that simply forwarded the relevant method but had a slightly different return type. (It actually isn’t possible, given the language, to solve this problem in a sensible manner. That doesn’t mean it’s less painful or that Rob Pike is any less at fault; it just means he messed up earlier and it only became apparent here.)

Syntax and parsing

Go’s syntax looks a bit funky at first. And then, eventually, it hits you: this language was not designed to make it easy for you to read and write it. It isn’t designed to make it fast for you to understand what’s written. It’s instead designed to reduce the amount of lookahead the compiler has to do, to simplify the amount of work parsing takes.

Why do I have to type “type Foo struct” rather than just “Foo struct”? The latter is consistent with the little-endian nature of Go, where types follow variables. But if you had “Foo struct” and “bar func”, that would increase the amount of lookahead the compiler had to do. Similarly, with functions, Go could have followed a strategy similar to the C family of syntaxes. But that would require more lookahead to implement.

It’s certainly not to help me read things faster. Remove the “func” and “type” keywords and I can read code just as fast. I can write it slightly faster. It’s only for the compiler’s benefit that I have to write these keywords.

This is backwards. This is perverse. A team of five to ten individuals decided they wanted to do slightly less work, so everyone else has to do more work. We pay people big money to spend more effort so a lot of people can do slightly less, and we think that’s valuable. We think it’s a good tradeoff. But here we get the exact opposite treatment and people seem to love it. I don’t understand.

There are other problems I have with the syntax. The compiler requires a := to create and initialize a new variable, while it just uses = for an assignment to an existing variable. There’s a special variable, _, which indicates “throw this value away”.

However, there are two other variable names that you will reuse very, very often: err and ok. err is the default variable name (by the documentation, not by language features) for an error. Many things return errors in addition to something else, and most of the time you’ll write something like val, err := tryGetValue(). It would be awesome if you could use := when reusing at least the ‘err’ variable.

I’m thinking of pre-declaring at least err so I can always use = for it, but I don’t think that would save me thanks to multiple return values.

All in all, this looks like two features that seem great in isolation (different syntax for declaring with initialization versus assignment, added to multiple return values) not working together very well in practice. But I’ve never even seen anyone use multiple return values aside from returning an error with a single value, so…

Also, Go says that all loops are special cases of for loops. You create an infinite loop with for { doStuff() }. You create a while loop with for booleanExpression { doStuff }. This hides programmer intent. Not ideal.

Constant initialization with iota is magic. You can write:

const (
  B = 1 << (iota * 10)

This gives you the constants you would expect given the names. The thing to remember is that iota auto-increments each time you use it, and a constant without an initializer acts as if you had copied and pasted the previous constant’s initializer… The first time I read this sort of code, I had no clue what it meant. (Also, it started with _ = iota, which confused things slightly more.) I thought I’d get sequential values, like every other language, incrementing from the previous given value. Or, if the language were especially clever, equal increments.

Magic is only good for making a programmer feel clever.

(As an aside, I praised D for its concurrency earlier. The standard library contains a lot of code written by someone who likes feeling clever. This means you have to write things like dur!"msecs"(15) rather than a more sensible construct like Duration.fromMillis(15). Even though I don’t have to modify that code, I depend on it, so I have to spend effort to understand an API expressed in templates and metaprogramming rather than simpler constructs.)

Shadowing declarations

We spoke a few moments ago about the problems with multiple assignments. Here’s a kicker: every time you create a new scope (which is, roughly, every time you have a new set of curly braces), you can freely shadow declarations.

What does that mean? Well, let’s take this snippet dealing with Redis:

var cursor int64 = 0
for {
  cursor, keys, err := redis.Scan(cursor, "prefix:*", 10)
  if cursor == 0 {
  // ...
if cursor != 0 {
  // We stopped early. Do something special.

Redis’s SCAN call takes an input cursor indicating where to start and emits an output cursor indicating where to start next time. Simple, right? Obviously correct. Wrong.

You created a new variable named keys. But you can’t separate that one variable’s new-ness from the other variables. Go assumes that you want to make all the variables anew. So instead of doing the right thing, updating cursor each time through the loop, you get a brand new variable.

Either Go will create and initialize the inner cursor to 0 each time, lift it above the point of declaration, etc; or it will use the cursor variable from above, never updating it. Either way, you’ll process the first set of values over and over again forever.


People mock Javascript for its awfulness, but Go isn’t far behind. Use Go instead of Node.js if you want, but since there are bajillions more Javascript devs than Go devs, you’d be better off using Node.js. Dart’s even significantly more popular than Go, so if you want static typing, that’s an option. (Or you can use TypeScript with Node.js, but you still have to deal with a lot of JS’s oddities.)

Telnet for Humans

I recently spent some work on telnet support in a MUD server. It took a bit of reading to find out how to implement it; the RFCs aren’t the friendliest thing to untangle, and I didn’t run across anything that was that much easier. It hurts that the standard is split across some thirty RFCs over twenty years. And this standard is big for how simple it seems — did you know that telnet supports encryption, for instance?

The most frustrating thing is that pretty much no MUD client supports any part of this, and MUD clients are poorly behaved in general. (In contrast, the telnet(1) utility on Linux seems pretty rugged, assuming the worst of the servers it interacts with.) It’s partly because the standard is so intractable, so I’m writing this guide to help out.

Core concept

An IBM 3277 display
An IBM 3277. Quite a bit smarter than Telnet. source

Telnet is a standardization of client/server communication where the client is a moderately intelligent terminal. Think back to the days where you had a mainframe in the bowels of a CS department and grad students logged in from glass terminals throughout the building. The terminal’s a dumb thing that can pretty much just display text and send text to you. It sends you whatever the user types in, and you send it what you want it to display.

Lesson One: The Client Is Always Stupid

The terminal is guaranteed to be smart enough to handle text scrolling and that’s about it. (And really, the only reason we assume it can scroll is because the original terminals were printers paired with keyboards.)

What does that mean? For starters, the client is not doing any layout. (I mean, it’s free to, but it never will.) If you send it a long line, it would be valid for it to cut the line off. In practice, clients wrap long lines by character rather than by word. So if your window is 25 characters wide, you might log into the MUD to see:

You see a large golden thr
oneroom filled with throne
s, each more regal than th
e last.

Let’s face it, if it’s possible for the terminal to do something wrong while technically doing what you tell it, it will. You must explicitly negotiate for anything you want the client to do. (And no, there’s no “wrap lines intelligently” option.)

Command stream

Interleaved within the data stream are commands. These commands generally deal with the terminal state and capabilities or the format of the data.

There are no guarantees about how commands and data are interleaved, and similarly there’s no guarantee about commands arriving in one packet versus several. This makes things annoying, to say the least.

Commands are distinguished from data by starting with 0xFF, and there are only a few formats allowed, so it’s not a Heraklean task to detect them. If you want to implement a non-compliant but mostly working telnet handler, you can easily just filter out the relevant octet patterns.

(If you happen to need a 0xFF in your data stream, just send it twice: 0xFF 0xFF is a command to send a literal 0xFF character to the client.)


Generally, a server wants to know what a client supports so it can send the appropriate stuff, and the client wants to advertise to the server what it expects so it can get input it can deal with. But neither can send something until both agree. So what you initially see is a negotiation.

For example, Telnet clients and servers are required to support 7-bit ASCII. However, many other encodings exist. In RFC 2066 (published in 1997), the IETF established a means for clients and servers to choose a different character set — the CHARSET option. To negotiate enabling the CHARSET option, we might see an exchange like:

server: IAC WILL CHARSET (255 251 42)
client: IAC DO CHARSET (255 253 42)

The first octet for every command is 0xFF, which the RTFs call “IAC”, or “interpret as command”. This makes it easy to distinguish commands from data. Our next octet was WILL, 0xFB, which indicates that the server is willing to deal with the option it’s discussing. It ends with the CHARSET option (0x2A), which is what it’s negotiating about.

The client responds in kind, but it replaces WILL with DO (0xFD). This indicates that it’s received the request and agrees. It could also have sent IAC DONT CHARSET to indicate that it can’t deal with this option. Both are legal and valid.

WILL indicates that the sending party is willing to do something, and DO indicates that the sending party expects the receiving party to do it. The client could send IAC WILL CHARSET instead of the server, indicating that the client wants to handle the character encoding negotiations instead of the server.

For many options, there’s not much difference if the client says WILL and the server says DO versus if the server says WILL and the client says DO.

Extended commands

So we’ve covered one format of command: IAC [WILL|WONT|DO|DONT] option. That’s a simple three-octet sequence. But our example was character set negotiation. How are you going to do this in three octets?

You aren’t. You need a longer format. Specifically:

IAC SB option payload IAC SE

Essentially, we have a command: “begin a subcommand for the following option.” This option value is the same as the one we used in negotiation. Then we have an option-defined payload of arbitrary values, followed by another command: “end this subcommand”. (There are different begin and end markers, so you could theoretically nest them. For your own sanity, don’t.)

For example, the server might advertise character sets it can use to send data to the client:

(255 250 42 1 59 85 84 70 45 56 59 73 83 79 45 56 56 53 57 45 49 255 240)

Here, the first subcommand contains the CHARSET-specific REQUEST code (0x1) followed by a literal ASCII string specifying the supported encodings, delimited by an arbitrary one-octet delimiter. That delimiter appears as the first octet in the sequence to avoid a separate step to agree on a delimiter.

Using the command stream as a side data channel

If the client and server agree on a protocol, you can use the command stream to send data rather than simply agreeing on connection properties. RFC 1073 (published in 1988) creates a protocol for the client to inform the server of its dimensions, for instance.

Specifically for MUDs, you may be interested in GMCP, the Generic Mud Communication Protocol. This lets you send a select collection of character stats from the server to the client.

What telnet options are interesting?


You want to use UTF-8. The protocol doesn’t support it natively; it assumes 7-bit ASCII. You have to negotiate for it. (Even if you want to use Extended ASCII, you have to negotiate for that, but it’s got a slightly different process.)

We saw an example above, of the server advertising which character sets it can support. A happy response would be:

(255 250 42 2 85 84 70 45 56 255 240)

Note that the delimiter is gone.

But the client doesn’t necessarily support any encodings that the server can provide. A sad response would be:

(255 250 42 3 255 240)

Negotiate About Window Size

It’s pretty damn essential to know how wide the client terminal is because clients don’t do wrapping. It’s also important to know how tall the terminal is — if you’re displaying a help file that’s 50 lines long, should you send it all in one go or paginate?

Discworld MUD has explicit settings for that. Wouldn’t it be great if you could automatically detect changes? If you could do the right thing for a client without the user having to deal with it?

How it works: you enable NAWS (code 31) using negotiation as covered above. Then the client can send an extended command about the window size at any point in time:

client: IAC SB NAWS 0 80 0 24 IAC SE
(255 250 31 0 80 0 24 255 240)

The payload is simply the width followed by the height as 16-bit values in network byte order — in this case, 80 columns wide and 24 rows high. If I were mudding on a truly monstrous display, I might send:

IAC SB NAWS 10 25 4 12 IAC SE

This would have a width of 10 * 256 + 25 = 2585 columns and a height of 4 * 256 + 12 = 1036 rows.

The client can send this at any time and should send it whenever the number of displayable rows or columns changes. That could be the window being resized, or it could be switching fonts or font sizes.

Negotiate About Carriage-Return Disposition

If you’re not familiar with this: remember how, with typewriters, you’d finish a line, then you’d need to move the paper forward (a line feed), and then you’d need to return the head of the typewriter, known as the carriage, all the way to the start? We brought that over into ASCII. I don’t know what we were thinking. In our defense, we were pretty smashed.

Telnet, by default, interprets a line feed character as a command to go to the next line but stay at the same column, and it interprets a carriage return character as a command to go to the start column while staying on the same line.

(As a historical note, UNIX-derived operating systems always used just the line feed character, ‘\n’, for this; Windows has always required the carriage return followed by the line feed, ‘\r\n’; and Macintosh around System 7 required just the carriage return, ‘\r’. Are we having fun yet?)

As is, you need to be careful to send ‘\r\n’ rather than just ‘\n’ for newlines. This is kind of annoying. Wouldn’t it be great if the client could interpret ‘\n’ correctly? It would be less work for you, definitely, and it would safeguard against some data handling problems.

How do you tell the client what sort of carriage return handling you want?

server: IAC WILL NAOCRD (255 251 10)
client: IAC DO NAOCRD (255 253 10)
server: IAC SB NAOCRD DR 252 IAC SE (255 250 10 1 252 255 240)

The value 252 is a magic number that just tells the client that it should handle carriage returns, but it might receive some carriage returns. In this case, it should just discard them.


GMCP is the Generic Mud Communication Protocol. It lets a MUD send specific types of data to the client, using the extended command stream as a data transfer mechanism. It’s also got some options for the client to send data back, including login information and the client name.

You might want to enable it just to get the client name. That lets you enable quirks modes for different popular clients. Yeah, it’s crud, but you need clients to work well.

One awesome thing that GMCP enables is auto mapping. As long as you have a stable unique integer to identify each room (sorry, LP MUDs), you can send sufficient data to clients that they can automatically generate maps for your MUD.

GMCP’s code is 201, and it has far too many options to list. I’ll just show a brief exchange:

server: IAC DO GMCP
client: IAC SB Core.Hello { "client": "Mudlet", "version": "2.1.0" } IAC SE
client: IAC SB Core.Supports.Set [ "Char 1", "Room 1" ] IAC SE
client: IAC SB Char.Login { "name": "dhasenan", "password": "it's a secret!" } IAC SE
server: IAC SB Char.Vitals { "hp": "10", "mp": "18" } IAC SE
server: IAC SB Room.Info { "num": 1200, "name": "The Hall of Immortals", "area": "gods" } IAC SE

No, I won’t!

Telnet allows you to negotiate about many things. Almost nothing succeeds.

Remember how clients don’t do word wrap? And how, for the past thirty years, it’s been possible to have the client send its window dimensions to the server? It would be really handy if the client would actually do that. Which ones do?

  • CMud: yes
  • GGMud: no
  • GNOME Mud: yes, and it helpfully breaks up its notifications into two packets just to thwart you
  • KildClient: no
  • Mudlet: yes
  • MUSHclient: no
  • telnet(1): no
  • tinyfugue: yes


Well, we’ve got the most popular Windows client and the most popular command line client, anyway. That’s nice, I guess…?

Okay, well, it would be nice if we could at least use a modern character set rather than this blasted 7-bit ASCII. What clients support negotiating about the character set? Or at least handle UTF-8 characters?

  • CMud: no; it looks like it does Latin-1 by default.
  • GGMud: no; it omits characters it can’t deal with.
  • GNOME Mud: no negotiation, but it seems to handle UTF-8 characters okay.
  • KildClient: no; it munges as if it’s Latin-1.
  • Mudlet: no; it also munges like Latin-1.
  • MUSHclient: no; also Latin-1.
  • telnet(1): no, but it blindly passes data back to the terminal, so UTF-8 usually works.
  • tinyfugue: no; it munges characters in a rather unique way (é -> C for some bizarre reason).

You begin to see, I think, why it’s so annoying to use Telnet.

Why bother?

If there’s no sensible client, why bother with all these neat and annoying options? Why waste your time implementing the negotiate about window size option if no clients will use it?

Well, first off, MUDs are often expected to support GMCP. So you have that much work to start with. And once you’ve done that, it’s only another couple hours to support window size and charset. You’ll want to support window size specifications using internal configuration options; telnet commands just offer another way of manipulating the setting — one you don’t have to explain to your users.

Character sets are incredibly important, and it’s disappointing that so few MUD clients support UTF-8. MUDs are one of the few games that work for blind people, and right now they’re restricted to people who know English and scant few other languages. Blind non-Anglophones deserve games, and right now it’s damn hard to find them.

Finally, there’s no pressure for clients to support options that servers don’t. By supporting it on the server side, you’re encouraging clients to support it.

Further reading

Telnet: PCMicro’s Telnet collation, which puts the constants you need and the RFCs you hate all in one place.

GMCP: Iron Realms’s writeup of the portions they support, which should be moderately comprehensive.

Procedural narratives: working toward an implementation

This is the start of the capstone to our discussion of actor-based procedural narratives. We discussed our goals, we described how to make decisions without referring to other actors, we described some potential improvements to that decision-making algorithm, we incorporated other actors’ actions into our decisions…

and now it’s time to write some code.

Before we do that, let’s look at the code we need to write.

We need:

  • the world
  • any background simulation (accounting for nature and other non-actors)
  • the mutations or possible actions
  • the basic elements of plot
  • a plot generator
  • an explainer

Now, we’ve implicitly discussed it, but let’s put this to the fore: we’re going to be producing tons and tons of possible worlds. We need a way to make these copies, be certain of not overwriting the actual world state, and process them as appropriate.

Using a functional programming language gives us security and copy-on-write semantics for free. We’re guaranteed not to overwrite the state of the world, ever. And many runtimes are smart enough to share unchanged state, which is awesome.

Another option is to store the decisions rather than the entire world state. This is a time/memory tradeoff; instead of storing world states, you recalculate them.

Previously we mentioned a constraint on the amount of prediction each actor does. We mentioned a number of possible worlds to evaluate at first. If we reinterpret that as a number of days in the future instead, we can change to a depth-first search. Now, instead of a queue of states to examine, we have a stack. This is much more efficient: you keep logarithmically many states in memory instead of a linear amount. However, it rather breaks best-first search, which previously allowed us to descend further along paths that seemed more promising. What we can do instead is probabilistically terminate processing on paths based on their depth and the expected utility.

In the context of a game, it should be relatively straightforward to identify the actions that can be taken. For a non-interactive work of fiction, it might be slightly harder. In either case, the plot is a heap of work.

Tune in next time and we’ll start the implementation. Maybe.

Connecting to OpenVPN with ChromeOS

Chromebooks are awesome, right? A limited computer managed by a mostly-trusted company with the option of turning into a full-fledged poweruser’s laptop. Light on the specs, usually, but almost always cheap. The “cheap” and “limited” aspects mean that businesses love putting them into users’ hands — the inevitable spilt coffee matters less, and there’s far less of a chance that someone will get malware on them and into the internal network.

Business laptops mean VPNs. VPNs mean distributing ovpn client configuration files. Let’s look at how to set up a Chromebook to use a VPN, shall we?

To start off, we’ll pop up to the network settings and hit “add connection”.

The ChromeOS network settings page, showing my current connection and an 'add connection' option.

Oh hey, there’s an option for OpenVPN — looks promising, but half your users haven’t even gotten this far. And now —

The ChromeOS VPN setup page. It's a form with ten entries: server hostname, service name, provider type, pre-shared key...

Sweet baby Maeve, what the hell is this?! On Linux I can just type “openvpn client.ovpn” and I’m done. On my Windows laptop I could just double-click the ovpn file. What the hell am I supposed to do with this? You’ve lost 90% of your remaining users.

Like the remaining 5%, I look it up on Google. Apparently I’m supposed to copy the <ca> tag’s contents into another file, same with the <cert> tag, and import them into the certificate store. These aren’t HTTPS certificates, and the only thing I see to install them says “HTTPS certificates”, but maybe it’ll work. So I try it and see:

Please enter the password that was used to encrypt this certificate file.

Yeah. Chrome? I didn’t encrypt the file. I don’t have the key, and I don’t think you need one. You’re being stupid now.

But fine. We’ve failed in the GUI; it’s on to the command line. I hold down the Escape and Refresh keys, void my warranty, delete all my local files, wait ten minutes, and fire up the command line. Corporate customers don’t have this option, remember, and most people don’t even know about developer mode. We’re down another 95%. And success! Openvpn is installed!

chronos@localhost / $ sudo openvpn client.ovpn ~/Downloads/client.ovpn
Enter Auth Username:dhasenan
Enter Auth Password:
CHALLENGE: Enter One-Time Password
50 lines of logging
/bin/ifconfig tun0 ...
SIOCSIFADDR: No such device
SIOCSIFMTU: No such device
SIOCSIFBRDADDR: No such device
tun0: ERROR while getting interface flags: No such device
Exiting due to fatal error

At this point, you’ve lost another 90% of the people who made it this far. If you started with ten thousand, you’re left with maybe two people willing to soldier on. I’m one of them.

Now. Openvpn is starting, and it’s connecting. If you know some stuff about networking on Linux (and probably half the people who haven’t been scared off yet probably do), you know that tun0 is a network device. Some digging online shows that ChromeOS networking is managed by a service named shill, it kills any network device it doesn’t think should exist. That includes /dev/net/tun0. So I hop back in the terminal, do a quick sudo killall shill, and — nothing.

Shill is being run by upstart. Upstart is the init system that ChromeOS uses. (It took some time and effort to discover this.) On a standard Linux system using upstart, you can type service shill stop to manually stop a service. So we do that here and… command not found.

At this point, I’m pretty much ready to give up. But I soldier on out of pure cussedness. I look through /sbin and see some symlinks named “start”, “stop”, etc. They’re linked to /sbin/initctl. Turns out I didn’t realize that “service” is effectively an alias to “initctl”. So I just run sudo stop shill and —

Oh hey, I’m not online anymore.

But I run sudo shill --help, which shows me I can just run sudo shill --device-black-list=tun0. That gives me networking again but hides tun0 (and therefore our VPN connection) from shill’s wrath.

Of course, this doesn’t fix everything! The openvpn command line client doesn’t set up DNS for you. So you need to find your DNS server’s IP address and manually edit /etc/resolv.conf to search it first. (This is a failing of Linux, not specifically ChromeOS. But it’s still another hurdle.)

Putting it all together:

  1. Turn on developer mode (hold down Esc + F3, restart, hit Control+D).
  2. Open a terminal (Ctrl+Alt+T, type ‘shell’, hit enter).
  3. sudo nano /etc/resolv.conf; add “nameserver” (replacing “” with the right IP) at the top
  4. sudo stop shill
  5. sudo shill --device-black-list=tun0
  6. sudo openvpn ~/Downloads/client.ovpn
  7. Enter username, password, OTP.
  8. Leave this tab in the background.
  9. When you’re done with the VPN, switch back to this tab and hit Ctrl+C.

And you’re done!

Now. If this set of instructions were made obvious to everyone, 99% of people wouldn’t want to void their warranty, another 80% would get lost, and out of that initial ten thousand, we’d have a full twenty who managed to get their VPN configured. As is, we probably get under 0.2% of a person for every ten thousand.

This situation is simply shameful.

If Google wanted to make this work as it should, it would be simple: maybe two days of UI work, a smidgeon of effort to copy your client file somewhere, and just shell out to the the openvpn command line client. Getting proper error messages would take some work; handling multifactor authentication would take some work; but still, assuming I was familiar with that part of ChromeOS, I could have it working in a week.

Will it ever happen?

Probably not.

An aside: there’s a ton of stuff in my ovpn file that has no place in the current ChromeOS VPN setup interface. I’m wondering, if I managed to plug in all the certificates and get ChromeOS to submit the right stuff, would it do the right thing? How would it know, for instance, to route to the VPN instead of the local network? That information is in the ovpn file, but there’s no place in the UI to put it.

Procedural narratives: explain yourself!

One of our goals in producing actors was to get them to explain their plans. You get to the climax, the big bad delivers a villain speech explaining everything, and you hear:

It was me all along! I hired Thekal the Orc for my Army of Doom! Then I hired Koho the Salmon-beast for my Army of Doom! Then I purchased a sickle sword for Thekal the Orc! Then I purchased a spear for Koho the Salmon-beast! Then I told Thekal the Orc and Koho the Salmon-beast to patrol the corridors of my Fortress of Doom!

And then, three chapters later, if you pay close attention, you find out that she was actually the one to kill your parents. But that’s only a third of the way through her monologue, because, though it was halfway through her rise to power, she had this geometric growth thing going on. So you’ve got another six chapters of villain monologue because your villain AI didn’t know how to explain itself properly.

I don’t know how to fix this. But I have a stub leading toward a solution.

The basic idea is that your AI should have small goals that lead up to a big goal. For instance, the villain’s ultimate goal was to rule the country. One level down from that, she had two goals: obtain the Talisman of Senatorial Mind Control to take control of the government, and raise an army to crush the remaining resistance. Another level down, and on the talisman side her goals are to obtain the Three Rods of Power and assemble them at Mount Doom, while on the army side her goals are to obtain equipment and recruit soldiers. In order to get the Rods of Power, she can use her army to raid the Temple of Aberzle (where the Rod of Air is stored), use money to purchase the Rod of Water (which a rich person is keeping as a curiosity), and steal the Rod of Fire from Castle Fira.

You end up with a tree, or at least a directed acyclic graph, of plans within plans. It’s pretty easy to generate an explanation from this. You might ask the Dark Lady Valeria, “Why are you doing all this?” And she would answer:

I want to rule the country, so I decided to obtain the Talisman of Senatorial Mind Control and raise a private army. I needed the Three Rods of Power to obtain the talisman, so I looted the Rod of Air from the Temple of Aberzle, bought the Rod of Water from Locke Cole, and stole the Rod of Fire from Castle Fira. I recruited 7,232 Orcs for my army and purchased 6,491 swords, 3,188 spears, and 7,445 shields for them.

It’s…not great, but it does include the important bits, in rough order of importance, and it’s straightforward how to include more or less detail. If you’re making these intermediate goals manually, you can specify whether it’s typically important to go into the details or not.

Putting it in context

This is a top-down planning system. Before we were working with a bottom-up system instead. How do we reconcile this? Should we switch to top-down entirely?

Well, maybe. The top-down approach mimics how a human would plan. It’s somewhat backwards temporally, and its success requires accurately predicting the results of all your actions. That can be costly — but on the other hand, failures look somewhat like human failures. (The AI might fail at a prediction no human would, but it’s still producing a plot that’s perhaps reasonable in isolation.) But the huge downside of a pure top-down approach is that it requires a human to manually plug in every single intermediate state. That’s just exhausting.

A hybrid approach lets you guide your AI a lot more. This reduces the amount of innovation it can generate — but let’s face it, I can’t reasonably implement something that can find a novel solution that takes more than about twenty timesteps in-game. If I could make such an AI, I’d probably be able to apply it to real-world problems and make bank.

This approach does let the AI innovate among a much smaller search space when generating plans. But with a smaller search space, it can’t really produce as much novelty. The AI can also innovate between the plan nodes, but here it’s hamstringed by a lack of processing power.

Still, I think this is a balance between writing by hand and automatic generation.

Next time, we’ll consider implementing this beast.

Procedural narratives: considering others’ actions

Last time, we explored a few ways to make planning tractable. But there was a huge caveat there: each actor assumed that no other actor was going to do anything. And that’s a huge issue.

Professor Quirrell had remarked over their lunch that Harry really needed to conceal his state of mind better than putting on a blank face when someone discussed a dangerous topic, and had explained about one-level deceptions, two-level deceptions, and so on. So either Severus was in fact modeling Harry as a one-level player, which made Severus himself two-level, and Harry’s three-level move had been successful; or Severus was a four-level player and wanted Harry to think the deception had been successful. Harry, smiling, had asked Professor Quirrell what level he played at, and Professor Quirrell, also smiling, had responded, One level higher than you.

—Harry Potter and the Methods of Rationality

Right now, sadly, our actors are all playing at level negative one. They don’t even acknowledge that other people can act.

Let’s say you have two actors, Alice and Carol. They know each other very well — they’re married. They both love salmon, and there’s salmon steak in their fridge. Alice gets home from work an hour before Carol, and she always eats as soon as she gets home. Carol might recall, as she is leaving work, that there is a salmon steak at home, and she might count on eating it for dinner. But this would demonstrate a minor lack of foresight. When she gets home, she will be disappointed and hungry.

This is a trivial example, of course, and one that happens all the time in real life. People make this mistake. But when it’s something I care about, something I am devoting my full attention and faculties to, and I know about these other actors, I will attempt to incorporate their probable actions into my plans. At present, our AI system will never do this.

How do we fix this?

Moving from level negative one to level zero requires simulating all the other actors that Alice knows about as level negative one characters. Instead of simulating the changes caused by Alice and nature alone, we simulate other characters using the previous level. At level zero, you acknowledge that others exist and will take some default action at every turn. That’s cheap enough. It’s also dead stupid, but at least it’s slightly less stupid than before.

The next step beyond this, of course, is to model everyone else as a level zero character. (You could use level negative one, but since that’s only slightly less expensive, there’s really no point.) This requires vastly more resources, of course, and that’s true of real life, too — we rarely consider how someone will react to our reactions to their reactions to our plans.

Since going beyond level zero is expensive, we want to do that as little as possible. That means, ideally, coming up with a heuristic to determine when to switch from level zero to level one — and we probably don’t want to bother implementing level two or higher.

Next time, we’ll see how we can get actors to explain their motivations.

Procedural narratives: obvious improvements

Last time, we talked about how to have an actor make plans. We provided an expensive algorithm for reaching decisions, a simple breadth-first search through a space of possible worlds. It worked, but it was hideously expensive. Let’s make it a little better.

Best-first search

The most obvious change is to be smarter about what nodes we search and in what order. We can switch from breadth-first search, which will analyze every possibility one step from now, followed by every possibility two steps from now, and so on until your computer starts sobbing; instead, we can use a sort of best-first search.

In breadth-first search, we maintain a queue of nodes. When we visit a possible world, we put a tuple into that queue consisting of the possible world and the path we used to get there. Also, for convenience, we store the score of that possible world in the same tuple (the crude approximation of its expected utility). We keep popping items from the queue, and each time, we insert all the worlds you can reach in one decision back into the queue.

In best-first search, we use a priority queue instead. The queue is keyed on the the world’s score. This lets us repeatedly take only the best world out of the queue each time and explore possibilities from there.

This works. It’s the standard solution. It has a glaring problem.

Let’s say the actor, Scarlett, wants a television. Secondarily, she wants money, at a rate of $10,000 equivalent to one TV. She has an option of preordering a television for $200, to arrive in thirty days. Or she can just go to work and earn $5. We’ve got enough processing budget to analyze four billion nodes, plenty to breadth-first search far enough to get the television in. (Four billion nodes is 31 days’ worth of simulation for all possible decisions.)

But we’re doing best-first search. So we’ll look at the first two options, see that one loses us $200 and the other gains us $5, and we’ll prefer the second, since it puts us $205 ahead of the other. And we’ll keep going on that branch, keep choosing to work, never choosing to buy the television. What can we do about this?

Simulate ahead

Instead of just looking at the state of the world immediately after making the decision, we can look ahead thirty days, assuming we always make some nominal decision (probably the decision to do nothing). This greatly increases the cost of evaluating each world, but it avoids stupidity like this. Since we previously had a budget of looking through four billion nodes, now we’ll only have a budget of looking through about 140 million. But that took us to 31 days before, and it takes us through 26 days now. But we see a potential world 56 days from now.

This obviously isn’t perfect. Let’s say Scarlett, in addition to earning money, has bills to pay. Bills cost $4.50 per day, and she has $200 in savings. In 26 days, she’ll have saved up another $13, and we assumed she did nothing for the next 30 days. That saw her $17 in the red. But in Scarlett’s home town of Southumberland, there’s no such thing as credit; there’s debtor’s prison. If she buys the TV, she’ll end up in prison next month, with no access to television and no money in the bank.

We can change this to make her nominal decision “go to work” instead of “do nothing”. I’m still worried about similar problems that will require more manual intervention to fix.

Echo utility backwards to the point of the decision

We created the world. We created the option to preorder a television — we’ve created delayed gratification. We can have our AI handle this explicitly, as long as the events are structured in a way to allow it. We can, for instance, use a linear scale in utility for delayed gratification, where we achieve X% of the utility of a television per day until it arrives.

Alternatively, we can use the concept of net present value. We might say that a television in a month is worth 5% less than a television today, and we compound that every month. That means we’ll prefer to preorder the television for next month, and we’d even prefer a preorder that takes five years to arrive. But around 75 months, it’s worth more to Scarlett to work than to take the time and money ordering the television. At 150 months’ delay, she wouldn’t even take time off work to get a free television.

This is utterly straightforward in simple cases like this: you have an event, you look up the utility of the result, you calculate a net present value from that. What about more complex cases? You could just assume the result happened now and simulate the world for one or two steps to see what happens. That’s another crude approximation, and it requires to simulate your entire world, but it only costs you a day or two each time.

These are all simple, straightforward techniques, but they require you to be able to simulate quickly.

Machine learning

You can create a neural network that attempts to associate decisions with effects. This is a more holistic approach, and once you build the neural network, it’s going to be reasonably fast. However, neural networks require a lot of time and data to train, and they’re often rather large. Since we’re talking about procedurally generated actors, the network has to match the current collection of actors as well as the current state of the world.

Given the amount of data to match and the range of possibility generally available, you’re going to spend a ton of time with the game running a different AI just to feed a giant neural network.

In my case, I’m talking about a game that might have a large number of players. That would end up with me paying for a bunch of large AI servers just hosting this neural network, and players would have to be online in order to play. If I ever shut down the servers (for instance, because they cost a couple hundred dollars a month to keep running and I’m not seeing any revenue), my players wouldn’t be able to play the game.

Neural networks are not an option for me. But if you’re generating a novel, you might be able to use them.

Just be warned, neural networks aren’t good at explaining their reasoning. It’s usually important for a story that characters be able to explain their reasoning.

Next time, we’ll look at incorporating other actors’ actions into one’s plans.

Procedural narratives: making decisions in isolation

In the previous entry, we said that the first two steps in creating a procedural narrative were to enumerate options that actors can take (including their immediate results) and to implement a naive graph search.

Let’s define this more concretely. The nodes in the graph are possible world states, with the start node being the current state. The edges are decisions. In this simple version, they are all decisions that the current actor could take. You can just breadth-first search your way through the graph, stop when the AI budget for this actor has been reached, and go with the best option you’ve found so far.

That’s straightforward — but how do we define “best”?

The best possible world state is the one that matches the actor’s goals most closely. In order to make this definition tractable, we require our goals to be formatted in a specific way. For instance, one goal might be to have a world under this actor’s control reach a population of fifty million. This is an excellent goal for our system because we can simply find the highest population planet under the actor’s control, subtract its population from the target one, and get a distance metric for that goal.

However, an actor can have multiple goals. To manage tradeoffs between them, we need to normalize these metrics according to their importance to the actor. This isn’t utility, really — it’s quite possible that it’s useless to have a planet of 49 million and worth everything to have a planet of 50 million. It’s not quite expected utility, either, but it’s a crude approximation of expected utility.

Once we have that, we can determine, for a given actor, how good a particular possible world state is. And that lets us find a preferred future.

Now that we’ve got that sorted out, we can take a look at potential refinements.

Procedural narratives: goals and outline

I started working on a space empire management sim game. It was simple, it was doable — and then I realized, even before I had anything rendering, that it promised to be boring. I needed something to spice it up. And I quickly decided on factions and duplicitous intrigue. That quickly leads to a problem: play time per unit work drops. What can I do about it?

The obvious answer: procedural content generation. That’s one of the tactics employed by games from Nethack to Diablo III. But how do I generate intrigue dynamically? Again, the obvious answer: create characters dynamically and give them plentiful duplicitous tactics to achieve their goals.

This rather requires some artificial intelligence. Now, a general artificial intelligence is so far infeasible, and I’m not going to invent it just for a game. However, I can develop a restricted artificial intelligence that can choose from a menu of options I lay out before it and make sensible choices.

My rough outline for how to do this is:

  1. Create a set of options that an actor can take.
  2. Create a naive search between options and goals. This assumes the actor acts in a void and everyone else is a robot.
  3. Refine the decision making algorithm.
  4. Develop a way for characters to explain their decisions to the player, since it’s guaranteed to come up.

Steps 1 and 2 are pretty easy to implement. I just need my simulation to be fast — or at least, I need a fast approximation. Step 3 is “here there be dragons” territory. I’ve got some ideas, but they’re pretty expensive — recursive modeling of others’ decisions given that I make a particular decision, for a start. Step 4 is a little scary — it hinges on identifying which decisions were important. That’s not going to be easy. But I’ve got half an idea on how to make that easier and possibly ease some of my other processing.

Tune in next time and we’ll go over the easy parts in a little more detail.

Diversity and the Hugos

Background: the 2015 Hugos were the most contentious ever, largely thanks to two groups working in concert: the Sad Puppies and the Rabid Puppies. They both oppose what they see as Social Justice Warriors interfering with their awards. Notably, the ringleaders tend to be people who were nominated for a Hugo but failed to achieve one — an honor in itself.

From Amy Wallace’s article on the 2015 Hugos:

On the phone from the Middle East, where he is currently deployed, Torgersen lamented what he called “the cognitive dissonance of people saying, ‘No, the Hugos are about quality,’ and then at the same time they’re like: ‘Ooh, we can vote for this author because they’re gay, or for this story because it’s got gay characters,’ or, ‘Ooh, we’re going to vote for this author because they’re not white.’ As soon as that becomes the criteria, well, quality goes out the window.”

There are many aspects to how good a work is. In large part, it’s determined by what your audience wants. Your work is better when you avoid tropes that have been overused too much recently. It’s improved, often, by novelty, which depends mostly on what other people have been writing in the past few decades. Another thing that determines whether someone thinks your work is good is whether they personally can relate to any characters in it. That’s a lot more subjective a measure, but it’s still there.

Authors from marginalized groups offer different perspectives. This allows them to gain points on the novelty front more easily. Some tropes actively harm people from marginalized groups, and those people are generally aware of that fact and more likely to avoid those tropes — or engage with them directly, which can also be quite interesting. They are more likely to include people from their own groups in representation. And since the more commonly represented groups are so well represented, these authors have a plethora of examples to draw from when portraying characters not from their group.

For example: sci-fi books are skewed toward having male protagonists. A simple way to be slightly fresher is to have a female protagonist. A female author can do a better job of this than a male author, on average. Her male characters may be slightly less satisfying than a male author’s, but they’ll be pretty good because she has tons of excellent examples to imitate. Her personal experiences of being a woman will make her female characters much better.

But we should value the quality of the portrayals instead of the marginalization of the author! you may cry. Let me tell you a parable.

Internationally, almost everyone thinks that kiwi birds are fifteen feet tall, weigh several tonnes, and frequently tear apart cars to get at the juicy humans inside. They spray acid from their beaks and can fly. You grew up in New Guinea and have seen kiwis for yourself. They’re birds all right, and they’re called kiwis, but they max out at like a kilo and are fuzzy little harmless things that can’t fly and would run away from you sooner than attack. They don’t eat anything larger than a frog. And there’s nothing around that flies and tears apart cars.

Now you want to write a story about New Guinea. Every story you’ve read about the area features kiwis tearing up cars and flying away. And every story you’ve read about the area is by someone who’s never been there. You write accurately according to your experiences there.

In this scenario, two things are immediately obvious: your personal experiences let you write more accurate portrayals, and it’s unlikely you will be believed. However, I as a reader interested in accurate portrayals of New Guinea will prefer your account because you have appreciable experience with the area.

Similarly, I will prefer to read women’s portrayals of women over men’s portrayals of women. I will trust them more. Similarly with people of color, homosexual / bi / pan people, non-binary and trans people…

In short, we want novelty, one type of which is novel perspectives and characters of types we haven’t experienced very often. We expect the best portrayals to come from people like those characters, and we expect that most authors will be able to do a good job on the more common types of characters. Therefore we tend to promote authors who are members of marginalized groups. It’s not a reflexive “this person’s from a marginalized group, therefore give them awards!” thing. It’s a question of trustworthy quality.