如何实现瑞士轮匹配算法

2020 年时想的问题, 一直搁着. 今天突然想起来了.

瑞士轮编排通常要满足这些约束:

匹配过的两人不再重遇 (硬规则)
同分或近分者优先匹配
先后手尽量均衡 (棋类: 保证选手执黑 / 执白次数大致相等)
满足上述条件后适度随机 (部分严肃比赛不做随机)

要找到一组同时满足上述约束的匹配并不 trivial. 一种朴素做法是按经验法则先构造一组匹配, 再检查是否满足约束, 不满足就回溯重试 (trial and error). 早年 FIDE (国际棋联) 的裁判就是这样手工编排的. 这种启发式搜索的复杂度已经很高; 若改为暴力枚举所有可能的匹配再随机抽, 由于匹配数量随人数呈阶乘级增长, 更不可行. 因此需要更高效的算法求解.

引入图论

1990 年, Snjólfur Ólafsson 在论文 Weighted Matching in Chess Tournaments 中首次把瑞士轮编排 formulate 为图论里的优化问题: 把各项匹配约束转化为边上的权重, 再用现成的图论算法求解.

建模方式:

节点: 每个选手对应图中的一个节点 $v \in V$.
边: 若选手 $i$ 与选手 $j$ 尚未对局, 则在 $v_i$ 与 $v_j$ 之间连一条边 $e_{i,j}$.
权重: 为每条边赋予实数值 $w_{i,j}$, 表示这对匹配的 “理想程度”.

优化目标: 找一个匹配 $M$: 即若干条边的集合, 其中任意两条边不共享节点. 对应到编排上, 每条边就是一场对局, 每个选手恰好出现在一条边上 (或轮空), 所以一个匹配恰好给出本轮的全部对局方案. 目标是在所有匹配中使总权重最大:

\[\max_M \sum_{(i,j) \in M} w_{i,j}\]

这就是经典的 一般图最大权重匹配 问题; 标准解法是 Jack Edmonds 的 开花算法 (Blossom Algorithm): Edmonds 证明了该问题可在多项式时间内求解并给出构造性算法, 足以支撑大规模赛事的实时编排.

权重设计

下面的权重设计并非 Ólafsson 原文, 而是按文首约束做的简化示例. 实际系统中约束与权重构造方式可以千差万别.

权重 $w_{i,j}$ 可以构造如下 (仅做教学示例):

\[w_{i,j} = w_{\text{score}} + w_{\text{color}} + w_{\text{random}}\]

积分项 ($w_{\text{score}}$) 同分匹配优先: 同分选手间该项权重大, 分差大则权重小甚至不连边 (视作 $-\infty$). 该项通常比其他项大至少一个数量级, 以压过其余因素.
颜色平衡项 ($w_{\text{color}}$): 记 $\text{color_diff}_i$ 为选手 $i$ 执黑次数减执白次数. 若 $i$ 与 $j$ 的 $\text{color_diff}$ 一正一负、代数和接近 0, 则赋予更高权重.
随机项 ($w_{\text{random}}$): 在权重末位加一个随机小数, 使在其他条件相同时匹配结果带随机性.

极简代码示例

下面用 Python 做一个最小可跑示意 (奇数人可以加个虚拟节点表示轮空):

import networkx as nx
import random


def pair_round(players: list[dict]) -> set[tuple[str, str]]:
    G = nx.Graph()
    n = len(players)

    for i in range(n):
        for j in range(i + 1, n):
            p1, p2 = players[i], players[j]

            # 不能重复对局
            if p2['id'] in p1['opponent_ids']:
                continue

            # 1. 积分权重 (同分匹配优先级最高)
            score_diff = abs(p1['points'] - p2['points'])
            w_points = 10000 * (1 - score_diff)

            # 2. 颜色平衡权重 (cd 一正一负为理想匹配)
            w_cd = 100 * (2 - abs(p1['cd'] + p2['cd']))

            # 3. 随机扰动
            w_random = random.random()

            total_weight = w_points + w_cd + w_random
            G.add_edge(p1['id'], p2['id'], weight=total_weight)

    # 调用 Blossom 算法求最大权匹配
    matching = nx.max_weight_matching(G, maxcardinality=True)
    return matching


mock_players = [
    {'id': 'A', 'points': 1, 'opponent_ids': {'B'}, 'cd': 1},
    {'id': 'B', 'points': 0, 'opponent_ids': {'A'}, 'cd': -1},
    {'id': 'C', 'points': 1, 'opponent_ids': {'D'}, 'cd': 1},
    {'id': 'D', 'points': 0, 'opponent_ids': {'C'}, 'cd': -1},
    {'id': 'E', 'points': 0, 'opponent_ids': {'F'}, 'cd': 1},
    {'id': 'F', 'points': 1, 'opponent_ids': {'E'}, 'cd': -1},
    {'id': 'G', 'points': 0.5, 'opponent_ids': {'H'}, 'cd': 1},
    {'id': 'H', 'points': 0.5, 'opponent_ids': {'G'}, 'cd': -1},
]

pairings = pair_round(mock_players)
for p1_id, p2_id in pairings:
    p1 = next(p for p in mock_players if p['id'] == p1_id)
    p2 = next(p for p in mock_players if p['id'] == p2_id)
    print(f"对局: {p1_id} ({p1['points']} 分) vs {p2_id} ({p2['points']} 分)")

其他现成的简单实现可见 PyPair 库. 更成熟的实现可以参考 bbpPairings. 国际象棋比赛采用荷兰制, 约束更多更加复杂. 新的论文讨论的也是如何设计权重函数.