■

前にリーグ戦についてあれこれ考えたのだけど
今日(帰宅途中)はトーナメント戦について考えてみた。

目標としては、参加人数とシングル/ダブルイリミネーションを入力すると
どばっとトーナメントテーブルを吐き出すようなもの。

とりあえずシングルイリミネーションから。
シングルイリミネーションだと、強者も弱者も平等公平実力無関係であることが望ましい。

人数が2^nに等しければ簡単だ。
例えば参加人数が8人のシングルイリミネーションだったら
何も考えずに8人分枠を作って二人ずつ隣同士をつなげていけば、トーナメント表ができてしまう。作るのも簡単だし、皆決勝までの道のりも公平だ。

Player1	Game1	Game5	Game7
Player2
Player3	Game2
Player4
Player5	Game3	Game6
Player6
Player7	Game4
Player8

天下一武道会の決勝進出枠が8人だったのも
男塾キャラが4→8→16→32と増えていったのも、トーナメント作成が楽且つ公平だから。
楽且つ不公平なのは幽々白書。

n人のトーナメントを作成するには

1. nより大きい最小の2^Xを探す
2. 2^X人のトーナメントを作る
3. 1〜2^Xのうち、どの枠を実際に使用するかを決める(使用しない枠はBYE)

の方法が、2^Xに枠を足すより分かりやすい。

3番目のどの枠を使用するか、というのは、2^X枠の優先順位をどう決めるか、ということに置き換えることができる。

例えば、最初に8人トーナメントを作り、1〜8の優先順位を決めて、1〜n番目の枠を使う。
直感的にはPlayer番号と2^k(※k=[1,…,X-1])の剰余をとって
2分割を繰り返すのが非常に公平っぽいが証明は難しそう。そもそも公平の定義が難しい。

この方法がそこそこ公平だと仮定すれば、優先順位は機械的に決めることができる。
2^X=8だったら
【1,2,3,4,5,6,7,8】
まず1-8を2で割って余り1のグループと余り0のグループに分ける
【【1,3,5,7】vs【2,4,6,8】】
次にそれぞれを2^2=4で割って余りが1、3、2、4のグループに分ける
【【【1,5】【3,7】】【【2,6】【4,8】】】
要素が2個ずつになったら(正確には、最後に8の剰余をとって1個ずつになる。対戦としては順不同なので省略)終了。あとは順に並べるだけ。

例として6人トーナメントを作ってみた。優先枠はPlayer1>Player2>Player3>･･･>Player8

Player1	Game1	Game5	Game7
Player5
Player3	Game2
Player7
Player2	Game3	Game6
Player6
Player4	Game4
Player8

↓Player7とPlayer8がBYEなので

Player1	Game1	Game3	Game5
Player5
Player3
Player2	Game2	Game4
Player6
Player4

こんな感じ。

下のトーナメントに注目すると、Game3、Game4がシードの分偏りが出ている。
それでも、決勝のGame5はどちらも3人の代表なので納得しやすいはず。
対称じゃないと嫌な場合は人数確定後にひっくり返せばOK。

われながら
"直感的"に公平なものが"機械的"に作成可能てのがうさんくさい。