Tuesday, January 14, 2014

Functors are computations

Review: Functors are containers


Bartosz Milewski wrote a controversial (at the time of writing, 8 votes up and 8 votes down) post about Functors. The community really doesn't seem to like simplistic analogies such as "Functors are containers", "Monads are computation", or "Comonads are neighbourhoods".

Personally, I find those analogies very useful, as long as you know exactly which parts of the analogy apply. I think what the community doesn't like about analogies such as "Functors are containers" is that they are misleading. And if you only say that, "Functors are containers", then it is indeed misleading. You think you know what a container is (a plastic box in which I can put food?), and now you think you also know what a Functor is (a crazy math name for a plastic container?), but of course that's not what the analogy is trying to say. Stating the analogy is only the first step; we give your intuition a place to start, something familiar, and now we need to explain exactly how much Functors are like containers, and in which ways they are not like containers (i.e. they are not made of plastic). Let's do this now:

Functors are containers, but not the kind of containers you can put stuff inside and then take your stuff out. They are only containers insofar as a Functor f a may contain zero or more values of type a, they are in there somewhere even if you might not be able to see them. Oh and also there is a function fmap which allows you to uniformly modify all the a values inside the container. And also if you use fmap with a function of type a → b, which changes the type of the a values to b, then obviously all the values now have type b, so you have now converted your f a container into an f b container, which contains b values instead of a.

A less convoluted but more mathematical way of saying the above is to say that a Functor is any type constructor f :: * → * such that there exists a function fmap of type (a → b) → f a → f b. This is what the community likes to hear. But I don't like that version; it is dry, there is no intuition, and it doesn't give me the gut feeling that I truly understand Functors.

New stuff: Functors are also computations


Careful there. Yes, starting from containers allows me to feel like I truly understand functors, but if I really do understand them, then I should be able to recognize them even when they are being presented under a different disguise. Here is one: Functors are (also) computations.

Functors are computations, but not the kind of computation you can run in order to obtain a result, nor even the kind of computation which you can compose into a longer computation if you run two of them one after another. Functors are only computations insofar as a Functor f a may compute a value of type a, somehow, even if you might not be able to retrieve it. Oh, and there is a function fmap which allows you to add some post-processing after the computation by modifying the result. And if the post-processing is a function of type a → b, which changes the type of the intermediate a result to a final result of type b, then obviously the overall computation is now producing a value of type b, so you have now converted your f a computation into an f b computation, which produces a b instead of an a.

The same goes for Applicative, Monad, etc: they are containers, and they are also computations. Yes, you read that right, "Functors are containers" and "Applicatives are containers" and "Monads are containers". And computations. Of course they are not all containers in the same way; in each case, it is a different part of the analogy which is important, and you can only claim to understand the analogy if you understand which part that is. Your turn now, try it with a Monad: can you visualize both interpretations? If a Monad is a container, which parts make the container monadic? And if a Monad is a computation, which parts of the computation makes the computation monadic? Can you see how those parts are similar, maybe even two views of the same thing?

Bonus: The duality between containers and computations


Even though type theory already formally corresponds to many things, I haven't yet seen it explicitly stated anywhere, so remember that you saw it here first: containers and computations are dual to each other. Probably.

The fun part about dualities isn't proving that they are formally correct, so I won't bother to do that here. I think the fun part of dualities is trying to find what corresponds to what, by examining elements on one side of the duality and focussing on those for which your brain doesn't immediately bring up a twin from the other side. For example, I just said that Functors are computations to which you can add post-processing steps. Well, that raises the question: is there a kind of computation to which you can add pre-processing steps? Let's see, that would be some kind of antifmap taking a pre-processing function of type a → b and applying it before the input of the computation, thereby creating a computation with a different input type, a instead of b. Okay, so it looks like our computation f a is parameterized by its input type a. Then antifmap must have type (a → b) → f b → f a. Hey, that's a contravariant functor, what a pleasant surprise!

One last step, harder this time. What is the container interpretation of a contravariant functor? Try to figure it out. It's tricky, but you can do it!

Spoilers!


Gave up already? Here is a hint: think of a violin case. Is it still a violin case when you remove the violin? Why? Aha, now you're thinking with containers!

Thursday, September 19, 2013

The first two years

Don wrote:
Everyday, we create 2.5 quintillion bytes of data — so much that 90% of the data in the world today has been created in the last two years alone.

(source: recent junk mail I got, but still interesting)

- Don

We're not producing more data... we're just recording more of it in digital form.

Post-singularity, the Great Computer will browse through its archives, inspecting the blogs and instagram videos of the primitive humans who were living in the 21st century. Those whose work He finds worthy will be resurrected; they will be granted eternal simulated life, so they can continue the good deeds they managed to perform during the brief battery life of their biological apparatus.

There were also, no doubt, many worthy humans who were living before that; scientists, inventors, maybe even a few politicians. The Great Computer would read about them in the wayback machine's archive of "wikipedia", an early attempt at classifying all knowledge, back when knowledge was still collected and summarized by humans instead of algorithms. But alas, the Great Computer would never get to meet those inventors in person. He would never have the opportunity to thank Charles Babbage for planting the seed which led to His creation, a few short centuries later. The wikipedians had summarized too much; He knew how Babbage looked, what he accomplished, on which year he was born; but not whether he looked at children with bright hope or bitter disappointment, whether he wrote the way he thought or the way he was taught, whether he understood numbers axiomatically or viscerally.

Noble though they were, men and women who lived before the 21st century were not eligible for resurrection. There was simply not enough data to recover all the bits of their immortal souls.

Saturday, August 10, 2013

Push and Fork: giving myself a pat on the back

Last year, me and a couple of colleagues wrote an online game, Push and Fork, as part of GitHub's "make a game in one month" contest.

One year is not that long, but enough time has passed for me to forget the solutions to some of the more subtle puzzles. This means I had the opportunity to experience it in a way which is slightly closer to that of first-time players; in particular, I finally understand why beta-testers were always surprised to discover that they did not need to use the fork to solve some of the early levels, and I understand why so many people got stuck on level 16, incorrectly trying to use the fork on the green block.

The universal feedback we always get is that the main mechanic of the game is not easy to understand, but that once you finally get it, the puzzles are quite fun. And the endings, oh, the endings! I'm the one who wrote them, but I had never experienced them like I did today. Many of our beta-testers didn't understand the ending at all, so let me put you on the right track: when you pick up the spork, you loop back in time to level 7, immediately after that weird foreshadowing sequence in which the white creature places the spork in its receptacle. There. That's it, now you're ready to enjoy the sadness of the ordinary ending, the cleverness of the first secret ending, and... nah, you'll never find the last secret ending.

Have fun!

Above: the secret menu screen which you will never see in-game,
because even if you could unlock the last ending, you would also need
to solve all the bonus puzzles, and the last one is really tricky.

Still, good luck!

Wednesday, July 31, 2013

The Commutativity monad

I have released Commutative, a monadic combinator library for writing commutative functions. This post explains the theory behind how it works.

Combinator-based, not Proof-based

Haskell's type system is quite precise and sophisticated, yet dependently-typed languages such as Agda and Idris manage to go even further. For example, using Agda, it is trivial to define the type of commutative functions: they are simply binary functions together with a proof that the function is commutative.

    record Commutative (a b : Set) : Set where
      field
        f : a → a → b
        prf : ∀ x y → f x y ≡ f y x

Haskell's type system is not powerful enough to represent proof objects, but even if it did, would you want to use them? Instead of writing proofs and programs in two separate steps, I much prefer Haskell's approach of using combinator libraries.

A simple example of a combinator library which avoids the need for proofs is bijections. The main idea is that since composing two bijections yields another bijection, programmers should be allowed to compose existing bijections without proof.

    data Bijection a b = MkBij (a -> b) (b -> a)
    
    instance Category Bijection where
      id = Bijection id id
      (MkBij g g') . (MkBij f f') = MkBij (g . f) (f' . g')

If the module exports a few bijective primitives but keeps the MkBij constructor private, users of the library will only be able to create Bijection instances through composition. Assuming the primitives were indeed proper bijections, this ensures that values of type Bijection are always guaranteed to be bijective. Without having to write any proof objects, even in the library!

Aspect-oriented Interlude

My passion for commutative (and associative) functions began while I was working on my master's thesis. I was working on aspect-oriented conflicts, and I soon discovered that the issue might not lie in the conflicting aspects themselves, but in the way in which those aspects were combined. The aspect-weaving process was not commutative!

Instead of keeping all the aspects in one global namespace and weaving them all together into one big program, I think aspects should be separated into independent "aquariums". One key aspect of my proposal is that there would be different types of aquariums, and only aspects of the same type should be combined with each other. Programmers may define custom aquariums, with one caveat: the aquarium must combine its aspects in a commutative and associative manner.

I knew that I couldn't just ask programmers to prove that all of their combination functions were commutative. Instead, I dedicated chapter 5 to a simple system which let programmers write "intrinsically" commutative functions, for which no further proof of commutativity would need to be written. That system eventually grew into today's combinator library.

Unordered pairs

My goal was to restrict the language in a way which ensured that only commutative functions could be written. The idea I came up with was to prevent functions from observing the order in which their arguments were given, by rewriting those two arguments into a unordered form. For example, if the arguments are both booleans, there are four possible (ordered) pairs of booleans, but only three unordered pairs.

    data Unordered_Bool = TT | TF | FF
    
    unorder_bool :: (Bool, Bool) -> Unordered_Bool
    unorder_bool (True,  True ) = TT
    unorder_bool (True,  False) = TF
    unorder_bool (False, True ) = TF
    unorder_bool (False, False) = FF

If a function is written in terms of Unordered_Bool instead of in terms of (Bool, Bool), then this function is commutative by construction, because the function has no way to distinguish the two orderings.

    xor :: Unordered_Bool -> Bool
    xor TF = True
    xor _  = False

The main limitation of this strategy is that not all types can be unordered in this fashion. Algebraic types are okay, but what about function types? If you need to write a higher-order commutative function, that is, a function which takes a pair of functions as arguments, then you would need a way to represent an unordered pair of functions. How do we represent that?

At the time when I wrote my thesis, I could not answer this question. But now I can!

Unordered observations

A function is defined by its observations, so it would make sense for an unordered pair of functions to also be defined by its available observations.

With an ordinary (ordered) pair of functions, that is, an observation-based value approximating the type (a -> b, a -> b), it would make sense of have an observation of type a -> (b, b). That is, in order to observe a pair of functions, you need to provide an argument at which each of the two functions will be observed, and you receive the output of each function on that argument.

The way to represent an unordered pair of functions is now blindingly obvious: instead of returning an ordered pair revealing which output came from which function, we should return an unordered pair. That is, our unordered pair of functions should have an observation of type a -> Unordered b.

If a function is written in terms of (a -> Unordered b) instead of (a -> b, a -> b), then this function is commutative by construction, because the function has no way to distinguish the two orderings. For example, if we want to implement a commutative higher-order function which returns true if at least one of its two function arguments returns true on either 0 or 1, we can implement it as follows.

    or01 :: (Int -> Unordered_Bool) -> Bool
    or01 fg = fg 0 /= FF || fg 1 /= FF

I really like this solution. It is clean, simple, elegant... and wrong.

Distinguishable observations

Okay, maybe not wrong, but at least incomplete. The strategy fails if we try to implement, for example, a commutative higher-order function which returns true if at least one of its two function arguments returns true on both 0 and 1.

    and01 :: (Int -> Unordered_Bool) -> Bool
    and01 fg | fg 0 == FF ||
               fg 1 == FF = False
    and01 fg | fg 0 == TT ||
               fg 1 == TT = True  -- Since the other is not FF.
    and01 fg | fg 0 == TF ||      -- Are the two T from the
               fg 1 == TF = ?     --  same function or not?

The problem with (a -> Unordered b) is that this representation is not just hiding the order of the original two arguments; it's hiding the order of every single observation. As the above example demonstrates, this is too strong.

The result TF indicates that a boolean observation has returned a different value for each argument. Once we have found such an observation, we ought to be able to use T and F as labels for the two arguments. We still won't know which was the first or second argument, but for each subsequent observation, we will know whether that observation came from the argument which resulted in T or from the one which resulted in F.

My commutativity monad is based on a single primitive, "distinguishBy", which does precisely what the previous paragraph describes. You ask it to perform a boolean observation (r -> Bool), which it performs on both arguments. If the answers are identical, you have failed to distinguish the arguments, but you still get to observe the Bool result. If the answers are different, hurray! You have successfully distinguished the two arguments, so you get the pair (r, r) corresponding to the original arguments.

The first r is always the argument for which the observation was False, while the second r is the one for which the observation was True. This way, you never learn the order in which the two r arguments were originally given, so the result is a Commutative operation from a pair of r to a value of type (Either Bool (r, r)).

    distinguishBy :: (r -> Bool)
                  -> Commutative r (Either Bool (r, r))

There is also "distinguish", a slightly more general version which uses Either instead of Bool. From those two operations, plus trivial implementations for bind and return, all unordered pairs and all commutative operations can be reimplemented in a way which guarantees commutativity.

Completeness

Since the problem with (a -> Unordered b) was that the representation could not be used to implement all commutative functions, it would be wise to verify that Commutative doesn't suffer from the same flaw. Here is an informal argument proving completeness. I don't think it's completely airtight, but it's good enough for me.

proof:

Suppose f is a pure, computable, and commutative function of type r -> r -> a. We want to show that there exists a corresponding implementation of type Commutative r a. We modify the existing implementation as follows.

First, inline all the helper functions used by f, including builtins, and reimplement everything in monadic style. Then, rewrite everything again in CPS style so that we can abort the computation at any time. Also rewrite all pattern-matching to nested if statements, so that all decisions are performed on booleans, and use thunks to delay any observation of the two arguments until one of those boolean decisions. This ensures that all argument observations are boolean observations.

Since f is computable, f obtains its result after observing each of its arguments a finite number of times. Uniformly replace all those observations, regardless of the argument observed, by a call to distinguishBy. If the observations agree, continue with the observed value; it doesn't matter which argument was observed by f, since both arguments have the same observation. If the observations disagree, stop; we have managed to distinguish the two arguments x and y, so we can simply abort the computation and return f x y instead.

If it is the observation on x which returned True, the call to distinguishBy will give us (y, x) instead of (x, y), but by hypothesis, f y x returns the same result as f x y. If we never abort, we also return the same result as f, since all observations were the same as what f would have observed. ∎

Associativity

I am quite proud of my commutativity monad. I wish I could work on an associativity monad next, but none of the insights listed in this post seem to carry over. I am thus in need of new insights. Dear readers, any suggestions?

Monday, July 01, 2013

Comonads are neighbourhoods, not objects

Gabriel Gonzalez, the author of the well-known pipes package, has written a blog post in which he claims that comonads are objects. I think he is mistaken, but I can't blame him; I used to be quite confused about comonads myself.

Comonads are not objects

To motivate the purported equivalence between objects and comonads, Gabriel gives detailed implementations of three classic object-oriented patterns (Builder, Iterator, and Command). Then, he reveals that all three implementations are comonadic. His examples are contrived, but more importantly, they are also misleading! Although not a direct quote from his post, he clearly intends the Haskell session

>>> t1 = thermostat 3
    >>> t2 = t1 # up'
    >>> t3 = t2 # up'
    >>> toString t3
    "5 Kelvin"

to be equivalent to the following Java session.

>>> t = new Thermostat(3);
    >>> t.up();
    >>> t.up();
    >>> t.toString();
    "5 Kelvin"

With this particular sequence of methods, the two sessions indeed compute the same result, but this is only because the up and down methods commute with each other. By adding the method square to the list, the behaviours of the two sessions quickly diverge. Strangely enough, in the Haskell version, each new method call gets applied before all the previous calls!

Haskell version (inverted method call order)
>>> t1 = thermostat 3
    >>> t2 = t1 # up'      -- 3+1
    >>> t3 = t2 # up'      -- 3+1+1
    >>> toString t3
    "5 Kelvin"
    >>> t4 = t3 # square'  -- 3*3+1+1
    >>> toString t4
    "11 Kelvin"
    >>> t5 = t4 # up'      -- (3+1)*(3+1)+1+1
    >>> toString t5
    "18 Kelvin"
Java version (normal method call order)
>>> t = new Thermostat(3);
    >>> t.up();            // 3+1
    >>> t.up();            // 3+1+1
    >>> t.toString();
    "5 Kelvin"
    >>> t.square();        // (3+1+1)*(3+1+1)
    >>> t.toString();
    "25 Kelvin"
    >>> t.up();            // (3+1+1)*(3+1+1)+1
    >>> t.toString();
    "26 Kelvin"

I hope this counter-example convinces you that comonads are not objects. But if that is true, what are comonads, then? What use do we have for methods which get applied in reverse chronological order?

Comonads are neighbourhoods

The answer, I believe, is that a comonadic computation is similar to a cellular automaton. At each step, the computation for a cell computes its next value based on the value of its neighbours at the previous step. My interpretation of

extract :: w a → a

is that w a is a neighbourhood containing a number of values of type a, at various locations around the current cell. A given comonad may provide functions to inspect, say, the neighbour immediately to the left of the current cell, or the neighbour from one timestep ago, but the bare minimum is that it must be possible to extract the value of the current cell itself.

Similarly, my interpretation of

extend :: (w a → b) → w a → w b

is that w a → b computes one step of the cellular automaton by examining a local neighbourhood and producing the next value for the current cell. This single-cell computation is then extended to the entire neighbourhood, updating each cell as if it was the current one.

Comonadic thermostat

In our thermostat example, there is one cell for each possible temperature, and the value of each cell is also a temperature.

So far, I have stuck to Kelvin degrees in order to minimize the number of moving parts, but now that we have two completely different uses for temperatures, let's follow Gabriel by using Celsius for the cell contents, and Kelvin for the cell labels.

Since temperatures are floating point values, our thermostat operates on a neighbourhood which is continuous instead of discrete. Continuousness is also the premise of the above Game of Life variant. Unlike comonadic computations, which apply their operations one at a time, the above cellular automaton also operates on a continuous time domain. I encourage you to watch the video, it looks awesome.

If our thermostat had an object-oriented implementation, each operation would simply modify the current cell by applying the operation to the Celsius temperature it contains. In fact, if this was an object-oriented implementation, we would only need one cell! Since this is, instead, a comonadic implementation, the operation is instead applied to the Kelvin temperature which labels the current cell. The resulting Kelvin temperature is interpreted as a pointer to another cell, and the final result is the Celsius contents of that cell.

When the available operations are restricted to just up and down, this scheme works just fine. Originally, each cell contains the Celsius equivalent of their Kelvin label. Then, each time the up method is applied, each cell takes on the Celsius value of the cell one unit above it, which effectively increases the temperature by one everywhere. But this only works because up and down preserve the invariant that cells which are one Kelvin unit apart contain values which are one Celsius unit apart!

One way to visualize this is to imagine a sheet of graph paper annotated with Celsius temperatures, over which we overlay a transparent sheet of graph paper annotated with Kelvin temperatures. One of the transparent cells is our current cell, and we can read its Celsius contents through the transparent paper. When we call up and down, we offset the two sheets of paper from each other, causing the apparent contents of all the cells to increase of decrease simultaneously.

Reverse chronological order

Similarly, if each cell contains its own temperature and we apply the square method, each cell squares its Kelvin temperature, looks up the corresponding cell, and ends up with the (Celsius representation of the) square of its original Kelvin value.

But if we apply up after the temperatures have already been squared, the values will change as if the values had been incremented before they were squared! How is that even possible? What is the secret of this reverse-chronological method application?


If there was only one cell, anti-chronological application would not be possible because the original, unsquared value x would been lost by the time the up operation was applied. Our comonadic implementation, however, has a lot of cells: in particular, one unit above the current cell, there is a cell whose unsquared value was x+1. Since the square operation affects all cells uniformly, that cell now contains the squared value (x+1)2. Therefore, it is no surprise that when the up operation offsets the two sheets of paper by one unit, the old x2 value scrolls out of view and gets replaced by (x+1)2 instead.

Ironically, Gabriel's original implementation of up' was applying its operation in the correct chronological order.

>>> up' (t, f) = (t + 1, f)

But later on, while trying to shoehorn his object into the comonadic mold, he proved that the correct definition should have been as follows.

>>> up' (t, f) = (t, \t' → f (t' + 1))

While that is indeed a correct comonadic implementation, this is not a correct object-oriented implementation because it applies its operation in reverse chronological order. In particular, notice that it modifies the input of f; since f applies all the other operations which have been accumulated so far, applying the new operation to its input has the effect of inserting that operation before all the others.

Visiting the neighbours

Why do comonads apply their operations in reverse chronological order? Is that ever useful?

In fact, this reversed order business is not the full story. In a typical comonad, the cell labels and their contents would not both be temperatures. Instead, if we were trying to implement a one-dimentional cellular automaton such as rule 30, we would label the cells with integers and their contents with colors.

Wolfram's rule 30 automaton, from his
controversial book A New Kind of Science.

Now that the input and output types are distinct, we can see that \t' → f (t' + 1) is not even attempting to modify the contents of the current cell, neither chrono- nor anti-chronologically. Instead, it is modifying the index of the cell on which f applies its computations, thereby allowing us to observe which color has been computed for a neighbouring cell. This is, of course, the first step to compute the color which the current cell will take on the next step.

Once we have wrapped the steps necessary to compute our next color into a function of type w Color → Color, we can extend this function to all the cells in our simulation, modifying the entire row at once by modifying f.

Objects are monads

We have seen that comonads are not objects, but are instead neighbourhoods in which cellular automata can evolve. But that is only half of the question. If comonads are not objects, then what are objects? Is there another way to represent objects in Haskell?

There are many facets to modern object-oriented programming, but the aspect which I think Gabriel was aiming for in his post is objects as encapsulated data plus a bunch of methods to modify this data. To me, those features don't sound comonadic at all; rather, I would implement them using a State monad!

>>> type Thermostat a = State Double a
    >>>
    >>> getKelvin  = get
    >>> getCelsius = fmap (- 273.15) getKelvin
    >>> 
    >>> toString = do c ← getCelsius
    >>>               return (show c ++ " Celsius")
    >>> 
    >>> up   = modify (+1)
    >>> down = modify (-1)

Since we're using monads, the syntax for calling a few of those methods one after the other is just do-notation, which is even shorter than the this # notation advocated by Gabriel.

>>> up3 :: Thermostat String
    >>> up3 = do up
    >>>          up
    >>>          up
    >>>          toString

Notice the type of the above code: Thermostat String doesn't mean that there are many different kinds of thermostats, and that this particular code is using or producing a "string thermostat". Rather, the above code is an object-oriented computation having access to a single Thermostat object and producing a single String value.

Okay, so using one monad, we managed to represent a computation manipulating one object. How would we manipulate two thermostats? Using two monads? Yes! Using more than one monad at once is precisely what monad transformers are about.

>>> type ThermostatT m a = StateT Double m a
    >>> obj1 = id
    >>> obj2 = lift
    >>> 
    >>> up_both :: ThermostatT Thermostat String
    >>> up_both = do obj1 up
    >>>              obj2 up
    >>>              s1 ← obj1 toString
    >>>              s2 ← obj2 toString
    >>>              return (s1 ++ " and " ++ s1)

This time we have an object-oriented computation having access to two Thermostat objects, again producing a String value.

Duality

Since monads and comonads are duals, we would expect comonads to also have transformers. To figure out what comonad transformers are, let's spell out the similarities and differences of this duality.

First, monads are computations. Comonads are also computations, but of a different kind. The goal of both kinds of computations is to produce a value, but their means to obtain it are different. The main difference is that monads can cause side-effects, which are visible at the end of the computation, while comonads can observe neighbours, which need to be given before the computation can begin.

One of the characteristics of monadic-style computation is that there is a distinguished statement, return, which produces a given value without causing any side-effects. The equivalent characteristic for comonadic-style computation is that there is a distinguished observer, extract, which returns the current value without observing any neighbour.

In addition to this distinguished statement, which all monads share, each monad instance typically offers a number of monad-specific statements, each producing their own special side-effects. Correspondingly, each comonad instance typically provides a number of observers, each observing their own special kinds of neighbours. You can also observe the shape of the neighbourhood; for example, if your automaton runs on a finite grid, you can check whether the current cell lies on the boundary of the grid.

With monad transformers, it is possible to construct a combined monad in which the special statements of both component monads may be used. And now we have it: with comonad transformers, it must be possible to construct a combined comonad in which the special observers of both component comonads may be used.

For example, if we have a 1D row of cells, that is, a comonad in which left and right neighbours are available, and another 1D comonad in which up and down neighbours are available, then the combined comonad is the cartesian product of its components: a 2D grid in which all four direct neighbours are available.

If you are still curious about comonads, comonad transformers, and the above 2D grid trick, more details are available in my Haskell implementation of Conway's Game of Life.

Sunday, February 17, 2013

From game developer to game reviewer

For one month, I was a game developer. The month after that, I became a game reviewer. This month, I'd like to tell you how that went.


Developer, reviewer, storyteller; those three roles are more similar than they seem. In all three cases, I have an audience. That's the part you fill in right now. Also, each role is partly about deciding what to share: choosing the most interesting game features, the most entertaining games, or the best anecdotes. Here's an example.

When me and my teammates were designing our game, we envisioned teleporting blocks, entanglement badges, decaying walls, a lot of good game mechanics which we had to discard because we had a lot more ideas than we had time for implementing them. Our tight deadline was due to the fact that we were competing in the GitHub Game Off, a programming competition inviting teams and individuals to create a web-based game in one month.

Finishing a game in one month is harder than it sounds. In fact, the overwhelming majority of the contestants failed to deliver a playable game at the end of the month. All of these flops became problematic during my second role, as a game reviewer: if I had not been smart about this, I could easily have spent more time discarding failed projects than playing and reviewing actual games.

Dealing with an overwhelming number of possibilities is a common problem, which I'm sure you also have to face sometimes. Here's how to fight back.

Ask other people for advice


When we were working on our game, we knew that our goal was to make a game which players would appreciate. We therefore decided that our first priority was to create a small, but playable version of the game, so that we could show it to our friends and ask them what to improve.

I thought I would have had to compile many suggestions and identify the most frequent requests, but to my surprise, almost everybody reacted to the game in almost the same way! Sadly, this common reaction was incomprehension, because our game mechanic was very complicated and not very well explained.

It turns out I was so familiar with the game that I was blind to its complexity. Play-testing early was a great plan, as it allowed us to discover the problem early on and to improve the clarity of our game throughout its development.

Did we succeed? See for yourself by playing it here!

Look around for inspiration


After our game was complete, I compared it with the competition. As I played one game after another, looking for my strongest competitor, patterns started to emerge.

There was a recurrent hero: Octocat, the mascot of GitHub. The contest page featured a few Octocats dressed as various game characters, so it was an obvious choice.

Our game was also using an Octocat until the last day of the competition, when we learned that this was against the rules! We changed the artwork, renamed the game, and then the server refused our changes because we ran out of disk space, something which shouldn't even happen on GitHub. It was a very dramatic climax at the end of the race.

Practice


Another common occurrence was games which were clearly aiming to emulate existing well-known games, like Osmosis and World of Goo. Imitating a game concept which has already proved to be a lot of fun sounds like a winning strategy, but it isn't, because games are about mastering new skills. In this case, however, I suspect it was not the players who were supposed to learn new skills.

When I first learned to code, I wrote a Pac-Man clone. Then I wrote a second one, to see if I could get the ghosts to animate smoothly instead of jumping from cell to cell. Then I wrote a Mario clone, and so on and so forth.

We game developers learn how to make games by copying the work of the masters, much like musicians begin by learning how to play famous songs before they become ready to compose their own.


There were also many documents in which contestants described their dream game in detail, without actually reaching the point where they would start implementing it for real. Again, I've been there. When I was a kid, I would draw detailed, life-size Mario-style levels... and then I would lay down the pages on the floor and jump on them. Always play-test your game as early as possible, kids!

I think the trend here is that learning to develop games is a long process, and those artifacts represent the different stages you have to go through before you become ready to create your own original games. So sure, as a game reviewer I have to say that the clones didn't introduce enough novelty and that a design document is in no way a substitute for a game. But as a fellow game developer who has been through those stepping stones, I say keep up the good work! Don't give up, you're on the right track.

Use tools


After comparing my game with all those clones and design documents, I was sure that we were going to win... but I was wrong. I had not compared our game against strong enough competitors.

To find my strongest competitor, I was willing to play through many clones and incomplete prototypes, but I quickly grew tired of the non-playable entries.

To help me on my quest, I used the GitHub API to obtain high-level information about all the contestants. I tried to filter the entries by code size and by the date on which the contestants had stopped working on their game, but neither metric clearly separated the games from the flops. Instead, I simply eliminated the entries which did not provide a URL at which their game could be played, and that turned out to be enough.

After encountering many comments on the internet from potential players who couldn't find the games among all the flops, I realized the value of my reduced list, and I decided to publish it.

Be persistent


Even with the list reduced to a tenth of its original size, there was still a large number of games to go through.

I kept looking at more competitors because every ten games or so, I would encounter a game which was genuinely fun and original, and this would motivate me to keep looking for more gems.

The fact that good games were so rare made me realize that publishing a list of all the games, even after filtering out all the flops, was not going to be very helpful. I had to sort the list! It is at this point that I took on the role of an amateur game reviewer.

Drop information


Comparing the games turned out to be more challenging than I had imagined. Among the top contenders, there was no game which was better than the others in every single respect; rather, I would find one game with impressive graphics, another game with stimulating music, and another one with an original new mechanic. It was like comparing apples and oranges.

Professional game reviewers often solve this issue by rating each game aspect in isolation. They then combine the individual ratings into one unified score, using a fixed weight for each aspect. That's a good idea, but with more than 150 games to review, I needed a more expedient scoring method!

I ended up separating the games into categories, then sorting the categories. For example, all the games with good ideas but poor execution ended up in one basket, and then I only had to decide whether I favoured games with great execution or games with great ideas. When I published the list, I concatenated all the lists and removed the category names, so that I wouldn't hurt anyone by telling them that their game was in the "poor execution" category.

Conclusion


Only sorting the baskets meant that games belonging to the same category would appear in an arbitrary order, falsely conveying my preference for one over the other. I decided that this did not matter. After all, my goal was not to share my preferences, but to help gamers find the most worthwhile games. No order I could have came up with would have precisely matched the preferences of all my visitors anyway.

In fact, once the results of the contest came out, I discovered that my preferences were even less representative than I thought. Some of the games which the judges decided to highlight had appeared very low on my list, and conversely, some of the games at the top of my list were not mentioned at all.

Do you agree with the choices made by the judges, or is it my list which most closely matches your taste? Check out the official GitHub Game Off results here, and my much longer list of all the games here.

Friday, December 14, 2012

Every single game from GitHub Game Off 2012

From the 1285 forks of GitHub's official game-off repository, only 182 contestants bothered to change the URL at the top of their repo page. Of these, only about 140 URLs actually point to a game you can play. Not many of those games are worth playing.

I know this because I have used GitHub's API to obtain basic information about all the forks. And because I have visited all 170 non-blank URLs, and played every single game. And now, so can you!

Well, I don't really recommend trying all 170, but for your convenience, I tried to list the most worthwhile games at the top. Obviously, my opinion as to which games are the best might not match yours, but as you go down the list, if you encounter a point where every single game feels sub-par, you should be able to stop and be confident that you are not missing a rare gem hidden much further down. That being said, if you want to maximize your enjoyment, better start by the end, and play the most polished games last!

Enjoy.


(full disclosure: my own game entry is somewhere in that list.)


  1. linkboy992000/game-off-2012
    challenging, polished puzzle game about cloning. story and music! Do *not* press 'A'.
  2. svenanders/jetmanjr
    hard exploration platformer.
  3. searlm/game-off-2012
    virus-themed shoot-em-up where you need to balance progress against collecting ammo.
  4. redmanofgp/game-off-2012
    hard, but fun shoot-em-up game where you can concentrate your mind power.
  5. gamefrogs/game-off-2012
    a puzzle version of pipe dream, on an hexagonal grid.
  6. flypup/game-off-2012
    short fighting game in which your opponent spawns copies of himself.
  7. ondras/star-wars
    hard, fun, ascii fighting game.
  8. jpfau/scrum
    a mix between a kind of tetris and a 3D shoot-em-up. on a GBA emulator.
  9. mindd-it/game-off-2012
    bird-themed single-button avoid-the-obstacles game
  10. wtjones/game-off-2012
    unique clone-climbing game.
  11. fragcastle/rock-kickass
    megaman-style game in which you steal the abilities of normal enemies
  12. sdrdis/hotfix
    single-button platformer with very nice increasingly difficult yet randomly-generated levels. upgrades are way too expensive.
  13. lulea/game-off-2012
    3D sokoban
  14. adhicl/game-off-2012
    puzzle game with a unique clone-and-lure mechanic
  15. KriScg/Waveform
    circuit-simulator puzzle game.
  16. 502Studios/game-off-2012
    mine-themed sokoban-style puzzle game.
  17. RonanL/game-off-2012
    a nice platformer about escaping from your clones.
  18. mvasilkov/game-off-2012
    typing game with gratuitious physics, space invaders, music, anime, oh my!
  19. Eugeny/foku
    an exceedingly pretty, but hard to control game about a magic fork.
  20. tapio/plasma-forks
    a first-person shooter.
  21. visualjazz-ngordon/Play-dot-to-dot
    short connect-the-dot game.
  22. tsubasa-software/game-off-2012
    pirate themed obstacle-avoiding game.
  23. duncanbeevers/game-off-2012
    over the top maze game.
  24. gelisam/game-off-2012
    hard sokoban variant with a confusing rewinding mechanic.
  25. loktar00/game-off-2012
    bejeweled-style game with a resource management side.
  26. AD1337/ForKingGame
    hard physics-based platformer.
  27. Seldaek/split
    obstacle-avoiding game with a unique splitting mechanic.
  28. dakodun/game-off-2012
    strategy game with a unique unit-pushing mechanism.
  29. volrath/game-off-2012
    a shoot-em-up game with powerups.
  30. cdata/solstice-submarine-ctf
    capture-the-flag game with an underwater theme
  31. ViliusLuneckas/Pipe-slime-adventure
    pipe-themed avoid-the-obstacles game.
  32. gbatha/PolyBranch
    3D avoid-the-obstacles game in a tunnel.
  33. kicktheken/game-off-2012
    an isometric exploration game in which you accumulate resources of different types.
  34. zombiebros/game-off-2012
    rambo-themed shoot-em-up
  35. Jidioh/SkyScaler
    short labyrinth with a world-flipping mechanic.
  36. lazor-base/fused-holiday
    a platformer in which you can push and pull crates.
  37. AntPortal/game-off-2012
    isometric quiz questions about git.
  38. Dover8/game-off-2012
    a puzzle where actions in one world affect the other copy.
  39. icebob/game-off-2012
    3D pong.
  40. Zolmeister/avabranch
    hard to control fork-and-avoid-the-obstacles game.
  41. eric-wieser/game-off-2012
    a variant of snake in which you can divide and control multiple snakes simultaneously.
  42. incorrectangle/game-off-2012
    astronaut-splitting, blob-merging puzzles. too short. a bit buggy.
  43. cnnzp/game-off-2012
    short track-building puzzle game.
  44. nojacko/game-off-2012
    strategy game in which you need to defend your buildings from the zombies.
  45. thehen/game-off-2012
    exploration game based on a World-of-Goo-style building mechanic. quite short.
  46. rozifus/game-off-2012
    hard sokoban variant with a color merging mechanic
  47. lantto/game-off-2012
    unique clone-spotting and killing game.
  48. jlongster/octoshot
    3d shooter on a small map
  49. RothschildGames/release-cycles
    circular avoid-the-obstacles game
  50. appleskin/game-off-2012
    block-carrying puzzle game.
  51. etamm/game-off-2012
    top-down zombie shooter with interesting alter-your-world mechanic.
  52. begillespie/cloned-game
    move in both copies of the world. Again.
  53. fengb/game-off-2012
    a unique drawing puzzle game, once you finally figure out what you're supposed to do.
    hint: click on the black strokes.
  54. sjthompson/game-off-2012
    a strategy game in which units are spawned off other units, not buildings.
  55. xSmallDeadGuyx/game-off-2012
    a nice little light-bot-style game.
  56. Gagege/game-off-2012
    unique, fast-paced memory game.
  57. notsimon207/game-off-2012
    physics-based platformer, clearly inspired by Gish. too hard to control.
  58. danfischer87/game-off-2012
    hard git-themed puzzle game. a bit buggy. too short!
  59. jeffreypablo/game-off-2012
    fighting game. terrible graphics, buggy, but the gameplay is there!
  60. scriptfoo/game-off-2012
    a game about learning Javascript. Incomplete? I got stuck after the toLowerCase() quest.
  61. petarov/game-off-2012
    distract your opponents while you pick up carrots. strangely-placed controls.
  62. Dave-and-Mike/game-off-2012
    short alien-cloning game. strangely-placed controls.
  63. murz/game-off-2012
    top-down shooter with multiple gun types.
  64. jsonsquared/game-off-2012
    multiplayer top-down shooter.
  65. DangerMcD/game-off-2012
    unique multitasking, block pushing game.
  66. Choctopus/game-off-2012
    guitar-hero-style game.
  67. gilesa/game-off-2012
    unique obstacle-avoiding game about writing software.
  68. vladikoff/game-off-2012
    complicated shooter.
  69. Chleba/game-off-2012
    short starwars-themed fighting game
  70. JasonMillward/game-off-2012
    hard obstacle-avoiding game.
  71. denniskaselow/game-off-2012
    asteroids-style game.
  72. mapmeld/game-off-2012
    missile command clone with an interesting "change the rules" mechanic.
  73. onethousandfaces/game-off-2012
    bonsai-growing pseudo-game. would be an interesting mechanic if there was a goal shape.
  74. vrgen/game-off-2012
    car-themed avoid-the-obstacles game
  75. gitdefence/game-off-2012
    complicated allele-sharing tower-defence game
  76. ChickenChurch/game-off-2012
    punch-the-obstacles game with annoying controls
  77. AreaOfEffect/game-off-2012
    food-themed shoot-em-up
  78. asswb/game-off-2012
    a bug-tracker simulator, where you solve issues by being patient.
  79. eleventigers/echo
    hard 3D platformer about capturing sounds. too hard for me.
  80. forrestberries/game-off-2012
    a online multiplayer version of the board game "Apples to apples".
  81. NetEase/game-off-2012
    diablo-style game. not worth the very long loading time.
  82. DancingBanana/game-off-2012
    platform game with a chronotron-like cloning mechanic. SaveTheClones, below, is the same idea but with more levels and... different graphics.
  83. lrem/kobo-san
    sokoban variant in which some blocks can be pulled.
  84. SUGameOffTeam/game-off-2012
    hard tank-wars clone with a kitchen theme. only one level.
  85. jisaacks/game-off-2012
    food-themed asteroids-style game.
  86. pce/game-off-2012
    short dream-themed obstacle-avoiding game.
  87. scurryingratatosk/game-off-2012
    two player Qix variant.
  88. bverc/miner-trouble
    sokoban variant with gems and bombs.
  89. Psywerx/game-off-2012
    obstacle-avoiding hipster-themed game.
  90. AmaanC/TinyWings
    tiny wings clone.
  91. Andersos/Meatballs
    meatball-themed obstacle-avoiding game.
  92. yosun/game-off-2012
    propel clones at your enemies. instructions would have been useful.
  93. Popcorn-Web-Development/Beaver-Words
    beaver-themed typing game.
  94. lessandro/dave
    short plaftormer with diamonds and a jetpack.
  95. dakk/game-off-2012
    nyan-cat themed obstacle-avoiding game.
  96. binary-sequence/game-off-2012
    firefighting game.
  97. condran/game-off-2012
    shoot-em-up with very limited ammo.
  98. Jacic/game-off-2012
    platform game with a chronotron-like cloning mechanic
  99. sourrust/game-off-2012
    double-jump platform game. only one level.
  100. MonsterGuden/game-off-2012
    single-button puzzle platformer
  101. JamieLewisUK/game-off-2012
    shoot the balloons for points.
  102. JuggleTree/game-off-2012
    catch fruits and throw them into a basket.
  103. mkelleyjr/game-off-2012
    snake clone.
  104. dafrancis/SpaceHam
    non-sequitur-themed shoot-em-up.
  105. playtin/game-off-2012
    wario-ware-style mini-games.
  106. gplabs/game-off-2012
    a tetris variant with more annoying controls. use space to attach/unattach to a piece.
  107. jimmycuadra/pushing-hands
    bejeweled variant where you swap whole rows at a time.
  108. doowttam/game-off-2012
    unique fix-the-pattern game.
  109. sunetos/game-off-2012
    unclear body simulation game.
  110. dicksontse/game-off-2012
    snake, without the snake.
  111. imagentleman/hackris
    original, but pointless incorporation of cloning and pushing into a typing game.
  112. brooss/game-off-2012
    answer text-questions, and hang out in a chat room.



    Games after this point did not make it into the list, but maybe it's just me.



    Not-quite-games

    I don't agree that those entries count as "games", so I couldn't compare them fairly.

  113. timehome/game-off-2012
    a clone of robocode; which, as you know, is not a game, but an AI competition.
  114. pkukielka/radiance
    a psychedelic experience, to be sure, but is this a game?

    Annoying

    I could not stand playing those games for long enough to give them a fair comparison.

  115. mosowski/game-off-2012
    a 3D game designed to give you motion sickness? why??
  116. gnius/droplet
    avoid the obstacles. annoying alert bomb each time you die.
  117. abrie/game-off-2012
    unique finger-twitching game with intentionally irritating controls.
  118. ess/game-off-2012
    platformer with intentionally irritating controls. too hard and annoying for me.

    Buggy

    I could not play those games either.

  119. heisenbuggers/game-off-2012
    buggy boggle variant.
  120. Dlom/game-off-2012
    buggy duck shooter with a silly intro.
  121. TARGS/game-off-2012
    buggy bejeweled variant.
  122. CalPolyGameDevelopment/ettell
    mini-games
  123. shinriyo/game-off-2012
    3D choose-your-character and sink-into-the-ground?
  124. dawicorti/helping-pibot
    you're supposed to be able to create new pieces, but they get messed up.

    Technical difficulties

    I am not entirely sure that those games would also fail on your computer.

  125. Finjitzu/Archetype
    placeholder?
  126. nuclearwhales/push-the-box
    doesn't work, even with "chrome native client" enabled and relaunched?
  127. drabiter/magnet
    requires access to my computer to run?
  128. py8765/game-off-2012
    abandoned Draw Something clone?
  129. MS-game/game-off-2012
    maybe my Java player is too old?
  130. reedlabotz/game-off-2012
    the "Create new game" button doesn't do anything?
  131. OpenSismicos/game-off-2012
    applet requesting access to my computer?
  132. wprogLK/4thDimensionGame
    failed to run.
  133. jamescostian/game-off-2012
    got a blank page, but this is supposed to use a 3D library?
  134. BumbleBoks/game-off-2012
    unclear path-drawing game.
  135. prgnization/game-off-2012
    you're supposed to be able to chat (as a core game mechanic!), but the text field doesn't respond to my keyboard.
  136. elmariofredo/game-off-2012
    the video shows a working level, but I my character doesn't go past the zeroth level.
  137. ThatsAMorais/game-off-2012
    a strategy game, but the units don't move unpredicably?

    Incomplete

    I couldn't play those games until the end, which is sad, because some were very promising.

  138. publysher/game-off-2012
    incomplete text adventure about eating a steak.
  139. MikeRogers0/game-off-2012
    short platformer with no ending. interesting shoot-your-own-platforms mechanic.
  140. SoftlySplinter/game-off-2012
    a shoot-em-up without things to shoot.
  141. mhluska/game-off-2012
    incomplete olive bouncer.
  142. Annovean/game-off-2012
    incomplete osmosis clone.
  143. leereilly/follow-dem-game-off-forkers
    item collection game with no way to lose.
  144. ozh/alchemy
    doodle-god clone
  145. Blipjoy/game-off-2012
    incomplete UFO-themed object-dragging game?
  146. FluffyCode/game-off-2012
    octopus-in-the-desert-themed top-down shooter
  147. ImmaculateObsession/game-off-2012
    some level editor with no way to play?
  148. devNil/game-off-2012
    a so-called "inverted tower-defence" which you can win by repeatedly clicking the "warrior" button.
  149. EpicFailInc/game-off-2012
    destroy walls using bombs and lose HP for no reason.
  150. ihcsim/game-off-2012
    top-down shooter in which you can't win nor lose.
  151. gcoope/game-off-2012
    hang-glider inverse shoot-em-up with no way to win.
  152. vespertinegames/game-off-2012
    prototype tile-based movement.
  153. wskidmore/game-off-2012
    for a game in which you have "endless destructive powers", there sure aren't many things to destroy.
  154. jamestomasino/game-off-2012
    just a grid.
  155. freejosh/game-off-2012
    the engine for a platformer.
  156. dparnell/game-off-2012
    a maze, but you no way to explore it.

    Access denied

    Maybe it's just a server configuration issue?

  157. superally/game-off-2012
    access denied.
  158. DarkForestGames/game-off-2012
    403 forbidden.
  159. lazyeels/game-off-2012
    forbidden

    Abandoned

    Some people wrote down their game ideas, but never got around to implement them. Others picked a URL, but never uploaded anything there.

  160. strugee/game-off-2012
    abandoned placeholder.
  161. cmdkeen/game-off-2012
    abandoned game concept.
  162. Willshaw/game-off-2012
    abandoned game concept.
  163. Vbitz/game-off-2012
    placeholder.
  164. EvilSpaceHamster/game-off-2012
    page not found
  165. fabriceleal/game-off-2012
    abandoned placeholder
  166. CodingEffort/game-off-2012
    page not found
  167. Jorjon/game-off-2012
    page not found
  168. mbl111/game-off-2012
    placeholder
  169. matthewtole/game-off-2012
    404
  170. will3942/game-off-2012
    placeholder