Massive Multiplayer Recreational Programming Games

I've finally done it: 153 (out of 153) problems solved, first rank (out of more than 9000!) on 4clojure. Well, at the moment of writing, anyway.

It started as an attempt to justify an impulse purchase of the book called Programming Clojure.

Fiddling with the language and searching for examples of some decent clojure code online, I've come upon a link on a forum, tried to solve a couple of the first problems just for kicks... and got sucked in.

4clojure is a web-site where you get a small self-contained problem to solve, write a snippet of Clojure code, press the "Submit" button, see the unit tests go green, rejoice, rinse and repeat.

It's somewhat similar to Project Euler, except that it's focused on Clojure and is more interactive.

And somehow it turned out to be a lot of fun for such a generally boring activity.

I mean, most people would not be as motivated to solve these problems if it was a homework assignment. I am certain I would not.

At least, not in a way that you crave "to solve just one more before going to sleep" or are looking forward to "turn that tough one in once online".

Quite an amusing psychological phenomena.

My speculation is that one can find some parallels between this and some mechanics of massive (or not-so-massive) multiplayer online games. Those, that make it "fun". Thus the cheap "MMORPG" pun, see?

For example, let's take the "constant, tangible positive feedback from the user activities" (oh yes, that sounds boring, for sure... but the fun kinda comes from it)

In the case of 4clojure this kind feedback is present on different levels:

• The problems are mostly quite short, so generally it takes a limited amount of time to solve (and "turn in") each
• It is run "inside" the browser, in a sense that you type the code in, press the button and immediately see if your code does the right thing. Seeing the green bullet points when the test passes vs otherwise grey (or red) ones has also an interesting psychological effect.
• There is a "Top users" list, where you get the rank according to the amount of problems solved, and you can see your own entry slowly climbing upward with every problem that just has gone all green.
• After solving each problem you can see other users' solutions to it and compare with your own code. I found this to be an invaluable experience, since after trying and solving the problem yourself, you get much richer context for reading and understanding someone else's code. Quite often, the solutions by different people differ a lot. Quite enlightening.
• And probably the most important one: you constantly feel that you learn! The language, the algorithms, the ways to write (and not to write) elegant (and not-so-elegant) code.

There is no MMORPG without cheating, and we got it here... in a sense.

See, for every problem, the ultimate goal is to input a piece of Clojure code which would, when copy-pasted into the blanks inside the several predefined "test" expressions, all evaluate to true.

So let's say we have a problem that wants us to write a function that does a complex computation on an input string and returns some number.

There might be the test cases:

(= 42 (__ "Some string"))
(= 13 (__ "A different string"))
(= 17 (__ "Even different string"))

Whatever complex computation on those input strings the problem actually wants, you don't really need those for the test to actually pass:

#({\S 42, \A 13, \E 17} (first %))

will do well enough.

Instead of actually solving the problem (whatever it is), we are just using a look up table here.

Even more hilarious examples are, when for test cases of a kind:

(= false (__ (some-very-complex-expression1)))
(= true  (__ (some-very-complex-expression2)))
(= true  (__ (some-very-complex-expression3)))

one comes up with something like:

(fn [_] ([true false] (int (* 2 (Math/random)))))

...and then spams the "submit" button until the random permutation of results (in what is essentially a coin flip experiment) will match the desired sequence of true and false values.

Btw, can you tell what would be the probability that we get the "right" answer after, say, 10 "submit" button presses (uhm... sounds somehow familiar)?

What is amusing, that the boundaries of what can be called "cheating" here are actually fuzzy. It can be seen just as a custom set of rules, metagame in a sense, that is played, again, just for fun.

Another thing worth mentioning is that most of the content it the "game" is apparently a user content, something that has been a Holy Grail of the MMORPGs.

You can quite easily submit your own problem, which would get reviewed by the moderators and become the part of the game. Cool, isn't it?

But alright, no matter how great it is, there are still things that could've been better.

My personal list of issues (with hopefully constructive comments):

• The complexity of the tasks is graded via "trivial", "easy", "medium", "hard" (and they are sorted by the complexity). This rank is often not representative of the "actual" complexity (it's assigned by the author of the problem at the point when its initially typed in). Some kind of user voting for the complexity (and for that matter, maybe for the problem itself) could help.

• There are timeouts on how long for your code takes to execute. While it's a good thing in general, the actual timing apparently also includes e.g. the macro expansion, which for some reason can take insanely long (one of the examples is usage of "for" macro in some of the complex problems, which I ended up avoiding altogether). Granted, this looks more like a problem on the Clojail side (it is used to sandbox the code execution), so that's probably where it should be improved, in the first place.

• The unit test cases sometimes are boring, not representative and easily cheated. That's where the voting (and commenting) would possibly help as well.

• "Code golf" league, while cool, often makes people write incomprehensible code (as opposed to clean and elegant). I believe this is partially beacause of too simple "conciseness" metric. At the moment it's just the amount of characters minus whitespace and commas:

      (defn code-length [code]
        (count (remove #(or (Character/isWhitespace %)
                            (= % \,))
                       code)))
  

  This possibly could have been improved by e.g. not counting the comments, not taking the identifier length into account, counting forms rather than characters (and possibly the "complexity" of forms... some nestedness factor or something).

• User ranking system could have been more sofisticated. At the moment it's just the amount of problems solved. But ideally, it could also have taken the "quality" of the solutions into the account: running time (even though it's quite unclear how to measure it adequately), votes of other users for the solution, "proper" code golf metrics.

• The limited scope of the problems in the context of the Clojure language features. Most of the problems are solved via just sequence manipulations, not really involving things as macros (and DSLs), multi-methods, namespaces etc. I am not really sure how to tackle this one (aside from consciously submitting more problems on the poorly covered language features). Some of the limitations come from the approach of "copypasting the user's code snippet into the blanks inside the test expressions" itself. Maybe that could have been extended somehow.

But enough with the "complaining".

To sum up, it has been a great both educational and entertaining experience. There might just be something very promising about this way of learning things.

I believe people need more stuff like 4clojure.

Loot drop and other epic problems of probability theory

One day my old friend called me and asked if I could give a hand in solving some school math problems (he was trying to tutor his nephew).

Among the problems was:

The factory produces some parts. Given that from every 60 parts 12 are defective, find the probability that from 10 parts at least two are defective.

Frankly, the solution did not occur immediately at all - it's been a while since the student years.

What did occur to me immediately, though, is that something is wrong with the way people are usually taught those things at school. There are often troubles remembering them afterwards. Why?..

Apparently, one of the reasons is that the problems which students are asked to solve are usually plain boring.

Why would I care about those "defective parts", indeed?...

Now, the funny part is that it has nothing to do with the mathematical apparatus at hand (which is the thing we are supposed to learn): being abstract as it is, it can be applied to many practical problems. And some of them might appear more interesting than others, depending on the context.

For example, what about:

Two friends are playing World of Warcraft. They agreed to group for farming a boss, who drops a certain epic loot with a chance of 20%. What are the odds that after killing it 10 times both friends would get the desired epic gear?

See what I have done here?.. It is exactly the same problem. Except now it's better flavoured, and furthermore, it's actually a problem of practical interest to people playing WoW.

And something makes me feel that there are more young people playing WoW these days than those making defective parts at factories!

So, here's the (interactive) answer to the problem. Try entering different numbers and pressing the "Recompute" button (keep in mind that the code here does not attempt to be too robust with the boundary cases... also, values might be rounded, so 99.999999% will be shown as 100%, which is not correct):

With the loot drop chance of %, the odds of getting at least drop(s) after attempts are 0.012%.

It is computed by substituting values into a somewhat intimidating formula:

Here n is the total amount of boss kills, p is the loot drop chance and x is the minimal desired amount of drops we can get.

The mentioned article uses particular case of this formula, when x is 1 (i.e. when we want to know the chance that the item drops at least once):

Alright, but this is an answer, not a solution!

However, chances are that it is almost the implied solution to the original problem about the defective parts: the student is supposed to identify the Bernoulli process (AKA "repeated coin flipping"), remember that the number of successes in a given amount of trials has a binomial distribution, and use cumulative distribution function formula for that.

But this brings another problem with education: we are tought more about "what's" (facts and answers), than of "why's" (motivation and solutions). Resorting to just memoizing the formulas is not too reliable from the point of view of problem solving abilities.

So, let's try to unlearn all that again and start from the beginning.

Step 1

First, let's treat all our probabilities as being in the range [0, 1], not in percents (converting back and forward is just about multiplication/division by 100%).

One fundamental formula to consider is:

Here P(A) means "probability that event A happens", and P(not A) means "probability that event A does not happen".

The chance of loot drop is 0.2 (which corresponds to 20%). What is the chance that there will be no loot drop?

The answer is 0.8 (1 - 0.2, using the formula).

Step 2

The chance that two independent events A and B would happen both is:

The boss can drop the epic sword with 0.1 chance. What is the chance to kill the boss two times, and both times to get the sword?

The answer is 0.01 (0.1*0.1). We want both of the idependent events (sword drops) happen.

Step 3

One more basic formula from probability theory: if events A and B are mutually exclusive (either of them can happen, but not both together), then:

The boss can drop one of two items: an epic sword (0.1 chance) or an epic shield (0.2 chance). What is the chance to get either of them?

The answer, according to the formula, is 0.3 (0.1 + 0.2). The two possible loot drop scenarios are mutually exclusive.

This is a special case of the so-called addition law of probability.

Step 4

Back to the serial boss kills.

The boss can drop an epic sword with 0.2 chance. What is the chance for the two friends to kill the boss 10 times, and get the sword exactly twice, and do that during the last two kills?

Here's how this scenario does look like:

Using the knowledge from steps 1 and 2, we find that the answer is (0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.8)*(0.2)*(0.2), or in general form: We've got n events here, they are all independent, and should all happen together (thus we have a product of probabilities).

Step 4

The boss can drop an epic sword with 0.2 chance. What is the chance for the two friends to kill the boss 10 times, and get the sword exactly twice?

Notice that now we actually don't care if that loot necessarily drops exactly during the last two kills. As long as it manages to drop exactly twice during the total 10 kills - we're good. Which means there are more possible scenarios which satisfy our needs:

The total amount of such scenarios is C(n, k), which is called binomial coefficient (the number of distinct k-element subsets of n-sized set): We won't go into details of this particular formula this time, but here's a really nice and intuitive explanation.

Remembering the step 3, and the fact that all of the scenarios are mutually exclusive (if one scenario happens, another one can not happen anymore), and we want any of them happen (Scenario1 or Scenario2 or ...), the answer is:

This is so-called probability mass function of binomial distribution.

Step 5

In the original problem, we don't want the loot drop happen exactly twice. It's rather at least twice (indeed, I bet nobody would mind if the loot actually drops 2, 3 or even all 10 times, which is also theoretically possible).

But first let's look at a slightly modified problem:

Two friends are playing World of Warcraft. They agreed to group for farming a boss, who drops a certain epic loot with a chance of 0.2. What are the odds that after killing it 10 times the gear will drop less than 4 times?

"Less than 4 times" means: "exactly 3 times or exactly 2 times or exactly once or not at all".

So it's essentially a sum of formulas from the step 4:

There is a name for this one, it's called cumulative distribution function.

We are interested in the loot dropping "at least 2 times", not "less than 2 times", so simply take that formula and apply the step 1, giving us the final result:

Now this formula looks much less intimidating, and actually makes sense!

Isn't it amazing?..

The code

JavaScript function which computes the answer:

/** * Computes the chance that in given amount of attempts the loot would * drop at least desiredDrops times * @param {integer} attempts Total attempts at getting the loot dropped * @param {integer} desiredDrops The desired least amount of the actual loot drops * @param {number} dropChance Probability of the loot to drop */ function computeDesiredDropsChance(attempts, desiredDrops, dropChance) { return 1 - Probability.binomialCDF(desiredDrops - 1, attempts, dropChance); }

The probability helper functions:

var Probability = { /** * Computes the sum of function values over given integer range * @param {integer} i0 First index value * @param {integer} iN Last index value * @param {function(integer)} fn Function with values to sum up * @return {number} fn(i0) + fn(i0 + 1) + ... + fn(iN) */ sum: function (i0, iN, fn) { var res = 0; for (var i = i0; i <= iN; i++) { res += fn(i); } return res; }, /** * Computes the product of function values over given integer range * @param {integer} i0 First index value * @param {integer} iN Last index value * @param {function(integer)} fn Function with values to multiply * @return {number} fn(i0)*fn(i0 + 1)* ... *fn(iN) */ product: function (i0, iN, fn) { var res = 1; for (var i = i0; i <= iN; i++) { res *= fn(i); } return res; }, /** * Computes binomial coefficient (the number of distinct k-element * subsets of n-sized set). * * Note that we use the multiplicative formula, as opposed to the * standard n!/(k!(n-k)!) one,in order to improve robustness/efficiency. * (http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula) * @param {integer} k Subset size * @param {integer} n Set size * @return {number} The binomial coefficient, C(n, k) */ binomialCoefficient : function (k, n) { return Probability.product(1, k, function(i) { return (n - (k - i))/i; }); }, /** * Probability mass function for binomial distribution * http://en.wikipedia.org/wiki/Binomial_distribution * @param {integer} k Amount of successes * @param {integer} n Amount of trials * @param {number} p Probability of success * @return {number} Probability that amount of successes in Bernoulli * experiment with n trials is exactly k */ binomialDistribution : function (k, n, p) { return Probability.binomialCoefficient(k, n)* Math.pow(p, k)*Math.pow(1 - p, n - k); }, /** * Cumulative distribution function * http://en.wikipedia.org/wiki/Cumulative_distribution_function * @param {integer} x Upper bound value * @param {function(integer)} pFn Probability mass function * @return {number} Probability that random value with * probability mass function pFn is smaller or equal to x */ CDF: function (x, pFn) { return Probability.sum(0, x, pFn); }, /** * Cumulative distribution function for binomial distribution * @param {integer} x Upper bound value * @param {integer} n Amount of trials * @param {number} p Probability of success * @return {number} Probability that amount of successes * in Bernoulli experiment with n trials is less or equal to x */ binomialCDF : function (x, n, p) { return Probability.CDF(x, function(i) { return Probability.binomialDistribution(i, n, p); }); } }

Some final notes

While it's not too relevant to the main point here, we've still made a bunch of assumptions about how the loot dropping mechanism may work.

One of them is that we can use the Bernoulli process to model the loot drops.

In simple words, it means that outcome of the previous boss kills are not connected in any way to the outcomes of all the next boss kills.

It may be the case in WoW (after all, it's the most simple/efficient model from the implementation point of view), in practice the loot dropping code could be more complex than that, i.e. the history of the loot drops could have been taken into account.

For example, the code could make sure that those two friends would have 100% guarantee/satisfaction to get their loot after 10 boss kills.

But that's a totally different story.

P.S.

Just to be clear: the point is not about World of Warcraft making things interesting.
It's rather about how cognition is related to empathy, and how academia could exploit that.

9 of 10 guys are jerks. What is the chance that after dating 5 guys you'd meet the one who's not a jerk?