algorithm - TrueSkill 对接会实现

Question

您好!

我一直在关注有关 Microsoft TrueSkill 算法如何工作的指南 http://www.moserware.com/2010/03/computing-your-skill.html这些信息非常好，但没有说明应该如何进行玩家的实际选择(这很明显，因为我猜这对于每场比赛都是独一无二的)。

我的问题是我想出的所有算法看起来都非常复杂(时间复杂度高)。假设我有 2 支球队，每支球队应包含 4 名球员。如果我使用蛮力，我需要检查当前可用的所有组合的匹配质量(遵循 trueskill 算法)。如果要考虑很多参与者，这将导致大量迭代。

所以我想问你是否可以给我一些关于如何更聪明地做这件事的提示。也许您已经了解了一些解决此问题的信息？

Answer 1

我还使用 the TrueSkill algorithm in Python 实现了匹配服务我也担心同样的问题。

我的配对服务等待一段时间来收集配对请求。然后它根据用户的 TrueSkill μ 值对请求进行排序并进行划分。并再次等待。它找不到最佳匹配，但速度很快。这是一个伪代码:

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)

附注您需要大量用户和大型匹配池才能从评级系统和匹配服务中获益。