tadhg.com
tadhg.com
 

Coding and Concepts: Tiebreakers

23:56 Mon 04 Feb 2008. Updated: 08:56 05 Feb 2008
[, , ]

While working on the tournament runner application that’s part of the ongoing rewrite of sfmagic.org, I encountered a problem which I think is indicative of how important ways of viewing problems are for coming up with solutions, especially in programming.

One of the problems I’m trying to solve is tiebreaker calculation. If players have the same match record after a draft tournament is over, we use tiebreakers based on data other than their match record to determine ranking. After score (which is essentially match record where a win is worth 3 and a draw is worth 1), the tiebreakers are:
opponent match win percentage (AKA ‘strength of schedule’)
game win percentage
opponent game win percentage
opponent opponent match win percentage
opponent opponent game win percentage

Often only the first of these is necessary, and it’s rare to have to go past game win percentage—but it does happen, and it’s a pain when it does. Since computers can do math of this kind rather easily, it makes sense that the tournament runner should handle it.

Calculating the individual tiebreakers themselves is quite easy. What turned out to be more interesting was how to apply them in order once they were calculated.

So I had player objects (dictionaries), each with a key for each tiebreaker, and a value for that key. The player objects were in an array, and JavaScript allows arbitrary functions to be passed to Array.sort(), so I just had to write the comparison function, which takes two objects at a time for comparison.

The way you apply tiebreakers as a human being is simple: you check the first one, and if it doesn’t work—that is, if it’s a tie—you move onto the next one. This is how I conceptualized the problem, and this led directly to my first embarrassing but functional try at it (the comments below were in the original code):

function sortRanks(p1, p2) {
    var better = -1,  worse = 1, s = 'score';
    var omp = 'opponent_match_percentage', gwp = 'game_win_percentage', ogwp = 'opponent_game_win_percentage';
    var oomp = 'opponent_opponent_match_win_percentage', oogwp = 'opponent_opponent_game_win_percentage';
    
    /* This is just horribly filthy: */
    if (p1[s] == p2[s]) {
        if (p1[omp] == p2[omp]) {
            if (p1[gwp] == p2[gwp]) {
                if (p1[ogwp] == p2[ogwp]) {
                    if (p1[oomp] == p2[oomp]) {
                        if (p1[oogwp] == p2[oogwp]) {
                            return -1; //this is random...
                        } else {
                            return (p1[oogwp] > p2[oogwp]) ? better : worse;
                        }
                    } else {
                        return (p1[oomp] > p2[oomp]) ? better : worse;
                    }
                } else {
                    return (p1[ogwp] > p2[ogwp]) ? better : worse;
                }
            } else {
                return (p1[gwp] > p2[gwp]) ? better : worse;
            }
        } else {
            return (p1[omp] > p2[omp]) ? better : worse;
        }
    } else {
        return (p1[s] > p2[s]) ? better : worse;
    }
}

The better and worse variables provide an easy way to switch between ascending and descending sorts. The other variables are ways to not repeat the full string for each tiebreaker, even though that only saves one instance for each.

Obviously, the real horror here is the six nested if/else loops. It was late and I knew it was wrong (even though I knew it would work), so I went with it, and it worked.

Before I went to bed, though, I couldn’t bear to leave it as it was, and I changed it to the following less readable but also less horrific version:

function sortRanks(p1, p2) {
    var better = -1,  worse = 1, s = 'score';
    var omp = 'opponent_match_percentage', gwp = 'game_win_percentage', ogwp = 'opponent_game_win_percentage';
    var oomp = 'opponent_opponent_match_win_percentage', oogwp = 'opponent_opponent_game_win_percentage';
    
    function s_score() { return (p1[s] == p2[s]) ? s_omp() : ((p1[s] > p2[s]) ? better : worse)};
    function s_omp() { return (p1[omp] == p2[omp]) ? s_gwp() : ((p1[omp] > p2[omp]) ? better : worse)};
    function s_gwp() { return (p1[gwp] == p2[gwp]) ? s_ogwp() : ((p1[gwp] > p2[gwp]) ? better : worse)};
    function s_ogwp() { return (p1[ogwp] == p2[ogwp]) ? s_oomp() : ((p1[ogwp] > p2[ogwp]) ? better : worse)};
    function s_oomp() { return (p1[oomp] == p2[oomp]) ? s_oogwp() : ((p1[oomp] > p2[oomp]) ? better : worse)};
    function s_oogwp() { return (p1[oogwp] == p2[oogwp]) ? better : ((p1[oogwp] > p2[oogwp]) ? better : worse)};
    return s_score();

Here, it’s the same conceptual approach: go through each tiebreaker, and if it’s a tie, go to the next one. Using nested ternary operators instead of explicit if/else statements. But at least I would only have to move a line and change a couple of characters if the order changed.

The order of tiebreakers is very unlikely to change, and the above function worked, but it still bothered me, and I was sure there had to be better solutions.

After all, application of tiebreakers in this way was essentially the same as a multi-column sort, and there had to be better ways to do those—I just didn’t happen to know any.

This evening I mentioned the problem to my brother, and when I told him it was the same as a multi-column sort, he mentioned that some of the methods for dealing with those could be a little strange, and that one approach was to add the ‘columns’ up.

At that point, the proverbial lightbulb flashed, and I knew how to approach the problem the right way.

Instead of doing it the ‘human’ way and only going to the next tiebreaker if the current one fails, the way to approach it in code (where math is very, very cheap) is simply to turn each set of tiebreakers into a number and then compare the numbers:

function sortRanks(p1, p2) {
    var breakOrder = ['score', 'opponent_match_percentage', 'game_win_percentage', 'opponent_game_win_percentage', 'opponent_opponent_match_win_percentage', 'opponent_opponent_game_win_percentage'];
    
    function getNumber(p) {
        var array = [];
        for (i in breakOrder) {
            array.push(p[breakOrder[i]].toString().replace('.',''));
        }
        return (array.join('').charAt(0)==0) ? parseInt(array.join('').slice(1)) : parseInt(array.join(''));
    }
    
    return (getNumber(p1) > getNumber(p2)) ? -1 : 1;
}

breakOrder provides a way both to easily change the order of the tiebreakers (even though that’s likely to be unnecessary in practice, it’s the right approach) and to make the code easier to understand later.

The final line is a simple ternary expression, comparing the numbers for the two players. The real core is in getNumber.

It takes a player object as an argument. That object has a number of properties (keys), many of which we’re uninterested in. After creating an array to hold the numbers in, iterate through breakOrder (which keeps the order as originally defined), adding the value of the corresponding property in the player object to the array after the value has been converted to a string and stripped of its decimal point. Doing this for each value in breakOrder creates an array with a bunch of strings in it which would provide the tiebreaker number if you just joined the whole thing together. So, join the whole thing together, using a ternary expression to remove a leading zero if there is one, then parse the result as an integer and pass it as the return value.

10 lines, about the same as the function-happy version I had last night, but a much better 10.

I’m sure there are other ways to approach the same problem, and perhaps some that are incomparably better than what I came up with. However, I still think my newer version is far better than the original, and the only reason I got there is because I got halfway to the right conceptualization by seeing it could be a multi-column sort rather than a series of decisions, and then my brother got me the rest of the way by pointing out how some other programmers have approached the same problem.

The code itself was relatively easy in both cases, where by “code” I mean the vocabulary and grammar required to express the concept. The conceptual difference itself was the tricky part, and despite the triviality of the problem (multi-column sorts are hardly something new, and are probably familiar to most Computer Science undergrads) I think this illuminates part of the reason why programming can be interesting, challenging, and sometimes maddening.

6 Responses to “Coding and Concepts: Tiebreakers”

  1. Lev Says:

    Beautiful! A case study in the process of code goodification.

  2. JC Says:

    There are a couple of potential problems that I can see.

    You’re generating a large number by performing string operations on OMP, GWP, OGWP, OOMWP, OOGWP, any of which can be 100, which will sort incorrectly. Any of those numbers can also be a single digit. Using that algorithum, a score of [6, 100, 9] (61,009) will score lower than [6, 99, 10] (69,910). You’ll also have similar problems with number of decimal places. Oops.

    The “(array.join(”).charAt(0)==0)” is just a kludge for working with a string that’s not a number. Why not just work with numbers to begin with? Or if you prefer, just perform an alphanumeric sort.

  3. Tadhg Says:

    Lev: Thanks!

    JC: I should have made clear that the incoming values are all three-decimal-point numbers, from 0.000 to 1.000, so the comparisons will work correctly.

    The elimination of the leading zero is definitely a kludge, and should probably be replaced with

    return Number(array.join(''));
    

    which appears to do the right thing.

    However, you’re right that it would be better to work with numbers entirely, eliminating the concatenation approach. Maybe something like:

    function sortRanks(p1, p2) {
        var breakOrder = ['score', 'opponent_match_percentage', 'game_win_percentage', 'opponent_game_win_percentage', 'opponent_opponent_match_win_percentage', 'opponent_opponent_game_win_percentage'];
    
        function getNumber(p) {
            var num = 0;
            for (i in breakOrder) {
                num = num + ((p[breakOrder[i]] * 1000) * Math.pow(10,(breakOrder.length-i)));
            }
            return num
        }
    
        return (getNumber(p1) > getNumber(p2)) ? -1 : 1;
    }
    

    If that works (I haven’t tested it), I’ll probably switch to it, as it looks like a cleaner method. Thanks for the comments!

  4. JC Says:

    Nice job. One more trick – The comparator function can simply be “return getNumber(p2) – getNumber(p1)”. Array.sort only cares if the return value is positive or negative. Hope to see it in action soon, perhaps on Lev’s or Seth’s iPhone.

  5. Phil Says:

    What was wrong with the logic in the first one? The problem was the code duplication, which can be fixed on its own with the breakOrder array you ended up using. The process was efficient and easy to understand, so I don’t see why the rest needed changing. Wouldn’t something like this work?

    function sortRanks(p1, p2) {
    var breakOrder = ['score', 'opponent_match_percentage', 'game_win_percentage', 'opponent_game_win_percentage', 'opponent_opponent_match_win_percentage', 'opponent_opponent_game_win_percentage'];
    
    for (i in breakOrder) {
       if (p1[breakOrder[i]] != p2[breakOrder[i]) {
            return ((p1[breakOrder[i]] > p2[breakOrder[i]]) ? -1 : 1);
       }
    }
    
    return -1; //tie
    }
    
  6. Tadhg Says:

    Phil: Ha! You appear to be right, but the breakOrder array was something I came up with after already going down the path of treating the values as one big number, so I never thought of revisiting the step-by-step check for equality. I’ll have to try out that approach, as it definitely looks more efficient (if less fun) than my latest version. It does kind of undermine some of the points in this blog post, though…

Leave a Reply