欧冠(欧联)小组赛抽签及其模拟计算

本赛季的欧洲冠军联赛和欧洲联赛小组赛抽签仪式分别于周四周五在摩纳哥举行。抽签前一天,各国球队经过残酷的晋级淘汰赛,得以拿到欧战的最终门票之时,各队球迷便开始分析本队可能遇到的对手,看热闹不嫌事儿大的中立球迷则数着“死亡之组”的可能性。那么问题来了,怎样用程序来模拟这样一个抽签过程呢?

抽签规则

首先来看一下欧冠联赛的抽签规则。(欧洲联赛与此大致相同)

小组赛共有32支球队,抽签之前将所有球队分成四档,每档的八支球队均分到A~H八个小组。今年的新规,第一档球队包含欧冠卫冕冠军,以及2014年欧足联国家(准确的说法是足协,因为一个国家可能有多个足球协会,如英国)积分排名前7位的足协下属顶级联赛冠军。由于欧冠冠军巴塞罗那同时也是当年西甲(西班牙国家积分第一)的冠军,因此积分第八荷兰的联赛冠军埃因霍温得以进入第一档。除第一档外,剩余球队按照抽签时的欧足联俱乐部积分[1]排名分档,积分反映了球队在欧洲的竞争力。

抽签时先抽第一档球队,待第一档球队全部分配完毕,再抽第二档球队,依次类推。每当抽出一支球队,要先计算它可能被分配的小组,然后从这些小组中随机抽取,决定该队的去向。问题的复杂便在于如何计算球队可能的去向,因为欧足联设定了许多条抽签回避原则。

  • 同一足协下属的球队不能同组。
  • A~D组和E~H组的比赛分别在周二和周三举行,为了方便各国球迷观看比赛,保证电视转播收视率最大化,各国球队应当均匀分布在上下半区,例如英格兰的四支球队必须有两支在A~D组,两支在E~H组。
  • 此外西班牙的皇家马德里和巴塞罗那拥有最高的收视率,它们也不能在同一半区。
  • 由于乌克兰内战,乌克兰与俄罗斯球队不会分在一组。

最复杂的规则当属转播权回避原则,它大大减少了可能出现的分组数量。随着抽签的进行,某些球队虽然没被抽出,但它们的位置却已经固定,没有更多的可能了。例如当天抽签时塞维利亚遇到的情况。下表为已经抽出的球队国家分布。

A B C D E F G H
法国 荷兰 葡萄牙 意大利 西班牙 德国 英格兰 俄罗斯
西班牙 英格兰 西班牙 英格兰 德国 英格兰 葡萄牙 西班牙
俄罗斯 希腊

此时第三档中抽出西班牙球队塞维利亚。根据同国回避原则,它可以去D组或G组,然而现场屏幕显示塞维利亚只能去D组。原因何在?此时第三档剩下的五支球队中,两支来自乌克兰,土耳其、意大利、法国各一支。土耳其总共只有一支球队进入欧冠,不需要考虑转播权原则,但是另外几支球队需要。由于上半区已经有意大利和法国球队,那么剩余的意大利和法国球队必然在下半区;乌克兰的两支球队也要分开。这样下半区就没有塞维利亚的位置了,它只能去上半区的D组。

模拟程序

尝试用python写抽签的模拟程序。第一版的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
A={'Barcelona':'ESP','Chelsea':'ENG','Bayern Munich':'GER','Juventus':'ITA', 'Benfica':'POR','Paris Saint-Germain':'FRA','Zenit Saint Petersburg':'RUS','PSV Eindhoven':'NED'}
B={'Real Madrid':'ESP','Atletico Madrid':'ESP','Porto':'POR','Arsenal':'ENG','Manchester United':'ENG','Valencia':'ESP','Bayer Leverkusen':'GER','Manchester City':'ENG'}
C={'Shakhtar Donetsk':'UKR','Sevilla':'ESP','Lyon':'FRA','Dynamo Kyiv':'UKR','Olympiacos':'GRE','CSKA Moscow':'RUS','Galatasaray':'TUR','Roma':'ITA'}
D={'BATE Borisov':'BYR','Borussia Monchengladbach':'GER','Wolfsburg':'GER','Dinamo Zagreb':'CRO','Maccabi Tel Aviv':'ISR','Gent':'BEL','Malmo FF':'SWE','Astana':'KAZ'}
teams=[A,B,C,D]
from random import choice
import copy
result=[]
alpha=list('ABCDEFGH')
def ucl_draw(teams, result):
pot=[]
nat=[]
teams_new=copy.deepcopy(teams)
if teams[0]:
for j in range(0,4):
selection=choice(teams[j].keys())
pot.append(selection)
nat.append(teams[j][selection])
del teams_new[j][selection]
if len(set(nat)) == 4 and ( 'RUS' not in nat or 'UKR' not in nat):
ucl_draw(teams_new, result)
result.append(pot)
else:
ucl_draw(teams, result)
ucl_draw(teams, result)
print '==========================='
for i in range(0,8):
print 'Group '+alpha[i]+': '
print ', '.join(result[i])
print '==========================='

这个版本没有考虑转播原则,因为我最初的目的只是想看看某个特定的球队可能的对手,代码里只设置了同国回避和俄乌回避,也没有按照标准的流程设计程序。即使这样也无法避免死签,因为只排除了当下不可能的选项,而没有更深一步考虑,如果遇到塞维利亚那样的问题,它是无能为力的。更不要说复杂的转播原则了。

为了让程序更加完善,必须提前排除那些不可能的选项,就像下棋时要考虑未来许多步的走法一样。自然,可以考虑弈棋程序里常用的搜索算法,例如深度优先搜索。当抽出某一个球队时,搜索可能进入的小组,顺次搜索下去,直到出现符合规则的小组时为止。然而程序的计算量可能会非常大。每一档球队可能的排列有$ 8! = 40320 $种,四档球队全部排列的数量十分巨大,必须对程序加以简化。

  • 第一档球队抽签无需进行搜索,因为它们没有来自相同国家的。
  • 由于欧冠预选赛将冠军组和非冠军组分开,第四档球队大多来自足球小国或弱国,一个国家只有一支球队,不用考虑复杂的回避原则,可以不进入搜索程序,因此搜索集中在二三档抽签中。
  • 执行搜索前可以先根据较简单的回避原则排除一些明显不可能的选项,还以塞维利亚为例,可以明显排除同国球队所在的小组。
  • 第二档球队是否需要加入搜索程序,目前没想到严密的方法证明,似乎简单的排除就够了,出现死签的概率很低。

具体程序还没写。每一届欧冠的参赛球队和分档不同,程序中加入的回避条件也会有些许差别,上面提到的简化原则也可能需要增添。距离下一年的抽签还早,就先拖延一阵子吧。

关于抽签是否公平的思考

前文提到今年的新政,第一档球队由各联赛冠军组成,而不是与二三四档一样按照积分排序。于是有些一档球队实力要弱于二档球队,如荷兰的埃因霍温、俄罗斯的圣彼得堡泽尼特。这就使得某些二档强队与一档强队分到一起,构成“死亡之组”,比如今年的皇家马德里与巴黎圣日耳曼。即使两支强队同时出线,在淘汰赛抽签中,小组第二要遭遇其他小组的第一,形势仍然很不利。而任何超级强队的提前出局,都降低了比赛的观赏性,减少观赛球迷的数量。

遍历所有满足欧足联规则的分组结果,可以计算出某球队与其他球队相遇的概率。直觉上,球队与另外一档所有球队碰面并不是等可能的,即使排除那些需要回避的球队,也未必是等可能的。这是不是有损公平原则呢?

(至少从条件概率角度,球队进入各个小组的概率是不等的。例如周四的现场抽签在第二档球队全部抽出以后,莫斯科中央陆军进入A~D四个小组的概率分别是0.308,0.192,0.308,0.192。)

通过模拟抽签过程,还可以计算出在这一抽签流程中某球队与其他球队相遇的概率。它是否与上一段中通过遍历得到的概率值相等?直觉上,这个问题的答案应该是肯定的,但不容易证明。因为抽签中存在回避原则,使这个问题变得异常复杂,即使每个签位是随机抽取的,也无法保证所有的结果是均匀的。

在研究这个问题的过程中发现了一篇分析2014年巴西世界杯抽签的论文[2],认为抽签存在不公平、不平衡、分布不均匀等现象。然而足球的世界充满了经济和政治考量,竞技水准往往不是决定性的因素。假如世界杯只取世界前32位球队参加比赛的话,亚洲将没有球队入选,这公平吗?何况用于评定竞技水准的参数如积分系统也不是特别完善。



  1. 参见欧足联积分系统

  2. Guyon, Julien. “Rethinking the FIFA World Cup Final Draw.” SSRN Scholarly Paper. Rochester, NY: Social Science Research Network, December 12, 2014.