トーナメントにおける最適なプレイヤーの配置と実装方法

今回はトーナメント（シングルエリミネーション）においてOFTN.GGで使っているプレイヤーの配置方法の考え方と、TypeScriptでの実装例を解説します。

このQuizKnockの動画がこの記事を書くきっかけです。この動画ではランダムな配置における準優勝者の実力順位の期待値が計算されています。

配置方法

この記事では、プレイヤーの実力順位があらかじめ分かっているものとし、その順位をシード値として扱います。 実力1位をシード値1、2位を2とし、全員に1から参加者数までの連番を付けます。

シングルエリミネーションでは、プレイヤーの配置が勝敗・順位に影響します。一回戦で一番目に強い人と二番目に強い人が当たると、どちらかは初戦に敗北し、期待された順位よりも下の順位に終わることになります。

例えば動画のように８人のトーナメントを考えます。以降の数字は各プレイヤーのシード値です。

配置順

[1, 2, 3, 4, 5, 6, 7, 8]

８人をトーナメントの上からシード値の小さい順に並べた場合、初戦で実力1位と2位のプレイヤーが当たってしまいます。

そこでどのような順番に配置すれば、強い人が早い段階で対戦せずに済むのかを考えていきます。

最適な配置の考え方

ここでは、シード値の小さいプレイヤー同士が、できるだけ後のラウンドで対戦する配置を目指します。

配置の考え方は意外と単純で、各段階で組になるシード値の合計が同じになるように配置します。

決勝から逆算して考えます。

決勝：シード値1と2が決勝まで当たらないように分ける

[1, 2]

準決勝：シード値1〜4が準決勝まで当たらないように分ける（組になるシード値の合計は5）

[1, 4], [2, 3]

1回戦：残りの4人を配置する（組になるシード値の合計は9）

[[1, 8], [4, 5]], [[2, 7], [3, 6]]

結果的に以下の配置で対戦することにより、強い人が早い段階で対戦せずに済むことがわかります。

[1, 8, 4, 5, 2, 7, 3, 6]

実装

この配置方法をTypeScriptで実装してみます。入力の配列は、シード値の小さい順に並んでいることを前提にします。

function recursiveBisection<T>(arr: T[]): T[] {
  if (arr.length <= 1) return [...arr];

  // シード値1と2の配置から始める
  let order = [1, 2];

  while (order.length < arr.length) {
    // 次の段階で、組になるシード値の合計
    const sum = order.length * 2 + 1;
    const next: number[] = [];

    for (const seed of order) {
      next.push(seed);

      // 元のシード値の直後に、合計がsumになる相手を配置
      const opponent = sum - seed;
      if (opponent <= arr.length) next.push(opponent);
    }

    order = next;
  }

  // シード値を、元の配列の要素に置き換える
  return order.map((seed) => arr[seed - 1] as T);
}

recursiveBisection([1, 2, 3, 4, 5, 6, 7, 8]);
// [1, 8, 4, 5, 2, 7, 3, 6]

order は [1, 2] から始まります。 4人に広げるときは sum = 5、8人に広げるときは sum = 9 とし、各シード値 seed の直後に sum - seed を追加します。

[1, 2]

sum = 5：各シード値の後ろに「5 − seed」を追加
[1, 4, 2, 3]

sum = 9：各シード値の後ろに「9 − seed」を追加
[1, 8, 4, 5, 2, 7, 3, 6]

これを入力の人数に達するまで繰り返すことで、上位同士が早いラウンドで対戦しない配置を生成できます。

人数が2の累乗でない場合は、opponent <= arr.length の条件で、参加者のいない番号を追加しないようにしています。例えば5人なら、返り値は [1, 4, 5, 2, 3] です。これはプレイヤーの並び順であり、不戦勝を含む対戦表の構築は別に扱います。

まとめ

今回は、トーナメントで強いプレイヤー同士が早い段階で対戦しないようにする配置と、その実装を紹介しました。

決勝から逆算して組になるシード値の合計を揃えていくと、配置を段階的に作ることができます。この考え方をそのまま繰り返し処理にすることで、プレイヤーの配置を計算できます。

色々な人数における配置に関してはOFTN.GGに登録して確認してください。