欧冠淘汰赛将在2月份开始，正好赶上中国农历新年，相信球迷们都很期待。我觉得对于欧冠来说欧冠淘汰赛对阵表，最重要的无疑是比赛本身。当然，另一个能让球迷们兴奋的就是淘汰赛的对决。计算欧冠淘汰赛各队之间的对决概率其实是一件很难的事情。作为一个纯种学生，我曾经考虑过计算对决概率的解析解（ ）。当然，我在计算过程中遇到了解不出来的问题（嗯，是的，我五年级的数学是体育老师教的，那就让他背锅吧，本泽马可以先休息一下），最后不得不放弃这种方法。每当找不到解析解的时候，一个自然的想法就是用数值解（ ）。本文讨论如何利用基于蒙特卡洛模拟的算法来获得数值解。
欧洲冠军联赛淘汰赛阶段概览
欧冠淘汰赛共有16支球队，小组第一出线的球队为：曼联（英超A组）、巴黎（法甲B组）、罗马（意甲C组）、巴塞罗那（西甲D组）、利物浦（英超E组）、曼城（英超F组）、贝西克塔斯（土超G组）、热刺（英超H组）。小组第二出线的球队为：巴塞尔（瑞超A组）、拜仁（德甲B组）、切尔西（英超C组）、尤文图斯（意甲D组）、塞维利亚（西甲E组）、顿涅茨克矿工（乌超F组）、波尔图（葡超G组）、皇马（西甲H组）。淘汰赛抽签规则大致如下：1、小组第一的球队与小组第一的球队对战； 2.同组球队之间互相避让（比如小组赛曼联不能和同组巴塞尔交手）；3.同一国家联赛的球队之间互相避让（比如巴萨可以和同为西甲的皇家马德里交手）。
我们的目标是计算一个8×8的矩阵，矩阵的元素对应两支球队匹配的概率，矩阵的行对应小组第一晋级的球队（曼联标记为1，巴黎标记为2，罗马标记为3，巴塞罗那标记为4，利物浦标记为5，曼城标记为6，贝西克塔斯标记为7，热刺标记为8），矩阵的列对应小组第二晋级的球队（同样，巴塞尔标记为1，拜仁标记为2欧冠淘汰赛对阵表，切尔西标记为3，尤文图斯标记为4，塞维利亚标记为5，顿涅茨克矿工标记为6，波尔图标记为7，皇马标记为8）。
抽签的具体流程是这样的：第一轮从小组第一的队伍中抽出一支队伍，然后再从其对应的可能的第二支队伍中抽出一支队伍（考虑到规则2、3中的回避条款），然后这两支队伍成为对手。第二轮对剩下的队伍重复上一步。理论上，这样八轮就可以完成我们的抽签了。是不是觉得很简单？妈妈再也不用担心我的数学了？你以为会玩王者荣耀的小学生都能算出这个概率吗？哈哈哈。其实陷阱还是挺多的。
陷阱
我们来看看这些陷阱。第一，虽然名义上是八轮比赛，但实际上七轮过后就已经确定了最终的对阵。因为七轮过后，小组第一和第二只剩下一支球队，所以一定是他们之间的比赛。第二，假设六轮过后，小组剩下的第一名球队是巴萨和贝西克塔斯，小组第二名球队是顿涅茨克矿工和皇马。其实也可以说六轮过后抽签就结束了。为什么呢？因为小组第一巴萨无法和皇马交手（避免同属一个国家联赛），所以只能和顿涅茨克矿工交手，由此可以推断出贝西克塔斯将和皇马交手。但问题是，在这种情况下，六轮过后抽签就结束了，那么有没有可能五轮过后就结束了，甚至四轮过后就结束了，或者至少提前确定了部分对阵呢？这个问题我们后面再讨论。第三，我们换个角度来看第二个陷阱，从小组第二的皇马角度，无法对阵巴萨（避免同属一个国家联赛），所以只能对阵贝西克塔斯，由此可以推断出巴萨将对阵顿涅茨克矿工。
你是不是觉得我很无聊？这个例子中的第二个和第三个陷阱本质上是一样的，有没有一种凑字数骗稿费的感觉？我要洗白自己了。 的确，在前面的例子中，第二个和第三个陷阱本质上是一样的，但是在更一般的情况下，两者并不一定是一样的。 我们举个例子，假设前两轮比赛结束后，我们的平局结果是巴黎vs皇马，贝西克塔斯vs拜仁。那么在这个例子中，我们来关注一下小组第二名切尔西的情况。由于存在同样的小组回避条款和同样的国家联赛回避条款，所以一开始可能的球队就只有巴黎、巴萨和贝西克塔斯。现在前两轮比赛已经抽到了巴黎和贝西克塔斯，那么可能的对手就只有巴萨了。 这种情况对应着我们的第三个陷阱，但与我们的第二个陷阱并不对应。
还有一个需要我们讨论的问题是，第二、第三个陷阱到底需要多少轮才会出现？答案是两轮。为什么呢？按照欧冠规则，同一个联赛中欧冠名额最多为3+1，其中三支球队直接进入欧冠小组赛，一支球队参加附加赛，如果附加赛夺冠，就可以参加小组赛（我为什么这会儿就想到阿森纳了，哈哈哈）。但如果联赛中还有一支球队在去年夺得了欧联杯冠军（去年的欧联杯冠军是英超球队曼联），那么他们今年也可以直接晋级欧冠小组赛。所以理论上一个联赛最多可以有五支球队参加欧冠小组赛，如果这五支球队都表现出色，小组出线，那么联赛中就有五支球队可以参加欧冠淘汰赛。如果其中四支球队是小组第一，而另一支球队是小组第二，或者其中四支球队是小组第二，而另一支球队是小组第一，那么唯一一支球队不仅需要避开同级联赛的四支球队，还需要避开同组的球队，所以他需要避开的球队有五支，而可以选择的球队只有三支。这个最极端的例子就发生在今年，切尔西是幸运儿。在这种最极端的情况下，切尔西的对阵很有可能会在两轮平局之后确定。
这个问题有好的一面也有坏的一面，坏的一面是由于问题的复杂性，我们的代码长度会变得更长；好的一面是我们已经考虑了最极端的情况，所以对于其他年份，我们只需要改变初始数据集，而不需要修改后续计算部分的任何代码。
计算对决概率的数值解
下面介绍如何使用蒙特卡洛模拟算法计算对决概率的数值解。第一步，我们先生成一个所有元素均为0的8×8矩阵。第二步，我们按照规则画出对决结果（即16支球队8场对决的结果）。若两队交手，则矩阵中对应元素加1；若两队不交手，则矩阵中对应元素保持不变。第三步，我们重复第二步，直至完成10万次蒙特卡洛模拟。第四步，我们将第三步得到的矩阵中各个元素的最终累加值除以蒙特卡洛模拟的次数，即10万次，即可得到我们的对决概率的数值解。
上面的操作中，编程最难的部分是第二步。我大致的编程思路是这样的。前两轮按照规则随机抽签（我们上面已经分析过，即使在最极端的情况下，前两轮也不会陷入第二、第三个陷阱）。从第三轮开始，我们先观察第一组中是否有任何一支球队会只有一个对手可供选择。如果有，就直接抽签；如果没有，那太好了，我们进入下一步。我们下一步是继续观察第二组中是否有任何一支球队会只有一个对手可供选择。如果有，就直接抽签；如果没有，那太好了，我们可以像前两轮一样在第三轮按照规则随机抽签（也就是在避免同组、同国家联赛的条件下）。第四轮到第七轮的抽签思路和第三轮是一样的。在所有情况下，第八轮的抽签是没有意义的，因为七轮过后比赛结果已经完全确定了。因此，我们根据前七轮的抽签结果，自然而然地推导出第八轮的抽签结果。我们的概率估计结果如下：
表 1：各队对阵概率
有些同学可能会问的一个问题是，你的结果可靠吗？我的回答是，绝对可靠。由于每次蒙特卡洛模拟都完美遵循IID假设，而且参数只有64个，所以我觉得进行10万次模拟有些浪费算力。但毕竟10万次模拟是学术圈的套路，所以我们就照着套路来吧。但如果一定要拿证据来回答，那我还是沿用学术圈的套路——置信区间。我进行了1000次实验，每个实验进行了10万次蒙特卡洛模拟。然后计算95%水平下的置信区间，以及99%水平下的置信区间。对应的结果如下：
表 2：概率的置信区间
图 A：95% 置信区间
B 组：99% 置信区间
我们可以看到结果中的置信区间非常窄，证明了我们估计结果的准确性。
另一种方法是看1000个实验的分位数结果。我们重点关注两组分位数结果。第一组是2.5百分位数和97.5百分位数（95%的数据结果包含在两者之间）。第二组是0.5百分位数和99.5百分位数（99%的数据结果包含在两者之间）。对应的结果如下：
表 3：概率百分位数
面板 A：2.5 至 97.5 百分位数
面板 B：0.5 至 99.5 百分位数
我们还可以看到结果范围相对较窄，这再次证明了我们估计结果的准确性。
还有一位同学看到我的结论后提出了疑问：你们的代码能处理热球吗？哈哈哈，不得不为他的机智点赞。就像我们经常在新闻里看到某支球队有欧足联教父一样，如果欧足联非要用热球作弊来操纵比赛结果，这个问题还是交给FBI去处理吧。
实际的最终比赛结果为：热刺vs尤文图斯、曼城vs巴塞尔、利物浦vs波尔图、曼联vs塞维利亚、巴黎vs皇马、罗马vs顿克塔尔、巴萨vs切尔西、贝西克塔斯vs拜仁。其中最令人期待的对决无疑是巴黎（球员包括内马尔，老板阿联酋埃米尔身价高达1万亿美元）vs皇马（C罗和贝尔身价都2亿，克罗斯是真正的中场大腿）和巴萨（锋线四人组违约金高达17亿欧元，可以说锋线四人组莽撞，后卫三人组稳如狗）vs切尔西（虽然科特迪瓦人刘德华没了，还有比利时人杨坤）。从我们模拟的概率可以看出，巴萨对阵切尔西的概率在40%左右，这个大概率事件终于成为了现实。巴黎对阵切尔西的概率同样不小，达到了30%，虽然巴黎避开了切尔西，但是遇到皇马显然运气更差。
比赛时间是26:45（凌晨2点45分），考虑到读者中有18岁以上的老人（Wei）（Qiu）（Mi），我给大家放上视频链接，链接里并没有直接展示最终结果，所以如果第二天中午起床看视频的话欧冠淘汰赛对阵表，实际效果和直播差不多，链接为：
我们来看看最新的赔率：曼城1比4（隐含夺冠概率为1/4）、拜仁1比5.5（隐含夺冠概率为1/5.5）、巴黎1比6（隐含夺冠概率为1/6）、巴塞罗那1比8.5（隐含夺冠概率为1/8.5）、皇马1比9（隐含夺冠概率为1/9）、曼联1比15（隐含夺冠概率为1/15）、利物浦1比15（隐含夺冠概率为1/15）、尤文图斯1比17（隐含夺冠概率为1/17）、热刺1比28（隐含夺冠概率为1/28）、切尔西1比34（隐含夺冠概率为1/34）。你知道我之前为什么形容切尔西倒霉了吧。另外我想说，夺冠的隐含概率加起来高达108.45%，也就是说庄家的佣金高达1/12左右，相比0.5%的交易成本，庄家有点太狠了。从另一个角度看，足球博彩参与者的效用函数明显是凸的，除非他们能操纵比赛，或者掌握重要的非公开信息。
最后，你应该感谢上帝。宇宙存在了137亿年，地球存在了46亿年，人类存在了500万年，但上帝却偏偏眷顾你和梅西，让他们处于同一个时代。
厦门大学金融系假足球迷丁杰
本文的代码网盘链接：
密码：midn
