06 Feb 2013

Conway’s Game of Life

Game of Life

First published in 1970, Conway’s Game of Life is the prototypical example of cellular automata.  What I find fascinating about this simulation of artificial “life” is the incredible ratio of emergent behaviors to governing rules.  While there are many variations, the original game has only four basic rules, yet these can give rise to machines that translate, reproduce, oscillate, and count, among many other behaviors.  There are plenty of good simulators, both online and offline, though I haven’t played with any of them extensively enough to have a recommendation. Golly seems to have very high praise. Over the past four decades, many initial conditions have been identified which give rise to desired behaviors.  I’m interested to learn if there is a way to essentially run the game in reverse from an end condition or behavior to its simplest origin.  This is difficult, as the game is only deterministic in the forward direction, given that cells and structures can cancel out and leave no trace.


Gaussian Processes (the ML/statistical technique)

Unfortunately I haven’t found any great images that make sense on their own, so instead I’ll recommend this gentle introduction to the topic.

Gaussian processes are a set of statistical techniques from machine learning and robotics that can be used in a variety of ways to make predictions about missing or sparse data.   Rather than explain the details of how this works in a short space, I will try to describe what it can do for us.  If I told you the barometric pressure outside my house, and you knew the pressure outside of yours, we might guess that the pressure at a friend’s house in between ours would be about the average of our two numbers, assuming the distance between houses isn’t all that great and there aren’t any massive environmental discrepancies.  Expanding this, if we had a tight enough mesh of sensors across a much larger area, we can predict the empty spaces fairly well.  We don’t usually have the luxury of uniform information density, though, so this method breaks down easily.  Gaussian processes approach problems like these from a different direction, where the “distances” that we care about actually exist in a feature space containing not just latitude and longitude, but other values that describe that point in physical space.  One particularly notable application is the prediction of soil quality in countries like Honduras where there are areas where direct measurements simply cannot be made.  We can still get indirect information about these areas from satellite images and geographical data, which can tell us things like distance from rivers, altitude, foliage density, etc.  If we have soil quality data in other far away locations with similar characteristics, we can use gaussian processes to make predictions even in areas where we’ve never been.  See this paper for more details.

…So why am I suggesting this is a generative process?  It’s a bit of a stretch, but I would argue that this is a generative method because it can be used with real, known data to create predictions anywhere in the world.  If you still aren’t convinced, consider this:  If I mined the Lord of the Rings books for as many geographical descriptions as I could find, I could use data from the real world to give you my prediction about what plants would most likely grow in the Shire and the pH of the soil in Mordor, along with a numerical confidence for each.  (Or maybe I shouldn’t write blog posts this late at night.)


Minecraft (and other procedurally-generated worlds)


I love Minecraft.  Minecraft is art.  My apologies for yet another Minecraft-related Looking Outwards.  Part of what attracts me to this game the most is that no two worlds are even remotely similar.  The development team has done an amazing job at procedurally generating voxellated terrain, and in recent years terrain generation has expanded to include diverse biomes including deserts, swamps, and tundra (complete with reproducing plants and fauna).  When a player finds a village in the middle of the plains, the houses and structures there are unique to that game and likely will not be generated ever again.  The world is also boundless.  As the player walks in a certain direction, the world continues to generate far beyond the player’s field of view.  (It used to be that walking in a huge circle would result in bizarre discontinuities in the landscape when new land merged with old, but this has been fixed recently.)  In my opinion, the procedural nature of the game is what provides the sense of discovery rarely found in other games.  It can be found to some degree in huge worlds like those in the Elder Scrolls series, but these still fail to feel like true discovery, because the player knows that many others have found the exact same hard-coded locations.  In Minecraft, that scary cave you found is yours and yours alone.