The Infinite Card Game

  • 02.28.2018
  • etc

Kira and I were in Australia most of last month, and near where we were staying in Melbourne was a game shop. We had a free Friday night so I stopped by for my first Magic: The Gathering (MTG) draft event, and it got me thinking about designing card game systems.

MTG is a collectible card game with a great deal of strategic depth. Games with large state spaces like Chess and more recently Go have been more-or-less "solved"1; The state space of MTG is certainly orders of magnitude larger than Chess and Go, given the massive back catalog of cards (going back to 1993!)2 and the ever-growing number of interactions between them. Though the state space of Starcraft is likely larger (and people are working on "solving" it), to my knowledge MTG has not yet been solved in this sense.

For those unfamiliar with MTG, it's played between two or more players and involved constructing a deck of cards around a particular strategy. Some strategies may emphasize fast, aggressive plays ("aggro") which, if failing to win quickly, lose steam in longer matches. Others may focus on slowing opponents down by stopping plays short or making actions more expensive ("control"). And there are other strategies still.

MTG has a variety of game formats which govern how decks are constructed and can affect other game rules. These formats are broadly divided into Constructed and Limited formats. Constructed formats are where players carefully design and assemble their decks in advance. This gives plenty of space for creative, expressive strategies since players have a large pool of cards to select from. In contrast, Limited formats mean that players are given a small amount of random cards drawn from a set of cards and need to assemble a deck on-the-spot (a process called "drafting").

I've mostly played Constructed formats, but now that I've tried Limited a bit more I'm coming to prefer the randomness and uncertainty of Limited formats. In Limited you have to think on your feet more, design your deck more delicately (you aren't sure what to expect from your opponents), and work within a tighter set of constraints. It makes for more challenging and exciting games.

The problem with Limited is that each set has roughly 200-300 cards. After a few games you'll be familiar with every card and players have learned the strategies that work best within that set. Games start to get formulaic and stale. It loses that sense of uncertainty that makes Limited exciting in the first place. It isn't until the next set is released, with new cards and abilities, that things are interesting again.

These sets are carefully designed such that the cards have enough variation to keep things interesting, but not so much that they're totally incoherent (Mark Rosewater, the lead designer of MTG, has a great podcast delving into this design process). And they are meticulously balanced so no strategy is strictly better than any others.

That being said...I wonder if there's a way to design an infinite set, i.e. a dynamic and self-adjusting process which outputs a stream of cards to draw from for a never-ending Limited format. Such a system would need some rule scaffolding or framework (doesn't have to be MTG's) from which it can derive new mechanics and costs (some quantifier of their power), and then generate a balance of cards over some probability distribution.

For example, a core mechanic in MTG is that you have creatures that can attack opponents to damage them. Players can use their own creatures to "block" opponents' attacking creatures. These creatures have some cost to play ("cast") them; generally stronger creatures have the drawback of costing more to cast. Sometimes they may have other abilities which make them more or less versatile, which is compensated by a respective increase or decrease in casting cost. Sometimes you have creatures which are disproportionately cheap in casting cost for their strength, but these are rare.

Let's say the game for this infinite draft system has just this simple attacking-creature mechanic. Our creatures have only a strength and a casting cost. Generally, the stronger the creature, the higher it's casting cost. But not always -- on rare occasions we might have a strong creature that's a bit cheaper than normal. Finally, we add the additional constraint that weaker creatures are more likely, so we emphasize strong creatures as a more notable event.

What we're essentially saying is that the casting cost of a creature is dependent on its strength (and vice versa), which we can represent as a simple Bayes net:

G strength strength casting_cost casting_cost strength->casting_cost

When we want to create a new card, we can first sample its strength, then sampling a casting cost depending on the value we sampled for its strength.

We want a creature's strength to be a positive integer, say in the range $[1, 12]$. So we want a discrete probability distribution with finite support. We could use a Beta-binomial distribution, e.g. $\text{BetaBinomial}(\alpha=2, \beta=6, n=12)$, which has the properties we want:

$\text{BetaBinomial}(\alpha=2, \beta=6, n=12)$
$\text{BetaBinomial}(\alpha=2, \beta=6, n=12)$

Here creatures will tend to have a strength somewhere in $[1, 4]$ and very rarely above 6. Then we can do something similar with casting cost, except that it's dependent on the strength.

This is an extremely simple game and so not a very interesting one. We'd want to add in additional abilities that interact in interesting ways. For example, in MTG the "flying" ability makes a creature blockable only by other creatures with flying. So we can add in some small probability of a creature gaining flying, and have that also affect the casting cost's distribution.

MTG's Flying mechanic

A really nice version of this system is one where you can pass in an arbitrary network relating costs and abilities (a more complex example of the one above), and it would output card descriptions in some interchange form (e.g. JSON), and you can use that to print cards with whatever design you wanted.

A few years ago I prototyped a similar system of cost-based card generation, which incorporated different card types beyond creatures (which I called "units"), additional abilities, and procedurally-generated names.

An example generated card
An example generated card

This prototype doesn't incorporate intra-card balance beyond what falls out of cost-balanced cards. The relative effectiveness of various abilities are really hard to objectively quantify, since their costs are really relative to what the dominant strategies are, i.e. the metagame. So ideally this infinite draft system not only generates balanced cards but also tracks how people are playing them to learn which strategies seem over or underpowered, and correspondingly tweaks the costs of abilities related to those strategies.

The generation features I just described are more about balance but another interesting feature would be introducing a balance-drift so that gameplay never stagnates in an equilibrium of strategies. Perhaps once balance is achieved the system can gradually and temporarily bias the game towards different strategies to encourage different kinds of gameplay. That way there'd be an ebb-and-flow that keeps things interesting in the aggregate and subtly changing the overall feeling of the game.

For example, if the system sees that players almost exclusively play low-strength, cheap creatures, and almost no larger creatures, maybe it will start to slightly cheapen the larger creatures so they see more play. That in turn may cause a new strategy to dominate, maybe a slower gameplay with larger creatures, and eventually a different change would be introduced to shock the system to a different strategy equilibrium.

I've given a very hand-wavy outline of this system here and as described it by no means would match MTG's hand-designed depth and complexity. But I do like the idea of a general system where you input some mechanics and it outputs a series of cards to play a game with. You could, perhaps, model many different systems via a card game format this way.



  1. Not solved in the proper sense, but human players are reliably bested by computer players. 

  2. Based on mtgjson.com's data, there are 18,191 unique cards as of Jan 21, 2018. 


Public transit routing

For the transit demand model for the PolicySpace project (see previously) we needed to be able to ingest GTFS (General Transit Feed Specification) data and use it to generate public transit routes. That is, given a start and an end stop, what's the quickest route using only public transit? Ideally we minimize both travel time and number of transfers, or strike some balance between the two.

I found an existing implementation here, based off of the papers Trip-Based Public Transit Routing (Sascha Witt, 2015) and Trip-Based Public Transit Routing Using Condensed Search Trees (Sascha Witt, 2016). The routing worked fine, but processing the Belo Horizonte GTFS data (630 routes with 9,428 stops, including buses and metro) took over 12 hours. The routing itself did not seem to have a significant speed gain from this pre-processing (unfortunately I don't have specific numbers on hand).

Instead I spent the past few days implementing my own public transit routing algorithm. It's a first attempt, and so it's naive/not heavily optimized, but so far seems to work alright. The goals were to significantly reduce pre-processing time, have a relatively low memory footprint, and quickly produce routes.

First, it's worth explaining a bit about how GTFS data is structured and the terminology it uses.

Public transit has a few components:

  • stops: same as the colloquial usage; a ๐Ÿšstop is somewhere a bus, train, etc stops to pick up and drop off, described with an id and a latitude and longitude.
  • trips: a ๐ŸšŒtrip is a sequence of stops associated with a set of arrival and departure times. For example, trip ๐ŸšŒA goes through stop ๐ŸšX at 12:00, then stop ๐ŸšY at 13:00, then stop ๐ŸšZ at 14:00. Trip ๐ŸšŒB goes through stop ๐ŸšX at 13:00, then stop ๐ŸšY at 14:00, then stop ๐ŸšZ at 15:00. Even though they have the same stop sequence (๐ŸšX->๐ŸšY->๐ŸšZ), they arrive/depart from each stop at different times, so they are distinct trips.
  • route: a route is a collection of trips. A route's trips do not necessarily mean they share the exact same sequence of stops. For example, a route may have a trip that goes ๐ŸšX->๐ŸšY->๐ŸšZ and another trip that only goes ๐ŸšX->๐ŸšY. (I didn't use this data and it's confusing because we're using the term "route" to describe something different. This is the last you'll see this particular usage in this post.)
  • service: a service associates routes with days of operation (e.g. weekdays, weekends, off or alternative schedules on holidays, etc).

With these terms defined, we can define a public transit "route" more specifically as "a sequence of trips and their transfer stops". This is a bit more specific than how we describe routes conversationally, which is more like "take the Q line and transfer to the M at Foo Station". Instead, what we're after is more like "take the 12:42 train on the Q line, transfer to the 13:16 M at Foo Station".

GTFS data includes a few files (which are essentially CSVs but for whatever reason use the txt extension); the important ones here are:

  • stop_times.txt: describes stop sequences for trips, as well as arrival and departure times for each trip's stops.
  • stops.txt: describes stop latitudes and longitudes

We use some of the other data files as well, but those are more for juggling stop and trip ids and less core to the routing algorithm.

Transfer network: structure

The general approach is to generate a transfer network which describes at what stops are various trips linked together (i.e. where transfers can be made). The nodes of this network are described as (trip_id, stop_id) tuples. Note that not all stops of a trip will be nodes in the network; only those where transfers are made. Our resulting route only needs to return trips and where to transfer, not the individual stops within trips. That's something we can easily lookup later using the stop_times.txt data if needed.

The edges of this network can describe two different things:

  • inter-trip edges: If an edge connects two nodes which share a trip_id, e.g. (๐ŸšŒA, ๐ŸšX)->(๐ŸšŒA, ๐ŸšY), it indicates in the network structure that these nodes are along the same trip. Here the edge weight indicates travel time between stops ๐ŸšX and ๐ŸšY for trip ๐ŸšŒA.
  • transfer edges: If an edge connects two nodes which don't share a trip_id, e.g. (๐ŸšŒA, ๐ŸšX)->(๐ŸšŒB, ๐ŸšX) it indicates a transfer between trips, e.g. transfer between trips ๐ŸšŒA and ๐ŸšŒB at stop ๐ŸšX, and the edge weight indicates estimated transfer time.

We also need to distinguish between direct and indirect transfers:

  • a direct transfer is one where the two connected trips share a stop. For example, (๐ŸšŒA, ๐ŸšX)->(๐ŸšŒB, ๐ŸšX) is a direct transfer because these trips both share the stop ๐ŸšX.
  • an indirect transfer is one where the two connected trips do not share a stop, but there is a reasonable footpath between the stops (i.e. you could walk between stops under some threshold transfer time limit, e.g. 5 minutes). For example (๐ŸšŒA, ๐ŸšX)->(๐ŸšŒB, ๐ŸšY) where stop ๐ŸšY is around the corner from stop ๐ŸšX. By introducing these additional edges, we potentially find shorter routes or routes where there normally wouldn't be one.

The transfer network is directed graph. This is due to the forward arrow of time. For example, trip ๐ŸšŒA arrives at stop ๐ŸšX at 12:10 and the ๐ŸšŒB departs from stop ๐ŸšX at 12:20, which indicates a valid transfer from trip ๐ŸšŒA to ๐ŸšŒB. However, I can't make the transfer in reverse; if I'm on trip ๐ŸšŒB and arrive at ๐ŸšX, trip ๐ŸšŒA has potentially already departed from ๐ŸšX. If the situation was that trip ๐ŸšŒA lingers at ๐ŸšX for long enough that the transfer does work in the reverse direction, we'd just have another edge (๐ŸšŒB, ๐ŸšY)->(๐ŸšŒA, ๐ŸšX).

Transfer network: generation

The pre-processing step is almost entirely the generation of this transfer network. Once we have this network it's relatively easy to generate routes with Dijkstra's algorithm.

The generation process is broken into three parts:

  1. Generate direct transfer edges
  2. Generate indirect transfer edges
  3. Generate inter-trip edges

Direct transfer edge generation

We can use the stop_times.txt file to identify direct transfers. We group rows according to stop_id and look at the trip_ids under each group. However, we can't just create edges between all these trips here; we have to filter in two ways:

  1. down to valid transfers (those that obey the arrow of time). As noted before, a trip ๐ŸšŒA can only transfer to a trip ๐ŸšŒB at stop ๐ŸšX if trip ๐ŸšŒA arrives at ๐ŸšX before trip ๐ŸšŒB departs.
  2. for each equivalent trip, select only the soonest to the incoming trip.

Expanding on 2): we assume that travellers want to make the soonest transfer possible from among a set of equivalent trips. Equivalent trips are those that share the same stop sequence, regardless of specific arrival/departure times. For example: a trip ๐ŸšŒA with stops ๐ŸšX->๐ŸšY->๐ŸšZ and a trip ๐ŸšŒB with stops ๐ŸšX->๐ŸšY->๐ŸšZ share the same stop sequence, and so are equivalent.

Say we have a trip ๐ŸšŒC that also stops at stop ๐ŸšX, arriving at 12:10. Trip ๐ŸšŒA departs from ๐ŸšX at 12:20 and trip ๐ŸšŒB departs from ๐ŸšX at 12:40. We only create the edge (๐ŸšŒC, ๐ŸšX)->(A, ๐ŸšX) and not (๐ŸšŒC, ๐ŸšX)->(๐ŸšŒB, ๐ŸšX) because we assume no person will wait 20 extra minutes to take ๐ŸšŒB when ๐ŸšŒA goes along the exact same stops and departs sooner.

This assumption greatly reduces the number of edges in the network. With the Belo Horizonte data, this assumption cut edges by about 80%, roughly 18.5 million fewer edges!

Indirect transfer edge generation

To generate indirect transfers, we use the following process:

  1. generate a spatial index (k-d tree) of all stops
  2. for each stop ๐ŸšX, find the n closest stops (neighbors)
    1. for each neighbor ๐ŸšY:
      1. compute estimated walking time between ๐ŸšX and ๐ŸšY
      2. create edges between trips going through ๐ŸšX and ๐ŸšY, sticking to the same constraints laid out for direct transfers (valid and soonest equivalent transfers)

The network edge count and processing time vary with n. Increasing n will, of course, increase edge count and processing time. I've been using n=3 but this will likely vary depending on the specifics of the public transit network you're looking at.

Generate inter-trip edges

Finally, we generate edges between nodes that share a trip. We link these nodes in their stop sequence order. For example, for a trip ๐ŸšŒA with stop sequence ๐ŸšX->๐ŸšY->๐ŸšZ, where ๐ŸšX and ๐ŸšZ are both transfer stops, we should have a edge (๐ŸšŒA,๐ŸšX)->(๐ŸšŒA,๐ŸšZ). (๐ŸšŒA,๐ŸšY) isn't in the graph because it isn't a transfer node.

Trip routing

Once the transfer network is ready we can leverage Dijkstra's algorithm to generate the trip routes. However, we want to accept any arbitrary start and end stops, whereas the nodes in our network only represent transfer stops. Not all stops are included. We use the following procedure to accommodate for this:

  1. Given a starting stop ๐Ÿšs and departure time ๐Ÿ•’dt, find all trips ๐ŸšŒT_s that go through ๐Ÿšs after ๐Ÿ•’dt.
  2. Given a ending stop ๐Ÿše, find all trips ๐ŸšŒT_e that go through ๐Ÿše after ๐Ÿ•’dt.
  3. If there are trips in both ๐ŸšŒT_s and ๐ŸšŒT_e, that means there are trips from start to finish without any transfers. Return those and finish. Otherwise, continue.
  4. For each potential starting trip ๐ŸšŒt_s in ๐ŸšŒT_s, find the transfer stop soonest after ๐Ÿšs in ๐ŸšŒt_s (note that this could be ๐Ÿšs itself) to be an entry node into the transfer network. We'll denote these nodes as โญ•N_s. For example, if we have trip ๐ŸšŒA with stop sequence ๐ŸšX->๐ŸšY->๐ŸšZ and ๐ŸšX is our starting stop, but not a transfer stop (meaning it's not in our transfer network), and ๐ŸšY is a transfer stop, we get the node (๐ŸšŒA, ๐ŸšY). If ๐ŸšX is a transfer stop, then we just get (๐ŸšŒA, ๐ŸšX).
  5. For each potential ending trip ๐ŸšŒt_e in ๐ŸšŒT_e, find the transfer stops closest to ๐Ÿše in ๐ŸšŒt_e (which could be ๐Ÿše itself). We'll denote these nodes as โญ•N_e. This is just like step 4 except we go in reverse. For example, if we have trip ๐ŸšŒA with the stop sequence ๐ŸšX->๐ŸšY->๐ŸšZ and ๐ŸšZ is our starting stop but not a transfer stop, and ๐ŸšY is a transfer stop, then we get the node (๐ŸšŒA, ๐ŸšY).
  6. Create a dummy start node, โญ•START, and create edges from it to each node in โญ•N_s, where the edge weight is the travel time from stop ๐Ÿšs to that node.
  7. Create a dummy end node, โญ•END, and create edges from each node in โญ•N_e to it, where the edge weight is the travel time from the node to stop ๐Ÿše.
  8. Use Dijkstra's algorithm to find the shortest weighted path from โญ•START to โญ•END. This path is our trip route.

Conclusion

On the Belo Horizonte data (630 routes with 9,428 stops) with n=3 for indirect transfer generation we get a graph of 239,667 nodes and 4,879,935 edges. I haven't yet figured out a way to further reduce this edge count.

The transfer network generation takes about 20 minutes on my ThinkPad X260. I'm not certain a direct comparison is appropriate, but this is significantly faster than the 12 hours the other implementation took. The actual route generation doesn't seem any faster or slower than the other implementation.

While the routing is fairly fast, it definitely could be faster, and is not fast enough for direct usage in PolicySpace. We won't be able to compute individual trip routes for every one of Brazil's ~209 million inhabitants, but we were never expecting to either. This trip routing feature will be used by some higher-level interface which will cache routes and batch compute more approximate routes between regions (called "transportation analysis zones" in the transit demand modeling literature) to cut down on processing time. We're still figuring out specifics.

Anyway, this is version 1 of this trip routing method -- I'd appreciate any feedback and suggestions on how to improve the approach. I need to do more testing to get a better sense of the generated routes' quality.

The code for this implementation at time of writing is available here. There are a couple names different in the code than described here, e.g. the transfer network is called a "trip network", but the algorithm itself should be the same.


ProtonMail Bridge & Mutt

ProtonMail recently released their Linux beta for Bridge, which provides IMAP/SMTP access to the service. Prior to Bridge you could only access the service through the web interface, which is sort of clunky and requires you to, among other things, rely on their search, which is limited by the fact that they can't really index your emails - because you're paying them not to read the message bodies!

ProtonMail provides instructions for setting up the Bridge with common email applications like Thunderbird, but that's about it. So here's how to set it up with NeoMutt and OfflineIMAP for fetching our emails.

(My full email setup also includes the common Mutt companions NotMuch for better searching and urlscan for viewing URLs more easily in emails, in addition to some custom scripts, such as one for viewing HTML emails in a nice popover window and one for viewing MHT/MHTML emails (which are emails that contain inline attachments). It's too much to cover here, but if you want to poke around these scripts and my full email configs (at time of writing), see my dippindots.)

Installing NeoMutt and OfflineIMAP

These instructions are for Ubuntu 16.04, but I imagine they aren't much different for other distributions (yours might even have a package you can install).

Install dependencies:

sudo apt install -y xsltproc libidn11-dev libsasl2-dev libnotmuch-dev --no-install-recommends

Then grab the latest NeoMutt release, extract, and build:

./configure --disable-doc --ssl --sasl --notmuch
make
sudo make install

# so we can just access it via `mutt`
sudo ln -s /usr/bin/neomutt /usr/bin/mutt

Then install OfflineIMAP:

sudo pip install offlineimap

Running the Bridge

The Bridge can be run from the command line with the Desktop-Bridge program. By default this opens a GUI to setup your accounts, but you can also access a console interface with Desktop-Bridge --cli.

If you aren't already logged in you need to run the login command in this interface.

Configuring OfflineIMAP

First thing to do is configure OfflineIMAP to access our ProtonMail emails.

OfflineIMAP looks for a config at ~/.offlineimaprc. My config at time of writing is:

[general]
accounts = main


[Account main]
localrepository = main-local
remoterepository = main-remote

# full refresh, in min
autorefresh = 0.2

# quick refreshs between each full refresh
quick = 10

# update notmuch index after sync
postsynchook = notmuch new


[Repository main-local]
type = Maildir
localfolders = ~/.mail

# delete remote mails that were deleted locally
sync_deletes = yes


[Repository main-remote]
type = IMAP
remoteport = 1143
remotehost = 127.0.0.1
remoteuser = <YOUR EMAIL>
remotepass = <YOUR BRIDGE-SPECIFIC PASSWORD>
keepalive = 60
holdconnectionopen = yes

# delete local mails that were deleted on the remote server
expunge = yes

# sync only these folders
folderfilter = lambda foldername: foldername in ['INBOX', 'Archive', 'Sent']

# is broken, but connecting locally to bridge so should be ok
ssl = no

Basically this sets up an account arbitrarily called main which will store emails at ~/.mail in the Maildir format. It will only sync the INBOX, Archive, and Sent folders to/from ProtonMail (the folderfilter option). Emails deleted locally will also be deleted on ProtonMail (the sync_deletes option) and emails deleted on ProtonMail will be deleted locally (the expunge option).

After OfflineIMAP fetches new email, it will run the command defined for postsynchook, which in this case is is the notmuch command for updating its search index (notmuch new).

Important Bridge-related things to note:

  • Bridge generates a Bridge-specific password for you to use, so use that here and not your actual ProtonMail password.
  • Bridge's IMAP service runs at 127.0.0.1:1143 (normally IMAP runs on port 143 or 993 for SSL)
  • Disable SSL because it was (at least when I set this up) not working with Bridge. But this seems like a non-issue because it's over a local connection anyways and the actual outgoing connection to ProtonMail is encrypted.

Then try running it using the offlineimap command.

Configuring NeoMutt

There is a lot to configure in NeoMutt, so I'll only cover what is necessary to get this setup working. If you're interested in seeing more, my NeoMutt config at time of writing is available here.

NeoMutt looks for a config at ~/.muttrc. To get it working with OfflineIMAP and to send emails with SMTP you need at least:

# "+" substitutes for `folder`
set mbox_type=Maildir
set folder=~/.mail/
set record=+Sent
set postponed=+Drafts
set trash=+Trash
set mail_check=2 # seconds

# smtp
source ~/docs/keys/mail
set smtp_url=smtp://$my_user:$my_pass@127.0.0.1:1025
set ssl_force_tls
set ssl_starttls

Where my ~/docs/keys/mail file has contents in the format:

set my_user=<YOUR EMAIL>
set my_pass=<YOUR BRIDGE-SPECIFIC PASSWORD>

Important Bridge-related notes:

  • The SMTP port is 1025 (typically it's 587)
  • See the previous note on Bridge-specific password

That should be all you need.

"Daemonizing" the Bridge

There currently is no way to daemonize the Bridge, but here's a workaround using tmux:

tmux new-session -d -s mail 'Desktop-Bridge --cli'

This just opens up a new tmux session and runs the Bridge inside of it.


Finding closest edge positions in a spatial network

I encountered an interesting challenge the other day while working on a transit demand model for the PolicySpace project (under Bernardo Furtado at the IPEA/Institute of Applied Economic Research).

We have bus data for Belo Horizonte, one of the largest cities in Brazil (and South America). Specifically, we have GTFS (General Transit Feed Specification) data with geographic coordinates of bus stops.

We also have a network of the city's roads, with data provided by OpenStreetMaps and accessed with the osmnx library. The library provides us with the geographic and UTM (Universal Transverse Mercator) projected coordinates for nodes as well as line geometries for most of the edges (edges which are just straight lines don't have geometries provided, but they can be inferred from the coordinates of their start and end nodes).

How do we meaningfully map these bus stops to our road network? The first instinct might be to associate them with their closest node, but many bus stops start somewhere along a road rather than at the start or end of one.

So we need to be able to find the closest point along a road for a given bus stop. This is trickier because whereas nodes can be treated as single points, roads potentially have winding geometries. A road which starts and ends far from a bus stop might nevertheless have a very close point to the bus stop somewhere along it. We want to accommodate these kinds of cases.

Goal: find closest point on closest edge to a bus stop's coordinates
Goal: find closest point on closest edge to a bus stop's coordinates

The first step is to find candidate edges that are close enough to the bus stop to be plausible roads for it. We have bounding boxes for each edge's geometry, so we can accomplish this search with a quadtree, using Pyqtree. A quadtree is a data structure that indexes 2D boxes and allows you to quickly find boxes which overlap a given query box. It's sort of like a kd-tree but can search boxes in addition to points.

To demonstrate this process, I'll use a dummy road network consisting of a few paths:

bbox = (-0.3, -0.3, 1.4, 1.4)
paths = [
    [(0, 0), (0.2, 0.6), (0.5, 0.9), (1, 1)],
    [(0.8, 0.2), (0.5, 0.8), (0.5, 0.9)],
    [(0.4, 0.05), (0.5, 0.1), (0.6, 0.07), (0.65, 0)],
    [(0, 1.2), (0.2, 0.9), (0.2, 0.65), (0.3, 0.4), (0.3, 0.3)],
]

Which looks like:

Dummy road network
Dummy road network

So we index all our edges' bounding boxes into this quadtree. We pad the bounding boxes by some configurable radius, since the bus stop is likely to be in the vicinity of an edge's borders.

from pyqtree import Index
from shapely import geometry

# box padding
radius = 0.1

# keep track of lines so we can
# recover them later
lines = []

# initialize the quadtree index
idx = Index(bbox)

# add edge bounding boxes to the index
for i, path in enumerate(paths):
    # create line geometry
    line = geometry.LineString(path)

    # bounding boxes, with padding
    x1, y1, x2, y2 = line.bounds
    bounds = x1-radius, y1-radius, x2+radius, y2+radius

    # add to quadtree
    idx.insert(i, bounds)

    # save the line for later use
    lines.append((line, bounds))

Here's what these bounding boxes look like for the demo network:

Padded bounding boxes for edges
Padded bounding boxes for edges

Let's say we have a bus stop at the following red point:

Bus stop point
Bus stop point

To find the closest edges using the quadtree, we treat this point as a box, adding some padding to it as well:

# query point
pt = geometry.Point(0.6, 0.4)

# query box
pt_bounds = pt.x-radius, pt.y-radius, pt.x+radius, pt.y+radius
Bus stop box
Bus stop box

Querying the quadtree is simple:

matches = idx.intersect(pt_bounds)
Matched edges (in yellow)
Matched edges (in yellow)

Now it's a matter of finding the closest edge. We're using shapely's geometry objects which have a lot of what we need built-in:

# find closest path
closest_path = min(matches, key=lambda i: lines[i][0].distance(pt))
closest_line = lines[closest_path][0]
Closest edge (in red)
Closest edge (in red)

Once we have the closest edge, we find the closest point on that edge by projecting the query point onto the edge. We don't want an absolute position, but rather how far the point is along the edge. That is, we want a value in [0,1] such that 0 is the start of the edge, 1 is the end of the edge, 0.5 is halfway along the edge, etc. shapely's normalized=True argument will take care of that for us.

p = closest_line.project(pt, normalized=True)

If we want the absolute point to, for example, plot it below, we can get iteasily:

closest_pt = closest_line.interpolate(p, normalized=True)
Closest point (the red star)
Closest point (the red star)

Now we have mappings of bus stops to positions along edges, which we can leverage when computing trip routes for our transit demand model.


Simulation & Understanding

  • 01.26.2018
  • etc

This is the written reference for a talk at the Digital Humanities + Data Journalism Symposium (the slides are here). A class based on the topics presented here is now at the New School.

The world is very complex of course and seems inexorable in its acceleration of this complexity. Problems we face expand in difficulty in that they 1) grow to impossible scales but 2) simultaneously become increasingly sensitive to the smallest detail.

In 1973 Rittel & Webber described such problems as "wicked". Their paper Dilemmas in a general theory of planning attempts to enumerate the characteristics of such problems, which include but are not limited to:

  • difficult to agree on the problem (or whether there's a problem at all)
  • there is no comprehensive perspective
  • wicked problems are interconnected
  • no way to verify or experiment solutions
  • there may be (very) delayed feedback loops
  • every wicked problem is unique
  • are nonlinear (outputs are disproportionate to the inputs)
  • cannot be reduced to its parts (i.e. emergent)
  • they are massive & intimidating

For example, consider the issue of climate change:

  • Some people don't agree that climate change in general is an issue, some people think it's happening but it isn't caused by people, and so on.
  • No individual or organization really has a complete understanding of the issue. There isn't even a single unifying perspective since it affects different communities in very different ways.
  • It's deeply entangled with many other problems, e.g. displacement of populations, economic crises, ecological destabilization, globalization, etc
  • We can't really experiment with solutions because the problem is so complex it's unlikely we'll ever be able to establish any convincing causal relation between the intervention and the outcome.
  • Any intervention may change the nature of the problem such that we'd be dealing with a completely different problem, so any learnings from the intervention might be obsolete.
  • The feedback delay between an intervention and its outcome may not be felt until years or decades later.
  • Nonlinear dynamics like tipping points
  • Global scale, many moving parts, many different interests, varying degrees of cooperation, etc...it is, as Emily Eliza Scott puts it, "multiscalar, multitemporal, multidimensional, and multidisciplinary"

I was listening to an interview with the philosopher Frithjof Bergmann who's involved in a project called New Work. In the interview he put forward a claim that every problem can be traced back to our relationship with work. I was skeptical at first but after some thought there is a plausible causal chain between jobs and climate change. Employment and "job creation" are of course major political issues. Some part of this probably involves manufacturing (though perhaps in decreasing amounts in more developed economies) which requires stoking the flames of consumption to keep demand up; this kind of production drives energy usage and pollution and waste which end up contributing to climate change.

It seems that although technology is often responsible for the exacerbation of such problems and their complexity, there should also be some means of technologically mitigating them. Not solve them outright -- that takes much more than just new tech -- but at least better equip us to do so ourselves.

I think simulation has some potential to help here.

Simulation requires that we formalize our mental models; they are a "working memory" that support larger such models, the process of designing a simulation can lead to increase understanding, at the very least identify gaps in our knowledge, and they provide a canvas for us to sketch out possible alternatives.

What simulation?

There are many different forms simulation can take. Here I'm referring to both agent-based modeling and system dynamics (i.e. causal loop diagrams) and focusing on their applications to social systems ("social simulation").

Agent-based modeling (ABM) is a method which models systems via modeling its constituent elements (e.g. people) and describing how they interact. It's often contrasted with equation-based modeling (i.e. differential equations) which is far more common but limited by assumptions hard-coded into it:

  • usually assumes homogeneous population
  • usually continuous variables
  • cannot observe local detail, generally focuses only on aggregate phenomena
  • top-down (from global perspective as opposed to individual)
Agent-based modeling
Agent-based modeling

Agent-based modeling, on the other hand, supports heterogeneity, is flexible in the variables it supports (discrete or continuous), provides views at both the local and global level, allows for learning/adaptive agents, and more.

System Dynamics
System Dynamics

System dynamics models systems by stocks (quantities that change over time) and flows (rates of change relating stocks). System dynamics is like a higher-level abstraction over agent-based modeling, in which we don't represent individuals in a population explicitly but instead as aggregates.

An especially appealing aspect of both ABMs and system dynamics that they are much more intuitive than differential equations (I feel bad leveraging our education system's inability to make people comfortable with math, but oh well), so they are more immediately accessible to a wider audience.

Differential equations
Differential equations

They are also exceptionally flexible in what they can represent, ranging from ant colonies to forest fires to urban segregation to religious experiences.

Examples

Language Evolution Simulation (Fatih Erikli)
Language Evolution Simulation (Fatih Erikli)

This simulation shows how a language could evolve over time by exchanging vocabulary with random mutations.

Differentiation without Distancing. Explaining Bi-Polarization of Opinions without Negative Influence (Michael Mรคs, Andreas Flache)
Differentiation without Distancing. Explaining Bi-Polarization of Opinions without Negative Influence (Michael Mรคs, Andreas Flache)

This study looks at how opinions may become polarized without requiring negative influence ("individualsโ€™ striving to amplify differences to disliked others"). In the image you see everyone starting from the same intermediate position and eventually becoming bi-polarized.

Learning To Be Thoughtless: Social Norms and Individual Computation (Joshua M. Epstein)
Learning To Be Thoughtless: Social Norms and Individual Computation (Joshua M. Epstein)

This paper models how individuals not only learn which social norms to adopt but also learn how much to think about adopting a social norm (e.g. if a social norm is prevalent enough we may adopt it without consciously deciding to). On the left, the blue and yellow colors indicate a binary norm, and the image depicts, from top to bottom, how the adoption of those norms ebb over time. There are always little pockets of resistance (e.g. yellow amongst majority blue) that eventually bloom into the new majority and eventually fall to the same fate.

From Private Attitude to Public Opinion: A Dynamic Theory of Social Impact (Andrzej Nowak, Jacek Szamrej, Bibb Latanรฉ)
From Private Attitude to Public Opinion: A Dynamic Theory of Social Impact (Andrzej Nowak, Jacek Szamrej, Bibb Latanรฉ)

This model describes how opinions shift according to social influence. I really like that this model was printed out like this.

A Distributed Platform for Global-Scale Agent-Based Models of Disease Transmission (Jon Parker, Joshua M. Epstein)
A Distributed Platform for Global-Scale Agent-Based Models of Disease Transmission (Jon Parker, Joshua M. Epstein)

This is a massive epidemiology model at a self-described "global-scale" of 6 billion agents, running in reasonable time. This particular study models the H1N1 (swine flu) virus.

Simulados
Simulados

The Simulados project models hunter-gatherer groups in India from the years 10000BC to 2000BC. It's part of a broader initiative, Simulpast, which "aims to develop an...interdisciplinary methodological framework to model and simulate ancient societies".

Cities: Skylines (Paradox Interactive)
Cities: Skylines (Paradox Interactive)

Paradox Interactive's Cities: Skylines (similar to SimCity) models their citizen's activities as an agent-based model.

MONIAC (Monetary National Income Analogue Computer)
MONIAC (Monetary National Income Analogue Computer)

A non-digital example, MONIAC is a hydraulic system dynamics model of the UK economy.

System dynamics applied to religious experiences
System dynamics applied to religious experiences

Arlen Wolpert was an engineer and a scholar of religion who used system dynamics to describe a powerful religious experience he had. I like this example because it demonstrates the method's breadth of applicability, and it's really curious to see how he framed the different components of the experience.

Agent-based modeling in more detail

Most of my interest is in agent-based modeling rather than system dynamics, so I'll go into a little more depth here by walking through Schelling's model of segregation. This model was developed to demonstrate that even when individuals have "tolerant" preferences about who they live near, neighborhoods may in aggregate still end up segregated.

Every agent-based model has two core components: the agents and their environment.

In Schelling's model, agents are typically modeled as households, placed in a 2D grid environment. This is similar to cellular automata, like the Game of Life; CAs can be thought of as a subset of ABMs.

Each household has a "type" (typically representing race) and a tolerance threshold $t$. This threshold defines the minimum amount (percent) of similar neighbors required for the household to be "satisfied". An unsatisfied household will move to a random unoccupied spot in the grid.

Schelling basics
Schelling basics

Here we consider Von Neumann neighbors; that is, the spaces to the north, east, west, and south of a cell. This is in contrast to a Moore neighborhood, which includes all eight surrounding cells.

Neighborhoods
Neighborhoods

Here's how an Schelling agent would be defined in System Designer (still under heavy development! The API will change!), an agent-based modeling framework Fei Liu and I are currently developing:

import syd
import numpy as np

class SchellingAgent(syd.Agent):
    state_vars = ['type', 'position', 'satisfied', 'threshold']

    async def decide(self):
        neighbors = await self.world.neighbors(self.state.position)
        same = np.where(neighbors == self.state.type)[0]
        satisfied = same.size/neighbors.size >= self.state.threshold
        self.submit_var_update('satisfied', satisfied)
        if not satisfied:
            await self.world.queue_random_move(self.state.position, self.state.type, self.addr)

And here's how the Schelling environment (world) would be defined:

import random

class SchellingWorld(syd.world.GridWorld):
    state_vars = ['grid', 'vacancies']

    async def decide(self):
        self.submit_update(self.update_vacancies)

    @syd.expose
    async def queue_random_move(self, position, agent_type, agent_addr):
        if self.state.vacancies:
            new_pos = self.state.vacancies.pop(random.randrange(len(self.state.vacancies)))
            self.submit_update(self.move_position, position, new_pos, agent_type)
            agent_proxy = await self.container.connect(agent_addr)
            await agent_proxy.submit_var_update('position', new_pos)

    def update_vacancies(self, state):
        state.vacancies = list(self.vacancies(empty_val=0))
        return state

Then, to run the simulation:

from itertools import product

n_types = 2
n_agents = 50
width = 10
height = 10
grid = np.zeros((width, height))
positions = list(product(range(width), range(height)))

# value of 0 is reserved for empty positions
types = [i+1 for i in range(n_types)]

sim = syd.Simulation(node)
world, world_addr = sim.spawn(SchellingWorld, state={'grid': grid, 'vacancies': []})

for _ in range(n_agents):
    position = positions.pop(0)
    type = random.choice(types)
    agent, addr = sim.spawn(SchellingAgent, state={
        'type': type,
        'position': position,
        'satisfied': 0.,
        'threshold': threshold
    }, world_addr=world_addr)
    syd.run(world.set_position(type, position))

    for report in sim.irun(n_steps, {
        'n_satisfied': (lambda ss: sum(s.satisfied for s in ss if hasattr(s, 'satisfied')), 1)
    }):
        print('mean satisfied:', report['n_satisfied']/n_agents)
Schelling's model of segregation
Schelling's model of segregation

One key question when developing an ABM is: what constitutes an agent? Is it an individual, a family, a firm, a city, a nation, a cell, a grain of sand, etc? That is, what scale is relevant for the simulation? Of course, this depends on the exact problem at hand, but one idea which is particularly interesting is multiscale simulations.

Level-of-Detail in video games
Level-of-Detail in video games

In video games there is this notion of "level-of-detail" (LOD). When you are very close up to an object in a game (say, a rock) the engine loads a very high-resolution texture or more complex mesh so you can see all its detail. If however you're looking at the rock from far away, you won't be able to see the fine details and so it would be a waste to load such a high-resolution texture. Instead, a low-resolution texture or lower-poly mesh can be loaded and you won't be able to tell the difference.

Maybe the same idea can be applied to agent-based modeling. If you are "zoomed out" you don't see the actions of individuals but instead, for example, cities. It's not as straightforward as it sounds but it has a lot of appeal.

ABMs and Machine Learning

How does machine learning factor into agent-based models? Many agent-based models are fairly simple, relying on hand-crafted rules, but they can get very sophisticated too.

For example, in our project Humans of Simulated New York, Fei and I wanted to generate "plausible" simulated citizens. To do so we used ACS PUMS data (individual-level Census data) to learn a Bayes net (a generative model) which would capture correlations present in the data (this generation code is available on GitHub).

For example we could generate a citizen "from scratch":

>>> from people import generate
>>> year = 2005
>>> generate(year)
{
    'age': 36,
    'education': <Education.grade_12: 6>,
    'employed': <Employed.non_labor: 3>,
    'wage_income': 3236,
    'wage_income_bracket': '(1000, 5000]',
    'industry': 'Independent artists, performing arts, spectator sports, and related industries',
    'industry_code': 8560,
    'neighborhood': 'Greenwich Village',
    'occupation': 'Designer',
    'occupation_code': 2630,
    'puma': 3810,
    'race': <Race.white: 1>,
    'rent': 1155.6864868468731,
    'sex': <Sex.female: 2>,
    'year': 2005
}

Or specify some value, e.g. generate me a person from a particular neighborhood. It's not perfect, but it worked well enough for our purposes.

Similarly, we used a logistic regression model trained to predict the probability of two people being confidants (from Social Distance in the United States: Sex, Race, Religion, Age, and Education Homophily among Confidants, 1985 to 2004, Jeffrey A. Smith, Miller McPherson, Lynn Smith-Lovin. University of Nebraska - Lincoln. 2014), using that to bootstrap the simulation's social network.

HOSNY also included businesses which produced and sold goods (including consumer good firms, which produced food, capital equipment firms, and raw material firms). They needed to decide how much of a good to produce and what to price it at. It's quite difficult to come up with a set of rules that will work well here, so we implemented them with Q-learning (as described in "An agent-based model of a minimal economy, a basic reinforcement learning algorithm (reinforcement learning algorithms are the class of techniques used by AlphaGo, for instance).

Similarly, we implemented the government as a reinforcement learning agent, using Q-learning to decide on tax rates.

These are just a few examples of where the fields of simulation and machine learning overlap.

A systems language

In The Image of the City, urban planner Kevin Lynch interviews people in multiple cities to understand how they form "mental maps" of their cities.

We rely on similar mental maps when navigating non-corporeal landscapes. In Postmodernism Fredric Jameson references The Image of the City when calling for improved versions of this "cognitive mapping". As he describes it:

a situational representation on the part of the individual subject to that vaster and properly unrepresentable totality which is the ensemble of society's structures as a whole

Jeff Kinkle quotes Jameson's discussion of alienation and mobility in particular:

Lynch taught us that the alienated city is above all a space in which people are unable to map (in their minds) either their own positions or the urban totality in which they find themselves. [โ€ฆ] Disalienation in the traditional city, then, involves the practical reconquest of a sense of place and the construction or reconstruction of an articulated ensemble which can be retained in memory, and which the individual subject can map and remap along the moments of mobile, alternative trajectories.

Kinkle further notes:

an inability to cognitively map the mechanisms and contours of the world system is as debilitating politically as being unable to mentally map a city would be for a city dweller.

Can we, again quoting Kinkle quoting Jameson, develop a way of thinking about systems "so vast that [they] cannot be encompassed by the natural and historically developed categories of perception with which human beings normally orient themselves"? Is there any way to better represent these complex systems in which we are submerged, along with their incredibly nuanced causal chains, in a way that makes them more manageable and navigable?

How do we do so without relying on the crutch of conspiracy theories, inappropriately reducing the complexity of a situation in order to make it more comprehensible?

For cities we now have Google Maps. What about for these social systems?

This seemingly intractable problem has sometimes been called the "crisis of representation" or "representational breakdown". Speaking of climate change, but equally applicable to any similarly overwhelming problem:

What kinds of representation (visual and otherwise) are adequate to the task of conveying climate change, and perhaps most importantly, to stemming dysphoric paralysis while triggering critical thinking and action? (Archives of the Present-Future: On Climate Change and Representational Breakdown, Emily Eliza Scott)

There are many different ways of representing something like climate change. There isn't really a right one; they all have different effects.

Maldives Underwater Cabinet Meeting protest
Maldives Underwater Cabinet Meeting protest

For example: depicted here is a protest in the Maldives (which is at a very high risk of being submerged in the near future) where President Nasheed and his cabinet sent an SOS message to the UN climate change summit from underwater.

But what if we want to better comprehend the "total" system, with its interconnections, insofar as it even can be represented?

The Network of Global Corporate Control (Stefania Vitali, James B. Glattfelder, Stefano Battiston)
The Network of Global Corporate Control (Stefania Vitali, James B. Glattfelder, Stefano Battiston)

When it comes to systems the network is perhaps the most common type of representation. Networks are a fantastic abstract form but perhaps ineffective in communicating a system's less technical aspects. It is capable of describing the full system (in terms of its relational structure) but even this may serve only to intimidate. Such intimidation may be the only affective effect of such a representation, failing to depict the human experiences that emerge from and compel or resist the system.

For example, Bureau d'Etudes' An Atlas of Agendas is a meticulously researched mapping of organizations throughout the world, so detailed that a magnifying glass accompanies the book (they were originally produced at a larger scale on walls). It is undeniably impressive but induces vertigo and helplessness in its unmanageable intricacy.

_An Atlas of Agendas_
An Atlas of Agendas

This kind of network mapping also doesn't capture the dynamism of such a system.

In contrast to network mapping, Cartographies of the Absolute (the title is a direct reference to the aforementioned Jameson book), Jeff Kinkle and Alberto Toscano examine how narrative fiction provides a more experiential representation, i.e. an aesthetics, discussing for example The Wire and cinema from the peak of New York City's "planned shrinkage" (such as Wolfen). Kinkle describes the Cartographies of the Absolute project as such:

The project is an investigation into various attempts in the visuals arts to cognitively map the contours of the current world system and its influence on various local settings...focus[ing] on the techniques artists, filmmakers, and cartographers use to portray global forces in all their complexity without being merely didactic or reverting to antiquated aesthetic models.

For example, the chapter on The Wire, "Baltimore as World and Representation":

[The Wire] address[es] the drug trade, de-industrialization, city hall, the school system and the media...mapped both vertically (making internal hierarchies explicit) and horizontally (tracking their entanglements and conflicts with other 'worlds' spread throughout the city...we are...able to see how each world affects the ones around it...

This type of representation is more visceral and emotional but may obscure the totality of the underlying system (although The Wire seems to do a good job).

Is there some kind of representational "language" that falls in between? In Iain M. Bank's Culture novels he describes a language called "Marain" which "appeal[s] to poets, pedants, engineers and programmers alike". Is there an equivalent here, one that can similarly bridge the technical and the emotional representations, allowing the expressiveness of both?

The Culture's Marain
The Culture's Marain

In Ted Chiang's The Story of Your Life (which is being made into a movie now), a researcher studies an alien language which has two components - spoken (Heptapod A) and graphic (Heptapod B). The aliens tend to prefer the graphic one because the spoken language is limited by the arrow of time - it goes in one way and you have to "wait" to hear all or most of the sentence to grasp the meaning. With the graphic language, which I picture as large mandala-like ideograms, the whole sentence is consumed at once, there in front of you, which, for these aliens at least, lead to an instant and more total understanding of what was being communicated. Is there an analog of that for us?

Heptapod B as depicted in _Arrival_
Heptapod B as depicted in Arrival
Heptapod B more as I imagined it (depicted: Bismillah)
Heptapod B more as I imagined it (depicted: Bismillah)
Heptapod B more as I imagined it (depicted: a mandala)
Heptapod B more as I imagined it (depicted: a mandala)

In Thinking in Systems, Donella H. Meadows makes a similar observation:

there is a problem in discussing systems only with words. Words and sentences must, by necessity, come only one at a time in linear, logical order. Systems happen all at once.

... Pictures work for this language better than words, because you can see all the parts of a picture at once.

The possible impact of such a language in affecting our way of thinking can be seen in the effect of transitioning from Roman numerals to Hindu-Arabic numerals. Wilensky & Papert refer to these numeral systems as an example "representational infrastructure", calling this shift a "restructuration" which ultimately led to arithmetic being accessible to essentially everyone. Roman numerals were not amenable to - they did not afford, to use a design term - certain mathematical operations that are now second-nature to many; with Roman numerals only a specially-trained group of people could do such arithmetic. Wilensky is the creator of NetLogo, a very popular framework for agent-based modeling, so he seems to be positioning ABMs as a restructuration.

So what kind of language - what kind of representational infrastructure - is needed for everyone to be comfortable with complex systems?

Social simulation itself may not be this language, but it seems inevitable that it will at least be the engine for it. Perhaps we can build richer experiences on top of this engine.

A canvas for alternatives

Simulation can build an appreciation of the arbitrariness of the present, insofar as things could have played out different and still can play out differently ("another world is possible").

"Another world is possible"
"Another world is possible"

So many terrible systems and practices are maintained under the pretence of being "natural" (e.g. the infuriating "human nature" argument), so there we often see rhetoric justifying such arrangements along those lines; they are framed as spontaneous and organically-formed. They usually aren't, and even if they are, that's not a very convincing justification for their continuation.

This speculative aspect of simulation is really appealing; it carves out this space for experimentation and imagining utopias.

Humans of Simulated New York
Humans of Simulated New York

Fei Liu and I approached our project Humans of Simulated New York in this way. HOSNY was implemented as a simple economic simulation primarily based on New York City Census data, but we allowed people to play with the parameters of the world along three axes: food/agriculture, health, and technology/labor and see how the lives of citizens change in each alternate world.

HOSNY world specification
HOSNY world specification

There is a parallel here to cartography - in the late 1960's and early 1970's The Detroit Geographical Expedition and Institute (DGEI) focused on producing "oughtness maps": "maps of how things are and maps of how things ought to be." (The Detroit Geographic Expedition and Institute: A Case Study in Civic Mapping, Catherine D'Ignazio). William Bunge, one of the co-founders of the DGEI (the other was Gwendolyn Warren), noted (probably referencing Marx):

Afterall, it is not the function of geographers to merely map the earth, but to change it.

I feel a similar sentiment can be said about simulation. Perhaps we can see the emergence of simulation equivalents of the practices of "countermapping" and "radical cartography".

Detroit money transfers (Fitzgerald: Geography of a Revolution, William Bunge)
Detroit money transfers (Fitzgerald: Geography of a Revolution, William Bunge)
Detroit Recommended Redistricting to place black children under "sympathetic authority"
Detroit Recommended Redistricting to place black children under "sympathetic authority"

Exploring policy-space

This kind of systems mapping and modeling has more "practical" applications. For example, identifying points of influence/leverage points within a network.

One area of interest is in public policy modeling. The way policy is handled now seems totally nonsensical, and of course there is more than just ignorance about consequences to blame (i.e. politics), but I wonder if this sort of modeling wouldn't have at least some positive impact.

How to defeat ISIS
How to defeat ISIS
The Cycle of International Stupidity
The Cycle of International Stupidity

A comprehensive textbook on the topic, Modeling Complex Systems for Public Policies, was published last year so it seems like a fairly active area of research. In the text researchers discuss modeling transit systems, education systems, economies, cities,

_Modeling Complex Systems for Public Policies_
Modeling Complex Systems for Public Policies

One active and ambitious initiative in this area is the Eurace@Unibi model. It's a joint venture involving multiple European research institutes and seeks "to provide a micro-founded macroeconomic model that can be used as a unified framework for policy analysis in different economic policy areas and for the examination of generic macroeconomic research questions." (The Eurace@Unibi Model: An Agent-Based Macroeconomic Model for Economic Policy Analysis) The goal is to develop an economic model that has more representative power than existing methods (i.e. dynamic stochastic general equilibrium, or DSGE models, which, as the name suggests, are focused on equilibriums) and so would be a better tool for determining economic policy. I don't have enough experience with the model or economics itself to really comment on its relative effectiveness, but it's interesting nonetheless.

Eurace@Unibi
Eurace@Unibi

In urban planning a similar initiative exists, UrbanSim, an "open source simulation platform for supporting planning and analysis of urban development, incorporating the interactions between land use, transportation, the economy, and the environment."

UrbanSim
UrbanSim

There is an important distinction that needs to be brought up here: speculation vs prediction. Such an application of social simulation is not about predicting the outcome of a policy but rather about understanding what the possibilities are.

I try to mention this point a lot because social simulation is often misconstrued as something like Asimov's "psychohistory", which is described as a means of predicting the trajectories of civilizations.

Bret Victor, in What can a technologist do about climate change?, puts it this way:

Modeling leads naturally from the particular to the general. Instead of seeing an individual proposal as โ€œright or wrongโ€, โ€œbad or goodโ€, people can see it as one point in a large space of possibilities. By exploring the model, they come to understand the landscape of that space, and are in a position to invent better ideas for all the proposals to come. Model-driven material can serve as a kind of enhanced imagination.

Scott E. Page makes a similar caveat in the preface to Modeling Complex Systems for Public Policies:

Complex systems do not represent a silver bullet, but another arrow in the policy maker's quiver. More accurately, all of these tools put together can be thought of as multiple imperfect arrows that provide insight into what is likely to happen, what could happen, and how what happens might spill into other domains.

That is, simulation is more about counterfactuals (what-ifs), laying out the possibility space and shining a light on more of it than we would without such tools. It's not about predicting anything, but about exploring and speculating and moving towards understanding.

In any case, this application of simulation induces anxiety...there are too many examples of technology amplifying the power of those who already have too much of it. It's a common topic in science fiction: in the miniseries World on a Wire (which shares the source material behind The Thirteenth Floor but is quite a different experience), the IKZ (Institute for Cybernetics and Future Science) is pressured to use their simulated world to predict steel prices for the steel industry.

_World on a Wire_
World on a Wire

This furthers the urgency of popularizing this way of thinking. As we're seeing with the proliferation of machine learning, such technological vectors of control are especially potent when the public don't have opportunities to learn how they work.

A means for discourse

One side effect of translating mental models into simulation code is that you generally need to render your assumptions explicit. One assumptions are made unambiguous in code, it is easier to point to them, discuss them, and perhaps modify them. You can fork the model and assert your own perspective.

This becomes clear when you look at games which rely on simulation, like SimCity. As Ava Kofman points out in Les Simerables:

To succeed even within the gameโ€™s fairly broad definition of success (building a habitable city), you must enact certain government policies. An increase in the number of police stations, for instance, always correlates to a decrease in criminal activity; the gameโ€™s code directly relates crime to land value, population density, and police stations. Adding police stations isnโ€™t optional, itโ€™s the law.

SimCity 5 design document
SimCity 5 design document

Chris Franklin (Errant Signal) similarly notes many problematic assumptions in Civilization 5, such as framing only certain societies as "civilizations" (the rest are "barbarians", which are literally under the same banner as wild animals), and further asserting that the only valid form of social organization and actor in history is the nation-state. As such it precludes the possibility of alternative forms of society; the game simulation leaves no space for such things.

These two instances could be framed as examples of what Ian Bogost calls "procedural rhetoric", defined as:

an argument made by means of a computer model. A procedural rhetoric makes a claim about how something works by modeling its processes in the process-native environment of the computer rather than using description (writing) or depiction (images). (Persuasive Games: The Proceduralist Style, Ian Bogost)

Another example includes molleindustria's Nova Alea, a game about speculative real estate investment and gentrification in which you pump money into a city block to (if all goes well) see it grow and later reap the profits.

molleindustria's Nova Alea
molleindustria's Nova Alea

I'm also developing a video game, The Founder: A Dystopian Business Simulator, which argues that the logic that compels Silicon Valley is inherently destructive and destabilizing. In it you found and manage a startup for as long as you can satisfy the required growth targets. Maintaining growth requires hiring cheap labor, replacing it where possible, commingling with the government, pacifying employees, and more.

The Founder
The Founder

With simulation the mechanics of a system as you see it must be laid bare. They become components which others can add to or take from or rearrange and demonstrate their own perspective. This is no doubt utopian of me to say, but I would love to see a culture of argumentation via simulation!

Exploration & education

Simulations can be used to argue, but they can also be used for education, falling under the rubric of "explorable explanations". That is, when imbued with interactivity, simulations can essentially function as powerful learning tools where the process of exploration is similar to or indistinguishable from play.

Nicky Case is doing a lot of amazing work here. Their projects are great at communicating the pedagogical appeal of simulation. Parable of the Polygons (developed with Vi Hart) is a wonderful presentation of Schelling's segregation model. Their emoji simulation prototype is also awesome. (I highly recommend their talk How to Simulate the Universe in 134 Easy Steps.

Parable of the Polygons
Parable of the Polygons
emoji simulator
emoji simulator

Nicky also maintains a collection of explorable explanations, framing them as such:

What if a book didn't just give you old facts, but gave you the tools to discover those ideas for yourself, and invent new ideas? What if, while reading a blog post, you could insert your own knowledge, challenge the author's assumptions, and build things the author never even thought of... all inside the blog post itself?

What if, in a world where we're asked to constantly consume knowledge, we construct knowledge?

Working off a similar strand of thought is Buckminster Fuller's proposed "World Game":

In the 1960's Buckminster Fuller proposed a โ€œgreat logistics gameโ€ and โ€œworld peace gameโ€ (later shortened to simply, the โ€œWorld Gameโ€) that was intended to be a tool that would facilitate a comprehensive, anticipatory, design science approach to the problems of the world. The use of โ€œworldโ€ in the title obviously refers to Fuller's global perspective and his contention that we now need a systems approach that deals with the world as a whole, and not a piece meal approach that tackles our problems in what he called a โ€œlocal focus hocus pocusโ€ manner. (Buckminster Fuller Institute)

Fuller's World Game
Fuller's World Game

I loved this idea of a shared game through which people learn to think on a global scale, about the interrelatedness of all things, imbuing an acknowledgement of our connectedness as a species from a young age.

It reminds me of the fictional game Azad, from The Player of Games, which is played annually by the Empire of Azad and literally dictates how the civilization is run and what it values as a culture. The game has enough depth and complexity that a player can reflect their entire philosophy and perspective about the world through how they play. It's a beautiful capacity for a game to aspire to.

Azad
Azad

As far as I know Fuller's World Game never materialized, but a game which seems to trace its intellectual lineage to this proposal is Strange Loop Games' ECO, where players must collaborate in a simulated ecosystem to build a lasting society, involving both an player-run economy and a government, and culminating in cooperating to prevent an extinction event (a meteor impact).

Strange Loop Games' ECO
Strange Loop Games' ECO

Looking forward into the future, the speculative paper Optimistsโ€™ Creed: Brave New Cyberlearning, Evolving Utopias (Circa 2041) (Winslow Burleson & Armanda Lewis) postulates an educational method called "cyberlearning" which integrates VR, AI, and simulation:

Cyberlearning provides us (1) access to information and (2) the capacity to experience this informationโ€™s implications in diverse and visceral ways. It helps us understand, communicate, and engage productively with multiple perspectives, promoting inclusivity, collaborative decision-making, domain and transdisciplinary expertise, self actualization, creativity, and innovation (Burleson 2005) that has transformative societal impact.

Cyberlearning
Cyberlearning

This is the holy grail of simulation to me - such an educational experience could have an incredible effect.

MIT's CityScope project is a step in this direction, providing an interactive "Tactile Matrix" - a city in the form of Legos - that is connected to an urban simulation.

CityScope's Tactile Matrix (MIT)
CityScope's Tactile Matrix (MIT)

Experience generation

Last but not least: experience generation. Earlier I asked how we imbue simulation with the narrative richness other media provides. That is, how do we more accurately communicate the experiences that a simulation might (ostensibly) represent?

Humans of Simulated New York tries to tackle this question. We were initially curious about "breathing life" into data. Data about human phenomenon are meant to translate experiences into numbers which may reveal something about the underlying structure of these phenomenon. Perhaps if we take this structure, parameterized with these numbers, we can use simulation to generate some experience which better approximates the experience that initially generated the data.

Many "experience generators" already exist. Video games are probably the most ubiquitous example. Games like Kentucky Route Zero and Gone Home are powerful ways of telling the stories of individuals.

Kentucky Route Zero
Kentucky Route Zero
Gone Home
Gone Home

These particular examples at least are highly-scripted narratives; ultimately they are very guided and linear.

Some games go beyond this by not writing a particular story but instead defining the world in which many stories can happen. Games of this category include Cities: Skylines, Stellaris (similar to a galactic Civilization game), and famously Dwarf Fortress. These games describe rules for how a world (or universe) works and provides players the space to create their own stories.

Dwarf Fortress
Dwarf Fortress
Stellaris
Stellaris

These games, however, are not derived from real-world data and, perhaps as a result of this, lack the same narrative power that games like Gone Home have. It seems like if we can create game from a simulation meant to approximate our society (at least the aspects relevant to the stories we wish to tell) we can create a deeply engaging way to learn about each other. Sort of like Fuller's World Game, but one that doesn't privilege the global perspective and equally appreciates the individual one.

We certainly did not achieve this with HOSNY but this is part of what motivated the project. We were interested in creating a simulation that modeled a typical day in the life of a New Yorker of a particular demographic, as described by Census data (in particular, New York City American Community Survey data spanning 2005-2014). The following sketch gives an idea:

Early HOSNY form
Early HOSNY form

The simulation agents ("simulants") had very simple behaviors. They needed to buy food for them and their family and, unless they were independently wealthy or a business owner, had to find employment to get the money to do so. They also had to pay rent, could get sick, could visit the doctor if they could afford it, and could start a business if they could afford it. They also varied a bit in personality - this part was totally separate from the dataset - which influenced their decision making.

HOSNY simulant design
HOSNY simulant design

A social simulation needs a social network so we used a model from Social Distance in the United States: Sex, Race, Religion, Age, and Education Homophily among Confidants, 1985 to 2004 (Jeffrey A. Smith, Miller McPherson, Lynn Smith-Lovin. University of Nebraska - Lincoln. 2014) which looked at what factors correlated with two people being confidants. Given two simulants, this model output a probability that they would be friends.

HOSNY social network formation
HOSNY social network formation

The full simulation design document is available here.

The end result was a participatory economic simulation which players, after joining via their phone, are assigned a random simulant. It's their duty to ensure the well-being of their simulant by voting on and proposing legislation they believe will help improve their life.

HOSNY player screen
HOSNY player screen

I don't think we quite achieved generating a compelling narrative with this particular project, but I do think the general methods used will eventually support a successful one.

System Designer (SyD)

Fei and I are working on a framework, System Designer (SyD for short), which tries to tie together and realize these ideas I've discussed here. The goal is to create an accessible tool for constructing, running, and playing with social simulations and develop an accompanying educational program.

Early sketch of System Designer
Early sketch of System Designer

Our current blurb for describing it:

An open-source simulation toolkit and conceptual framework to make complex systems thinking (how did we get here/where are we now?) and the simulation of alternative worlds (where can we go?) more accessible to designers, activists, urban planners, educators, artists....

The framework is still in its early stages, but the plan is to include:

  • an engine for running simulations (Python)
    • multi-node support
    • extensibility
    • common data format for sharing/forking models
  • a protocol for communicating with the engine
    • to build arbitrary interfaces to build & tweak simulations
    • to build arbitrary visualizations on top
  • a GUI editor for building/tweaking simulations
  • workshops to teach the method & tool
Game of Life built with SyD
Game of Life built with SyD

Wrap up and come down

Clearly I'm very excited about the possibilities here, but I also want to add as a caveat: I'm not advocating this as some monolithic silver bullet (even though it might sound that way). I think simulation (in particular, agent-based modeling and system dynamics) is a very interesting methodology that has an inherent appeal and provides powerful new ways of looking at the world. But I also have reservations and uncertainties which I would be happy to discuss afterwards. There is one main concern I want to address, and it basically amounts to: "how well can we actually model people?"

This is a difficult question that has many different phrasings and different answers for some and no answers for others.

As a general and perhaps unsatisfying answer, I don't, at my current level of understanding of the field, think we can ever model people "perfectly" or even at an extremely high-fidelity (perhaps due to a combination of limits of computation and of what we can understand about human behavior generally), but I do think we can model people at a convincing and useful level. To quote George Box (this quote had to be in here somewhere): "all models are wrong, but some are useful".

The promise/spectacle of big data has revived a notion of "social physics", the idea that we can describe immutable laws which govern human behavior. In fact, Bruno Latour seems to be arguing for the abandonment of methods like agent-based modeling in favor of big-data-driven social science. Most of us are familiar with how flawed the idea of "big data == truth" is (Nathan Jurgenson goes into more detail about the shortcomings here), but to put it succinctly: processes of data collection and analysis are both subject to bias, and the "infallible big-data" rhetoric completely blinds practitioners to it.

In 2014, Joshua Epstein published Agent_Zero: Toward Neurocognitive Foundations for Generative Social Science. It is an ambitious attempt at defining a "first principles" agent that models what he describes as the three core components to human behavior: the cognitive (rational), the affective (emotional), and the social. The book is fascinating and I think there is a lot to be learned from it, but it also needs to be considered with great care because it too seems subjectable to a biased understanding of what constitutes human behavior.

Of course, there is no methodology that is immune to potential bias, and as Jurgenson notes in View from Nowhere, the main safeguard is training practitioners to recognize and mitigate such bias as much as possible. The same caveat needs to be applied to the methods of social simulation, and even so, I still believe them to hold a great deal of promise that needs to be further explored.


occhiolism
n. the awareness of the smallness of your perspective, by which you couldn't possibly draw any meaningful conclusions at all, about the world or the past or the complexities of culture, because although your life is an epic and unrepeatable anecdote, it still only has a sample size of one, and may end up being the control for a much wilder experiment happening in the next room.

from the dictionary of obscure sorrows