Apr 25, 2011

Memylon: the language wars are over!

Meet my cat:
He's programming (and JavaScript in particular) illiterate, but likes to program anyway. And situation like this is perfectly fine, unless that code, which is written to learn things, goes into production. We all know that never happens, though. We do, right?..

Anyway, one day he wanted to play with Html5 canvas and make a small silly game or something.

And that's what he came up with (press "Start Game" to begin):


No canvas for you, sorry. Please use a proper browser.



This is a classical Memory game:
  • At the beginning all the cards are shown for a couple of seconds. Try to remember their positions!
  • Then click on two cards at time to flip them over.
  • If a matching pair is revealed, then those cards disappear.
  • But the cards flip back if they do not match, and this counts as a "miss".
  • The goal is to find all the matching pairs with the least amount of misses.
As you may have noticed, the cards are corresponding to different programming languages, thus the name of the game: Memylon (what cat does not love cheap puns?..)

The full source code to the game can be found on github.

The unsophisticated animal did not use any existing JavaScript libraries. He definitely should have, but sometimes reinventing a bicycle is so much fun (oh yeah, of course he did peek into the jQuery source a couple of times, to check what shape the wheels are there)!

And of course, please pardon the silly animal if it does not work in your browser. It seemed to in the latest Chrome, Opera, Firefox and Konqueror on Linux, as well as in Chrome, Opera, Firefox, Safari and IE9 on Windows (even though with Chrome on Linux the global alpha value on the canvas' context did not seem to affect text transparency... which might be a bug or again a result of illiteracy - go figure).

First thing he did is running GIMP and gathering a collection of programming language pics into an "atlas" image (it should be mentioned that all the language logos/trademarks belong to the corresponding authors/owners, and background image is a courtesy of Renaissance):


Of course, every programmer knows that one should start from the hardest things. Not from the ones which are the most fun!!!

But come on, he's just a cat.

After that the illiterate creature opened a text editor and typed in a pile of JavaScript code:

//  the main entry point 
window.onload = function () { 
    Memylon.init(); 
} 
 
//  the game module 
var Memylon = function() { 
    //  constants 
    var FRAME_TIME = 50, FLASH_TIME = 1000; 
    var CARD_W = 64, CARD_H = 60, CARDS_IN_ROW = 11, CARDS_NUM_VARIATIONS = 54; 
    var FLIP_TIME = 500, HIDE_TIME = 500, SHOW_TIME = 300; 
    //  variables 
    var cards  = [], anims = []; 
    var numCardsW = 6, numCardsH = 4; 
    var prevIdx = -1; 
    var numMisses = 0; 
    var canInteract = false; 
    var bgImage, cardsImage; 
    var context; 
 
    // the initialization function 
    function init() { 
        var canvas = Utils.$('gameArea'); 
        if (canvas && canvas.getContext) { 
            context = canvas.getContext('2d'); 
            Utils.$('restartGame').onclick = function () { 
                this.value = 'Restart'; 
                resetGame(); 
            }; 
            canvas.addEventListener('mousedown', function (e) { 
                    onMouseClick(e.clientX - canvas.offsetLeft, e.clientY - canvas.offsetTop); 
                }, false); 
            setInterval(updateBoard, FRAME_TIME); 
        } 
 
        bgImage = Utils.$("bg"); 
        cardsImage = Utils.$("cards"); 
    } 
    //  draw a card sprite on canvas 
    function drawCard(cardID, x, y, scaleX, scaleY) { 
        var glyphID = cardID > 0 ? cardID : 0; 
        var cx = x + CARD_W*(1 - scaleX)/2; 
        var cy = y + CARD_H*(1 - scaleY)/2; 
        var glyphX = (glyphID%CARDS_IN_ROW)*CARD_W; 
        var glyphY = Math.floor(glyphID/CARDS_IN_ROW)*CARD_H; 
 
        context.drawImage(cardsImage, 
            glyphX, glyphY, CARD_W, CARD_H, 
            cx, cy, CARD_W*scaleX, CARD_H*scaleY);    
    } 
    //  play a "flash cards" animation 
    function playFlashCards() { 
        canInteract = false; 
        for (var i in cards) { 
            var card = cards[i]; 
            var startDelay = (i%numCardsW + 1)*80; 
            var flashTime = FLASH_TIME*numCardsW; 
            card.anim = createAnim( 
                ['pose', startDelay, card.id], 
                ['flip', FLIP_TIME,  card.id], 
                ['pose', flashTime, -card.id], 
                ['flip', FLIP_TIME, -card.id]); 
        } 
        anims = [createAnim(['exec', numCardsW*80 + FLIP_TIME*2 + flashTime, 
            function () { canInteract = true; }])]; 
    } 
    //  game-specific animation update functions 
    var AnimFunctions = { 
        //  "draw static card" animation 
        pose : function(t, cardID, card) { 
            drawCard(cardID, card.x, card.y, 1, 1); 
        }, 
        //  "flip card" animation 
        flip : function(t, cardID, card) { 
            var scale = Math.cos(Math.PI*t); 
            var id = (scale > 0) ? cardID : -cardID; 
            drawCard(id, card.x, card.y, Math.abs(scale), 1); 
        }, 
        //  "dissolve card" animation 
        hide : function(t, cardID, card) { 
            if (t < 1) { 
                context.globalAlpha = 1 - t; 
                drawCard(cardID, card.x, card.y, 1, 1); 
                context.globalAlpha = 1; 
            } 
        }, 
        //  flying text animation 
        text : function (t, params) { 
            //  append missing parameters with defaults 
            Utils.setDefaults(params, {sizeFrom: 10, xFrom: 182, yFrom: 150, alphaFrom: 1, 
                font: 'Arial', bold: true, color: '#2222AA'}); 
            Utils.setDefaults(params, {sizeTo: params.sizeFrom, alphaTo: params.alphaFrom, 
                xTo: params.xFrom, yTo: params.yFrom}); 
            //  interpolate current text parameters 
            var size = Utils.lerp(params.sizeFrom, params.sizeTo, t); 
            var x = Utils.lerp(params.xFrom, params.xTo, t); 
            var y = Utils.lerp(params.yFrom, params.yTo, t); 
            var alpha = Utils.lerp(params.alphaFrom, params.alphaTo, t); 
 
            context.font         = (params.bold ? 'bold ' : '') + size + 'px ' + params.font; 
            context.fillStyle    = params.color; 
            context.textBaseline = 'middle'; 
            context.textAlign    = 'center'; 
            context.globalAlpha  = alpha; 
            context.fillText(params.text, x, y); 
            context.globalAlpha  = 1; 
        }, 
        //  executes a function at the end of animation period 
        exec : function(t, fn) { 
            if (t === 1) { 
                fn(); 
            } 
        }, 
        //  empty "spin doing nothing" animation 
        wait : function(t) { 
        } 
    }; 
    //  create an animation sequence 
    function createAnim() { 
        var arg, animType, duration, param; 
        var anim = new AnimSequence(); 
        for (var i = 0, nArg = arguments.length; i < nArg; i++) { 
            arg = arguments[i]; 
            animType = arg[0]; 
            duration = arg[1]; 
            param = arg[2]; 
            anim.add(AnimFunctions[animType], duration, param);    
        } 
        return anim; 
    } 
    //  play the "game is won" scene 
    function playFinalScene(cardID) { 
        var xCenter = 190; 
        anims = [ 
            createAnim(['wait', 1000], ['text', 500, { 
                text: 'This is it.', 
                color: '#5F5B60', alphaTo: 0.8, 
                yFrom: 30, xFrom: 400, xTo: xCenter, 
                sizeFrom: 50 
            }]), 
            createAnim(['wait', 2000], ['text', 700, { 
                text: 'the language wars', 
                color: '#735551', 
                yFrom: 75, xFrom: -200, xTo: xCenter, 
                sizeFrom: 30 
            }]), 
            createAnim(['wait', 2700], ['text', 1000, { 
                text: 'ARE OVER.', 
                color: '#81878C', 
                xFrom: xCenter, yTo: 120, 
                sizeFrom: 0, sizeTo: 40 
            }]), 
            createAnim(['wait', 5000], ['text', 1500, { 
                text: 'and the winner is...', 
                color: '#B2A89B', 
                xFrom: 500, xTo: xCenter, yFrom: 160, 
                sizeFrom: 30 
            }]), 
            createAnim(['wait', 6500], ['text', 5000, { 
                text: getCardInfo(cardID).name, 
                color: '#D91122', 
                xFrom: -100, xTo: xCenter, yFrom: 210, 
                sizeFrom: 0, sizeTo: 55 
            }]), 
            createAnim(['exec', 10000, function () { 
                var winnerURL = Utils.$('winnerURL'); 
                winnerURL.style.visibility = 'visible'; 
                winnerURL.href = getCardInfo(cardID).url; 
            }]) 
        ]; 
    } 
    //  process the "card clicked" event 
    function clickCard(cardIdx) { 
        var card = cards[cardIdx]; 
        if (prevIdx === -1) { 
            //  no cards are flipped yet 
            prevIdx = cardIdx; 
            card.anim = createAnim(['flip', FLIP_TIME, card.id]); 
            card.id = -card.id; 
        } else { 
            var prevCard = cards[prevIdx]; 
            if (Math.abs(card.id) === Math.abs(prevCard.id)) { 
                //  animation for the already flipped card: wait and dissolve 
                prevCard.anim = 
                    createAnim(['pose', FLIP_TIME, prevCard.id], 
                               ['hide', HIDE_TIME, prevCard.id]); 
                //  animation for the current card: flip and dissolve 
                card.anim = 
                    createAnim(['flip', FLIP_TIME, card.id], 
                               ['hide', HIDE_TIME, -card.id]); 
                //  animation of the flying card caption 
                anims = [createAnim(['text', 2000, { 
                    text: getCardInfo(card.id).name, 
                    alphaFrom: 1, alphaTo: 0.01, 
                    sizeFrom: 10, sizeTo: 300}], ['wait'])]; 
                var cardID = card.id; 
                prevCard.id = card.id = 0; 
                if (Utils.every(cards, function (card) { return (card.id === 0); })) { 
                    //  all matches are found, show the final scene animation 
                    playFinalScene(cardID); 
                } 
            } else { 
                //  animation for the already flipped card: wait and flip back  
                prevCard.anim = 
                    createAnim(['pose', FLIP_TIME + SHOW_TIME, prevCard.id], 
                               ['flip', FLIP_TIME,  prevCard.id], 
                               ['pose', undefined, -prevCard.id]);                    
                //  animation for the current card: flip, wait, flip back  
                card.anim = 
                    createAnim(['flip', FLIP_TIME,  card.id], 
                               ['pose', SHOW_TIME, -card.id], 
                               ['flip', FLIP_TIME, -card.id], 
                               ['pose', undefined,  card.id]); 
                prevCard.id = -prevCard.id; 
                setNumMisses(numMisses + 1); 
                } 
            prevIdx = -1; 
        } 
    } 
    //  reset the game board into the initial state 
    function resetGame() { 
        var ids, i, idx1, idx2; 
 
        //  generate a random subset of card variations 
        ids = []; 
        for (i = CARDS_NUM_VARIATIONS - 1; i >= 0; i--) ids[i] = i + 1; 
        Utils.shuffleArray(ids); 
        cards = []; 
 
        for (i = numCardsW*numCardsH - 1; i >= 0; i--) { 
            cards[i] = { 
                id   : -ids[Math.floor(i/2)], 
                anim : createAnim(['pose']) 
            } 
        } 
        Utils.shuffleArray(cards); 
 
        //  cache the card positions 
        for (i in cards) { 
            cards[i].x = (i%numCardsW)*CARD_W; 
            cards[i].y = Math.floor(i/numCardsW)*CARD_H; 
        } 
 
        setNumMisses(0); 
        anims = []; 
        prevIdx = -1; 
 
        playFlashCards(); 
        Utils.$('winnerURL').style.visibility = 'hidden'; 
    } 
    //  update/draw the game board 
    function updateBoard () { 
        var i; 
        context.drawImage(bgImage, 0, 0); 
        for (i in cards) { 
            var card = cards[i]; 
            card.anim && card.anim.update(FRAME_TIME, card); 
        }    
        for (i in anims) { 
            anims[i] && anims[i].update(FRAME_TIME); 
        }      
    } 
    //  update the miss counter 
    function setNumMisses(num) { 
        numMisses = num; 
        Utils.$('attemptsCounter').innerHTML = numMisses; 
    } 
    //  mouse click handler 
    function onMouseClick(x, y) { 
        var cardIdx = Math.floor(x/CARD_W) + numCardsW*Math.floor(y/CARD_H); 
        var card = cards[cardIdx]; 
        if (canInteract && card && (cardIdx !== prevIdx) && (card.id !== 0)) { 
            clickCard(cardIdx); 
        } 
    } 
    function getCardInfo(cardID) { 
        var cardIdx = Math.abs(cardID) - 1; 
        var a = Utils.$('links').children[cardIdx]; 
        return {name:a.innerHTML, url:a.href}; 
    } 
 
    return { 
        init : init 
    } 
}(); 
 
//  helper utility functions 
var Utils = { 
    //  randomly shuffles the array using Fisher-Yates algorithm 
    shuffleArray : function (arr) { 
        for (var i in arr) { 
            var k = Math.floor(Math.random()*i); 
            var val = arr[k]; 
            arr[k] = arr[i]; 
            arr[i] = val; 
        } 
    }, 
    //  returns true if all elements of the array satisfy the given predicate 
    every : function (arr, predicate) { 
        for (var i in arr) { 
            if (!predicate(arr[i])) return false; 
        } 
        return true; 
    }, 
    //  linear interpolation between a and b with factor t 
    lerp : function (a, b, t) { 
        return a + t*(b - a); 
    }, 
    //  append parameters in "params" with default values from "defaults" 
    setDefaults : function (params, defaults) { 
        for (var i in defaults) { 
            if (params[i] == undefined) { 
                params[i] = defaults[i]; 
            } 
        } 
    }, 
    //  poor man's jQuery 
    $ : function (id) { 
        return document.getElementById(id); 
    } 
} 
 
// a simple class representing a list of animations played in sequence 
AnimSequence = function () { 
    this.anims = []; 
    this.curAnim = 0; 
    this.curTime = 0; 
}; 
AnimSequence.prototype.add = function (updateFn, duration, startParam) { 
    this.anims.push({updateFn: updateFn, duration: duration, startParam: startParam}); 
}; 
AnimSequence.prototype.update = function (dt, updateParam) { 
    var anim = this.anims[this.curAnim]; 
    this.curTime += dt; 
    if (anim.duration && this.curTime >= anim.duration) { 
        anim.updateFn(1, anim.startParam, updateParam); 
        if (this.curAnim < this.anims.length - 1) { 
            this.curTime = 0; 
            this.curAnim++; 
        } 
    } else { 
        anim.updateFn(anim.duration && this.curTime/anim.duration, 
            anim.startParam, updateParam); 
    } 
}; 


That's what happens when you give a keyboard to a cat.

Of course, the cat ran the program through JSLint, and it hurt his feelings.

And that was it.


Apr 15, 2011

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?