YONのドバトブログ

YONの土鳩ブログ

ゲーム好きの鳩"YON"がツイッターでは言い切れないことについて書き連ねるブログ

ダブルエリミネーション方式のトーナメント大会は、どの程度適切な順位付けができるか

この記事では、トーナメント大会を行う形式の一つである「ダブルエリミネーション方式」(ダブルイリミネーションとも)が、通常のトーナメント方式に比べて、どの程度適切な順位付けをできるかについて書く。

なお、この記事は寝椅子氏の企画であるスマブラAdventCalendar2020に参加している。リンク先の他のブログ記事も是非読んでみてほしい。

 

ダブルエリミネーションは
シングルエリミネーションの問題を緩和する

多くの競技で採用されている普通のトーナメント戦は、1敗した時点で順位が確定する。この形式をシングルエリミネーションと呼ぶ。シングルエリミネーションは順位が大雑把な上に組合せ運の影響が非常に大きく、たとえば2位相当の実力を持つプレイヤーでも、運悪く初戦で1位相当のプレイヤーと当たった場合、即座に最下位敗退が確定する。さらに、準優勝者が本当に2位相当の実力である確率は、たとえば64人トーナメントの場合32/63しかない。*1 *2

シングルエリミネーショントーナメントにおける上記の問題を、試合数を増やして緩和した方式がダブルエリミネーションである。格闘ゲームの大規模オフライン大会の多くはダブルエリミネーション方式を採用しており、スマブラも例外ではない。

ダブルエリミネーション方式では、最初に参加したトーナメント(これを勝者側トーナメントと呼ぶ)で負けたプレイヤーが敗退せず、一度負けたプレイヤーだけで構成される敗者側トーナメントで試合を続行する。敗者側トーナメントでも1敗した場合、つまり合計で2敗した時点で敗退し順位が確定する。最終戦は勝者側トーナメントの優勝者と敗者側トーナメントの優勝者の試合となり、この試合の勝者が大会全体の優勝者となる。

つまり、ダブルエリミネーションでも依然として組合せ運は存在するものの、シングルエリミネーションと異なり2回チャンスがある。トップクラスの選手と運悪く早期に当たってしまった場合でも、ダブルエリミネーションなら敗者側トーナメントの組合せ次第で実力相応の順位まで勝ち上がる可能性が残る。

しかも、試合数が多いので順位がより細かく出る。たとえば64人トーナメントの場合、シングルエリミネーションで付く順位は1,2,3,5,9,17,33位だが、ダブルエリミネーションでは1,2,3,4,5,7,9,13,17,25,33,49位である。*3

f:id:YON_4:20201207031609p:plain

Wikipediaより、ダブルエリミネーショントーナメントの例

 

f:id:YON_4:20201207025227p:plain

f:id:YON_4:20201207025248p:plain

△横向き表記の、オフラインスマブラ大会ウメブラのトーナメント表。1枚目の画像が勝者側トーナメントであり、2枚目の画像が敗者側トーナメントである

 

 

ダブルエリミネーションによる順位付けを数理的に評価する

もう少し掘り下げて、ダブルエリミネーションが「どの程度」順位を適切に評価しているのかを確かめてみよう。ダブルエリミネーションの方が「多少」公正なのは明らかだが、トーナメントと試合数を倍にして運営コストを大幅に上げるだけの価値が本当にあるのだろうか?考察するために、以下を仮定してみよう。*4

  1. 各プレイヤーは1位相当、2位相当、3位相当、...の実力を順々に持っている
  2. 実力が全く同じプレイヤーは存在しない
  3. 実力が高いプレイヤーは自分より実力が低いプレイヤーに必ず勝つ

この仮定のもとで、たとえば3位相当の実力を持つプレイヤーについて考えてみる。総当り戦ならこのプレイヤーは確実に3位になる。一方でダブルエリミネーションなら2回運が悪ければ最下位に、シングルエリミネーションなら1回運が悪ければ最下位になる。このプレイヤーの平均的な順位は、総当り戦では3位ぴったりに、ダブルエリミネーションでは3位より悪い値に、シングルエリミネーションではさらに悪い値になるだろう。*5

このように、各プレイヤーの実力相応の順位から、平均的にどれだけ順位が前後するかを考えれば順位付けの適切さを評価できそうである。これらを全プレイヤーについて簡単に計算するには、何度か大会をシミュレーションしてみて、各プレイヤーの順位の平均絶対誤差を求め、さらにその平均割合をみればよい。これを、「大会形式による順位変動評価値」とする。*6

以上を数学記号を使って記述すると以下のようになる。本筋とはあまり関係ないので読み飛ばしてよい。

i < j のとき、プレイヤーA_iA_jに必ず勝利すると仮定する。十分大きなN, nを定め、この仮定のもとで、プレイヤーA_i (i = 1,2,...,n)で形式Xの大会を、毎回組合せを無作為に指定してN回行う。k回目のトーナメントにおけるA_iの順位がa_{i,k}であったとき、形式Xの「大会形式による順位変動評価値」を、下記の式で定める。これは、形式Xにおける順位がプレイヤー数の何%分だけ実力相応の順位から平均的に前後するかを表した値であり、単位は%である。

\begin{align*}
  \frac{100}{Nn^2}\sum_{k=1}^{N}{{{{\sum_{i=1}^{n}{|a_{i,k} - i|}}}}}
\end{align*}

 

大会をシミュレーションし、大会形式の影響を調べる

さて、これ以上まともに計算していると大変なことになりそうなので、プログラミングの力を借りよう。Python3でシングルエリミネーションとダブルエリミネーションのトーナメントをシミュレーションし、上記の値を計算する。読み飛ばして問題ないが、実装プログラムを示す。

シングルエリミネーション

import random

N = 100

for exponent in range(1, 11):
    n = 2**exponent # プレイヤー数
    MSE = [0]*n

    for _ in range(N):
        players = random.sample(range(1,n+1), k=n) # 各プレイヤーの実力順位
        abs_error = [0]*n

        while len(players) >= 2:
            tmp = []
            rank = 2**(len(players).bit_length()-2) + 1 # この時点で敗退したプレイヤーの順位
            for i in range(0,len(players),2):
                tmp.append(min(players[i], players[i+1]))
                if players[i] > players[i+1]:
                    abs_error[players[i]-1] += abs(players[i] - rank)
                else:
                    abs_error[players[i+1]-1] += abs(players[i+1] - rank)
            players = tmp.copy()
        
        for i in range(n):
            MSE[i] += abs_error[i]/N

    print(n, sum(MSE)/n, 100*sum(MSE)/n**2) # プレイヤー数、評価値(順位単位)、評価値(参加人数%単位)

 

ダブルエリミネーション

import random

N = 100

for exponent in range(1, 11):
    n = 2**exponent # プレイヤー数
    MSE = [0]*n

    for _ in range(N):
        players_wt = random.sample(range(1,n+1), k=n) # 勝者側トーナメントのプレイヤーの実力順位
        players_lt = [] # 敗者側トーナメントのプレイヤーの実力順位
        abs_error = [0]*n

        while len(players_wt) + len(players_lt) > 2:
            if len(players_wt) >= 2: # 1位2位は確定しているのでGFはシミュする必要なし
                tmp_wt = []
                tmp_lt = []
                for i in range(0,len(players_wt),2):
                    tmp_wt.append(min(players_wt[i], players_wt[i+1]))
                    tmp_lt.append(max(players_wt[i], players_wt[i+1]))
                players_wt = tmp_wt.copy()
                random.shuffle(tmp_lt) # 敗者側トーナメントへの参戦箇所をシャッフル
                if players_lt: # 敗者側トーナメントに残っているプレイヤーと新たに負けたプレイヤーを合わせる
                    x = min(len(players_lt), len(tmp_lt))
                    tmp = [None]*(x*2)
                    tmp[::2] = players_lt[:x].copy()
                    tmp[1::2] = tmp_lt[:x].copy()
                    tmp.extend(players_lt[x:])
                    tmp.extend(tmp_lt[x:])
                    players_lt = tmp.copy()
                else:
                    players_lt = tmp_lt.copy()

            if len(players_lt) >= 2:
                tmp_lt = []
                rank = len(players_wt) + len(players_lt)//2 + 1 # この時点で敗退したプレイヤーの順位
                for i in range(0,len(players_lt),2):
                    try:
                        tmp_lt.append(min(players_lt[i], players_lt[i+1]))
                        if players_lt[i] > players_lt[i+1]:
                            abs_error[players_lt[i]-1] += abs(players_lt[i] - rank)
                        else:
                            abs_error[players_lt[i+1]-1] += abs(players_lt[i+1] - rank)
                    except IndexError: # 敗者側トーナメントに奇数人いる場合
                        tmp_lt.append(players_lt[i])
                players_lt = tmp_lt.copy()
        
        for i in range(n):
            MSE[i] += abs_error[i]/N

    print(n, sum(MSE)/n, 100*sum(MSE)/n**2) # プレイヤー数、評価値(順位単位)、評価値(参加人数%単位)

 

上記のプログラムを使って得た結果は下記の通り。シングルエリミネーションでは参加プレイヤー数の22%程度、ダブルエリミネーションでは参加プレイヤー数の14%程度、実力相応の順位から前後することが分かった。たとえば512人のトーナメントでは、この8ポイント分の差は40位分に相当する。

プレイヤー数 シングルエリミネーション評価値 ダブルエリミネーション評価値
2 0.0% 0.0%
4 10.4% 0.0%
8 17.2% 8.0%
16 19.2% 10.9%
32 20.7% 12.7%
64 21.3% 13.4%
128 21.5% 13.7%
256 21.7% 14.1%
512 21.9% 14.1%
1024 21.9% 14.1%

 

さらに、512人のトーナメントでのシミュレーションにて、順位と評価値のグラフは以下のようになった。青色がシングルエリミネーション、オレンジ色がダブルエリミネーションであり、縦軸が大会形式による順位変動評価値(順位単位。%ではない)、横軸が実力順位(左ほど上位)を表す。下位の順位変動がダブルエリミネーションでは大きく抑えられていることが分かる。

f:id:YON_4:20201210235450p:plain

 

総評

シングルエリミネーションでは参加人数の22%程度、ダブルエリミネーションでは参加人数の14%程度、実力相当の順位から変動する。その差分は8ポイント程度であり、順位変動評価値のグラフから明らかなように、ダブルエリミネーションによって順位が適正に評価されるようになるのは上位よりもむしろ下位である。

この差異を大きく捉えるかどうかは運営次第だが、8ポイントの改善のために運営コストを大幅に増やすのはやや過剰に思える。適用プレイヤー層を絞るか、効率的なツールを使用した上で運用するのが良いだろう。

ただし、スマブラやその他格ゲーではキャラ相性やプレイヤー相性なるものが存在することに留意する必要がある。不利キャラや苦手プレイヤーにたまたま1回当たってしまっただけで敗退するのは(それも実力のうちと言えるかもしれないが)少し理不尽であり、その不満の解消のためにもダブルエリミネーションは有用な形式と言える。

 

 

【追記おまけ】組合せ運だけを評価できないか?

前述のグラフをよく見ると、最下位のプレイヤーもかなりの順位変動をしていることが分かる。最下位のプレイヤーは常に最速敗退するのに、これは変ではないだろうか?

実は、大会形式の順位付けの細かさが影響している。たとえば8人トーナメントにおける最弱のプレイヤーの順位を考えよう。このプレイヤーは必ず最速敗退するが、シングルエリミネーションでは5位に、ダブルエリミネーションでは7位になる。つまりダブルエリミネーションの方が実力に近い順位になるわけだが、これは組合せ運が軽減されたわけではなく、単にダブルエリミネーションの方が順位付けが細かいからである。

そこで、各プレイヤーの実力順位からの変動を測るのではなく、「その大会形式で取れる順位のうち、各プレイヤーの実力順位に最も近い順位からの変動」を測ることで、順位の粒度の影響を除去し、組合せ運による影響だけを見られないだろうか?そう考えて書いたコードと実行結果が以下である。

# single_elimination

import random
import bisect

# ソート済みのリストlの中から値vに最も近い(2つ以下の)値のリストを返す
def closest_values(l,v):
    output = [float("inf")]
    x = bisect.bisect_left(l,v)
    for i in [x-1, x, x+1]:
        try:
            if abs(output[0]-v) > abs(l[i]-v):
                output = [l[i]]
            elif abs(output[0]-v) == abs(l[i]-v):
                output.append(l[i])
                break
        except IndexError:
            continue
    return output

N = 100

for exponent in range(1, 11):
    n = 2**exponent # プレイヤー数
    MSE = [0]*n

    original_proper = [1] # その大会形式で取得できる順位
    x = 0
    while len(original_proper) < n:
        original_proper.extend([2**x+1]*(2**x))
        x += 1
    original_proper = sorted(list(set(original_proper)))

    for _ in range(N):
        players = random.sample(range(1,n+1), k=n) # 各プレイヤーの実力順位
        abs_error = [0]*n

        while len(players) >= 2:
            tmp = []
            rank = 2**(len(players).bit_length()-2) + 1 # この時点で敗退したプレイヤーの順位
            for i in range(0,len(players),2):
                tmp.append(min(players[i], players[i+1]))
                if players[i] > players[i+1]:
                    cv = closest_values(original_proper, players[i])
                    abs_error[players[i]-1] += min(abs(cv[x]-rank) for x in range(len(cv)))
                else:
                    cv = closest_values(original_proper, players[i+1])
                    abs_error[players[i+1]-1] += min(abs(cv[x]-rank) for x in range(len(cv)))
            players = tmp.copy()
        
        for i in range(n):
            MSE[i] += abs_error[i]/N

    print(n, sum(MSE)/n, 100*sum(MSE)/n**2) # プレイヤー数、評価値(順位単位)、評価値(参加人数%単位)

 

# double_elimination

import random
import bisect

# ソート済みのリストlの中から値vに最も近い(2つ以下の)値のリストを返す
def closest_values(l,v):
    output = [float("inf")]
    x = bisect.bisect_left(l,v)
    for i in [x-1, x, x+1]:
        try:
            if abs(output[0]-v) > abs(l[i]-v):
                output = [l[i]]
            elif abs(output[0]-v) == abs(l[i]-v):
                output.append(l[i])
                break
        except IndexError:
            continue
    return output

N = 100

for exponent in range(1, 11):
    n = 2**exponent # プレイヤー数
    MSE = [0]*n

    original_proper = [1,2,3] # その大会形式で取得できる順位
    x = 1
    dummy = True
    while len(original_proper) < n:
        if dummy:
            original_proper.extend([2**x + 2**(x-1) + 1]*(2**(x-1)))
            x += 1
        else:
            original_proper.extend([2**x + 1]*(2**(x-1)))
        dummy = not dummy
    original_proper = sorted(list(set(original_proper)))

    for _ in range(N):
        players_wt = random.sample(range(1,n+1), k=n) # 勝者側トーナメントのプレイヤーの実力順位
        players_lt = [] # 敗者側トーナメントのプレイヤーの実力順位
        abs_error = [0]*n

        while len(players_wt) + len(players_lt) > 2:
            if len(players_wt) >= 2: # 1位2位は確定しているのでGFはシミュする必要なし
                tmp_wt = []
                tmp_lt = []
                for i in range(0,len(players_wt),2):
                    tmp_wt.append(min(players_wt[i], players_wt[i+1]))
                    tmp_lt.append(max(players_wt[i], players_wt[i+1]))
                players_wt = tmp_wt.copy()
                random.shuffle(tmp_lt) # 敗者側トーナメントへの参戦箇所をシャッフル
                if players_lt: # 敗者側トーナメントに残っているプレイヤーと新たに負けたプレイヤーを合わせる
                    x = min(len(players_lt), len(tmp_lt))
                    tmp = [None]*(x*2)
                    tmp[::2] = players_lt[:x].copy()
                    tmp[1::2] = tmp_lt[:x].copy()
                    tmp.extend(players_lt[x:])
                    tmp.extend(tmp_lt[x:])
                    players_lt = tmp.copy()
                else:
                    players_lt = tmp_lt.copy()

            if len(players_lt) >= 2:
                tmp_lt = []
                rank = len(players_wt) + len(players_lt)//2 + 1 # この時点で敗退したプレイヤーの順位
                for i in range(0,len(players_lt),2):
                    try:
                        tmp_lt.append(min(players_lt[i], players_lt[i+1]))
                        if players_lt[i] > players_lt[i+1]:
                            cv = closest_values(original_proper, players_lt[i])
                            abs_error[players_lt[i]-1] += min(abs(cv[x]-rank) for x in range(len(cv)))
                        else:
                            cv = closest_values(original_proper, players_lt[i+1])
                            abs_error[players_lt[i+1]-1] += min(abs(cv[x]-rank) for x in range(len(cv)))
                    except IndexError: # 敗者側トーナメントに奇数人いる場合
                        tmp_lt.append(players_lt[i])
                players_lt = tmp_lt.copy()
        
        for i in range(n):
            MSE[i] += abs_error[i]/N

    print(n, sum(MSE)/n, 100*sum(MSE)/n**2) # プレイヤー数、評価値(順位単位)、評価値(参加人数%単位)

 

プレイヤー数 シングルエリミネーション評価値 ダブルエリミネーション評価値
2 0.0% 0.0%
4 4.6% 0.0%
8 5.4% 4.3%
16 6.8% 7.4%
32 8.1% 8.9%
64 8.7% 9.8%
128 9.0% 10.5%
256 9.1% 10.6%
512 9.2% 10.9%
1024 9.2% 10.9%

 

f:id:YON_4:20201211064023p:plain

 

なんとダブルエリミネーションの方が順位変動評価値が大きくなってしまった。グラフによると、ちょうど322位の実力を持つプレイヤーの所でとんでもなく変動が大きくなっている。

実は、512人のダブルエリミネーションで取れる順位のうち、322位に最も近いのは385位である。一方で隣の321位に最も近い、ダブルエリミネーションで取れる順位は257位と385位の2つである。321位が実際の結果に従って257位と385位の両方からより変動評価値が小さくなる方を選択できるのに対し、322位は結果に関わらず385位しか選択できない。このような原因で322位で変動評価値のジャンプが起こっている。

同様の理由で、グラフには他の箇所にもジャンプが見られるが、元々の実力順位の値が大きいほどジャンプも大きくなる。したがって、より細かく下位を順位付けするダブルエリミネーションで大きなジャンプが起こってしまい、全体の評価評価値もそれに釣られて悪くなってしまう。

この問題を解決するため、変動評価値の計算にてnで割る代わりに、各プレイヤーの変動評価値を実力順位 iで割って相対誤差を見よう。こうすると、大会規模に対する変動割合は見られなくなるが、プレイヤー実力順位に対する変動割合を調べることができる。

\begin{align*}
  \frac{100}{Nn}\sum_{k=1}^{N}\sum_{i=1}^{n}\left|\frac{a_{i,k}-i}{i}\right|
\end{align*}

 

        for i in range(n):
            MSE[i] += abs_error[i]/(N*(i+1))

    print(n, sum(MSE), 100*sum(MSE)/n)

 

プレイヤー数 シングルエリミネーション評価値 ダブルエリミネーション評価値
2 0.0% 0.0%
4 6.5% 0.0%
8 10.1% 7.7%
16 18.6% 14.7%
32 25.1% 19.7%
64 30.2% 24.1%
128 34.8% 26.9%
256 37.1% 28.4%
512 38.1% 29.4%
1024 39.1% 30.1%

 

f:id:YON_4:20201211070743p:plain

 

というわけで、確かにダブルエリミネーションの方が変動評価値が9ポイントほど小さくなり、割合の変化だけ見ると結局最初の結果とほぼ同じとなった。最後のグラフの縦軸の単位は%であり、自分の実力順位に対してどれだけ順位が変動するかを示している。たとえば3位のプレイヤーを見ると、シングルエリミネーションでは1.7の値を取っているので平均的に5.1位順位が悪化するが、ダブルエリミネーションでは0.58の値なので平均的に1.7位程度しか悪化しない。大会方式による順位粒度の影響を除去し、さらに実力順位に対する変動の割合を見るならば、ダブルエリミネーションは上位に対する恩恵が大きい方式と言える。

 

 

*1:一般化すると、2n人のトーナメントの場合、この中の1位相当のプレイヤーAが2位相当のプレイヤーBと決勝まで当たらないときに限り、Bは2位になれる。この確率はn/(2n-1)しかない

*2:シングルエリミネーションの問題は昔から認識されている。たとえば不思議の国のアリスで知られるルイスキャロル(本名チャールズドジソン)は、1883年に出版した論文LAWN TENNIS TOURNAMENTS: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Methodにて、シングルエリミネーショントーナメントの運の影響を改善する方法を提案している。この方式はトリプルエリミネーション形式をベースにしており、自分より強いプレイヤーが少なくとも3人いることが確認された時点で敗退する

*3:一般化すると、シングルエリミネーションで取れる1位以外の順位は2^i+1 (i=0,1,2,...)であり、ダブルエリミネーションで取れる1位以外の順位は2^i+1 (i=0,1,2,...)2^i+2^{i-1}+1 (i=1,2,3...)である

*4:たとえばスマブラでも、少人数運営の小規模大会が多いオンラインではシングルエリミネーションの方が主流である。大会参加者側はシングルエリミネーションよりダブルエリミネーションを希望することが多い印象があるが、大所帯の運営による大規模大会でないとダブルエリミネーションは採用し辛い

*5:情報科学の見地から考察すると、大会という試みは「プレイヤーを実力順に並び替える操作」とみなせるので、大会形式はソートアルゴリズムとみなすことができる。実際にそのまま対応する組合せもあり、たとえばパラマストーナメントはバブルソートの一部と同じであり、総当り戦は比較数え上げソートと全く同じである。トーナメントを行うようにソートするトーナメントソートという手法も存在する。情報科学においては主に計算効率でソートアルゴリズムは評価されるが、大会という形式では比較回数が多い非効率なソートほど試合数が多く、頑健で運要素が小さいと見なせる

*6:誤差の評価基準は色々あるが、今回は直接誤差を解釈したいので平均絶対パーセント誤差(MAPE)を使用した。詳しくはこちらを参照