Blog Brag, with Numbers

I had Many Achievements today that I want to brag about:

• 9 hours of work, only 1 of which was a meeting (I don't know how people put in 8 hours of real, actual work in a day. Do most people really do this? I guess most people in service industries and skilled/unskilled labor do. I'm amazed by this.) (I know I should count achievement of goals instead of hours spent -- hours are on the "cost" side of the balance sheet -- but in my case hours and achievement scale together, more or less.)
• 3 meals, including plants in each one (oatmeal and blueberries; salad (greens, carrot, and bell pepper) and a quesadilla; salad (same) and PBJ; ice cream)
• ~32 emails sent
• ~7 dishes and ~7 silverware washed
• 17 is the level I reached in Hearthstone :)
• 1 call to Grandparents

It was a really unusually good day, according to my metrics. Less time with K than I would have liked, so we'll have to see how I can fix that.

Brilliance, blunders, and backfires

In AlphaGo's recent play, there were two kinds of moves that stood out:

• Brilliant moves: moves that accomplish the system's goal – winning the game – in ways that a human wouldn't think of, and that might take a while to even be understandable in retrospect (or might elude our understanding altogether).
• Blunders: moves that humans can identify (though sometimes only in retrospect) as bad for the system's goal.

As AI systems become more capable, it will be harder to tell the difference between brilliant moves and blunders until their effects are felt, and even in retrospect they may be hard to diagnose. If hard-to-understand AI systems are given safety-critical or high-impact tasks, blunders could become a source of significant harm.

However, I think we should be at least as concerned about a third kind of behavior:

• Backfires: moves that accomplish the system's nominal goal, but that don't do what the user actually wanted or that have unintended side-effects, and that might only be identified as backfires in retrospect.

Like blunders, we have the challenge that backfires won't easily be distinguished from brilliant moves. Backfires bring additional challenges; unlike blunders, improving a system's ability to achieve its nominal goals won't fix backfires, and may actually make them worse:

• A backfire might accomplish what we really wanted, but with additional effects that we don't want – getting a ball into a hoop while also smashing every vase in the room, or making a cup of coffee while also lighting the house on fire or breaking the law. As systems become more capable, they will be able to cause broader effects, making this problem worse.
• A backfire might accomplish the nominal goal without accomplishing what we really want, e.g. by manipulating a reward signal directly instead of by winning games of Go or Atari. As systems become more capable, they will find more ways of accomplishing their nominal goals, making this problem worse.

Backfires could happen because it's difficult to specify in full what we want a system to accomplish and what unintended consequences we want it to avoid, difficult to know in advance what means a system might use to accomplish its nominal goal, and difficult to specify goals in a way that can't be "gamed".

A "new" Magic: the Gathering format

The rules:

• Put all your non-land cards in a big pile. (You can include lands with cool abilities in this pile.) This pile will be both players' decks.
• Put all your lands in a big pile (face up so you can tell the difference). This is the land deck. Whenever a player does something to a deck, including drawing cards, they get to choose the land or the non-land deck. (This includes drawing your opening hand.)
• All lands tap for any color of mana and have all basic land names and types. They basically count as any basic land all the time.
• Players share a graveyard.

Why I like it:

• Basically no setup
• Minimal mana or color problems
• Optimized for things happening during the game, rather than i.e. skillful play, deck-building interestingness

I expect that this will be my default way to play in the future; it's awesome!

I thought that playing with a shared deck of cards selected kind of at random was called "Wizard's Tower" (because of the tall shared deck), but it looks like I'm wrong; I vaguely recall a similar concept called "Mass Magic" or something, but a bit of Googling gives me nothing. Dan and I added the separate land deck after the first couple of games, but it turns out that there's a format with basically these rules called fat stack. The "every land counts as all basic lands" doesn't appear in any shared-deck formats that I found, but I wouldn't be surprised if someone else thought of it first; it's pretty obvious.

I think I'll make my Star Wars card game (a project I haven't blogged about, but that I probably will blog about in the future) like this; it's a more streamlined experience, and realistically nobody's going to be building decks for my hobby game design project anyway :)

Langton's ant

I've been thinking on and off about Langton's Ant. It bugs me that nobody's resolved the conjecture about the ant eventually building a highway (I'm going to assume you looked at the wikipedia page, and not explain things again here!). I thought it'd be a fun recreational math problem to poke at, and I can now at least say that it is fun!

Today, I started out wanting to implement Langton's Ant in javascript, just to have something to play with. Implementing things like this is always interesting, because there are typically a lot of ways to write the program that are kind of annoying and painful; for example, in this case, you could encode the 2D grid the ant lives on as an array, but arrays in javascript have finite size, and so you'd have to watch closely to make sure the ant doesn't run off the edge of the array and then resize it... ugh.

Instead, I thought I'd just keep a list of locations that the ant has visited. Then, you can calculate the color of the ant's current location by checking how many times the ant's been there before. However, since the ant's rules are written from the perspective of which way the ant is facing ("turn left" or "turn right"), deciding whether the ant moves up, down, left, or right depends on the last two moves and also the color of the square. This is only mildly annoying to code, but I'm very lazy, so I kept trying to cut down the complexity.

Next, I thought I'd keep a list of move directions, like "uldrurdrd...". This would make calculating the next step easier. Interestingly, with this representation, you don't need to keep a list of positions at all -- all of the information about which squares the ant has visited is encoded in the sequence of moves! To know the color of the current square, count the number of times it has been visited before, which is equal to the number of prefixes of the move sequences where (number of up moves minus number of down moves) and (number of right moves minus number of left moves) are the same as these properties of the whole string. I wrote a (probably buggy) program based on this idea (see end of post).

This got me thinking, though, about the overall problem of the highway conjecture. In this representation, the highway appears as a repeating sequence of (up, down, left, right) moves. This is kind of nice, because it makes it easier to see when the ant has hit the highway; this sequence is kind of like an attractor, or something.

We now have, instead of an ant on a grid, a system for generating the next letter in a sequence. Given a list of letters, the next letter is determined by:
- The last letter
- The parity of the number of substrings with the same properties (u - d) and (r - l) as the overall letter sequence

This system could be generalized in a variety of ways. Using e.g. modulo 3 or 4 instead of parity would add more colors, and it's interesting to me that we could use properties other than (u - d) and (r - l) -- for example, ratios or more complex expressions.

I'm not sure, but I feel like this is incremental progress toward solving the conjecture, which makes the whole thing feel worthwhile :) If I can make more progress, you'll hear about it in a future post.

A final note: Langton's Ant is reversible, so theorems that hold into the future also hold into the past. For example, not only will the ant get arbitrarily far away from its starting point (see wikipedia), it also came from arbitrarily far away if you assume it's been running forever. If the highway conjecture is correct, ants not only eventually build highways, they came from highways, unwinding them from the infinite distance until they got to their starting point! That's kind of neat.

⁂

The program:

function move(ms) {
 possible = ({u:"lr", d:"rl", l:"du", r:"ud", "":"ud"})[ms.slice(-1)];
 x = ms.split("r").length - ms.split("l").length;
 y = ms.split("u").length - ms.split("d").length;
 console.debug(x+", "+y);
 color = 0;
 ms.split("").forEach(function (c) {
  x = x - (c=="r"?1:c=="l"?-1:0);
  y = y - (c=="u"?1:c=="d"?-1:0);
  if (x == 0 && y == 0) color = -color+1; // wrong here to include last character? Does this just invert?
 });
 return ms + possible.charAt(color);
}

Non-post for March 12

I played Magic with friends instead of writing a blog post today! I regret nothing.

Projecting maps by travel time

Maps where something else is used instead of distance or area (e.g. population, GDP, travel time) are called cartograms. Apparently maps where distances correspond to travel times are called linear cartograms, but this seems like kind of a bad name. I'll call them travel-time cartograms instead.

You could think about different parts of the 2D surface of the Earth as having different speeds when you cross them by some mode of travel (trails are easy to walk on, mountains are hard to walk up but easy to walk down, and water can't be walked on at all), and try to make a map that way. The mountain case tells us that when travel time depends on direction, a travel-time cartogram can't be made, i.e. the distance between the top and bottom of a mountain must be two things at once. I guess you could take an average, but I don't like that much -- it seems to destroy or hide a lot of information. Instead, I'll consider different modes of travel, and assume that direction doesn't matter.

I think three modes of travel (plane, car, walking) might be the sweet spot in terms of accuracy vs. difficulty, but two modes of travel is complicated enough to bring out the conceptual issues, and airplanes change our travel time around the world much more than cars do. Airplanes are pretty weird -- do you consider the points along the plane's trajectory to be quickly reachable, or do you imagine the plane disappearing from one airport and then reappearing at the other end? I'll use the time-delayed teleportation model, since I can't really get places by parachuting out of a plane. So, my first-approximation travel-time cartogram should have this property:

The distance between any two points is the minimum travel time by a combination of air travel and "land travel" (a continuous form of travel at 30 miles per hour, a rough average of car and foot travel)

What happens when I try to build this map?

• Major cities and their neighborhoods should be near each other.
• Far from airports, the map should approximate a globe (since only land travel is relevant there).
• Any shortest line between two points (along the surface) should correspond to the shortest trip between them (i.e. it should point-for-point cover the same route as the shortest trip).
• There are points on the surface between the major cities that don't correspond to points on the globe, so that travel between airports isn't immediate, but you also can't parachute out of the planes.

Instead of working with a globe, let's start with a circle (a slice of the sphere, where travellers can move only along the circle between points) and add two airports that can be moved between quickly. What we need to do, it seems to me, is bend the circle through the third dimension until the airports are near one another in 3D space, then add a line between them of length equal to the travel time. It's important to note that distance on this cartogram isn't measured in raw Euclidean terms, but instead by distance along the surface itself (just like on a globe, you measure distance along the surface instead of tunneling through the earth). If you add more airports, then it's like folding the circle up so that many points on its circumference nearly meet.

In fact, if we assume that airplanes all travel at the same speed along this circle, then you can make a separate surface corresponding only to air-travel, with points corresponding to airports and edges corresponding to flights, and this surface will be curved overall like a circle. So, we have a large "land-travel circle" and a smaller, nodes-and-edges "air-travel sphere", and we can make the final map by folding the larger circle through 3D space so that its airports meet the smaller circle's airports.

To get back to the real world, "all you have to do" is make a land-travel globe (which looks like a normal globe), an air-travel "globe" (a smaller web of connections between airports that is overall curved like a sphere), then fold the land-travel globe through the fourth dimension so that its airports meet up with the air-travel globe's points. That's pretty awkward, because now we have a 4D map that is going to be really hard for humans to read and get intuitions about!

To flatten a globe into a map in a way that lets humans understand distances, we sometimes put a grid on the sphere as guidelines for humans. Can we do a similar thing here -- put a grid on our 4D map, cut and flatten it, and then print it out? Not sure, but that seems like what we want to do!

Lots of presents

I just noticed a funny thing. I'm traveling for work, and I'm very picky about what I bring; I'm a light packer (one shoulder bag for a week trip), but I like to be as prepared as possible. Here are some of the things I have with me:

• Timbuktu bag (present from my parents)
• Down vest to stay warm (present from my parents)
• Rain jacket (present from my parents)
• Spacepak clean/dirty clothes bag (wedding present I think?)
• Socks (present from Killian's parents)
• Headphones (present from Killian)
• More socks (present from Killian's parents again!)
• Peacock-feather-pattern dress shirt (present from my parents)

Isn't that nice? I think the majority of the things I have with me are presents from someone! And I'm staying with friends, so that's like a present, too. I have a reputation for being hard to buy presents for, but apparently people are doing great at it!