TrueSkill Matchmaking Implementation

algorithm

Solution

I also implemented a matchmaking service with the TrueSkill algorithm in Python and I worried about same issue.

My matchmaking service waits to collect match requests for a while. Then it sorts requests by user's TrueSkill μ value and devides them. And waits again. It cannot find best match but it is fast. Here's a pseudo code:

class Matchmaker(object):

    def matchmaking(self):
        sorted_pool = sorted(self.pool.itervalues(), key=by_rating)
        matches, self.pool = divide_uniformly(sorted_pool, expectation, minimum)
        return matches

    def run(self):
        while self.should_match():
            for match in self.matchmaking():
                if quality(match) < 0.5:
                    cancel(match)
                else:
                    succeed(match)
            time.sleep(self.interval)

p.s. You would need lots of users and a large match pool to get a benefit of rating system and matchmaking service.

Problem

Hello! I was following this guide about how the Microsoft TrueSkill algorithm works http://www.moserware.com/2010/03/computing-your-skill.html The information is really good but leaves out how the actual selection of players should be done (which is obvious as this is unique for each game I guess). My problem is that all algorithms that I come up with seems pretty complex (high time-complexity). Lets say I got 2 teams that should contain 4 players each. If I go brute force I need to check the match quality (following the trueskill algorithm) for all combinations that is currently available. This will lead to a huge number of iterations if there are a lot of players to take into account. So I am asking you if you can give me any hints about how to do it smarter. Maybe you have stepped upon some information addressing this problem?

Original source