LoginSignup
1
2

More than 5 years have passed since last update.

@tibigame

ランダムマッチングとスイス式マッチングによる順位戦の昇級をシミュレーションする

Last updated at Posted at 2018-04-14

はじめに

多数のプレイヤーが参加する大会のリーグ戦ではスイス式の対戦が組まれることがある。
これを将棋の順位戦のシステムに採用するとどうなるのか気になるところだ。
理論的に考えるのは難しいので、シミュレーションしてみよう。

ランダムマッチングとスイス式マッチング

  • ランダムマッチングとは各回戦ごとに完全にランダムな組み合わせで対戦が行なわれる方式である。
  • スイス式マッチングとはある回戦まではランダムマッチングを行い、以降は……
    • その次点での順位(勝数, SOS, SB, ...)を基にして上位同士を組み合わせる
      • SOSとは対戦した相手の勝数の合計である
      • SBとはSOSのうち勝った相手のみを合計した数値である

順位戦のシミュレーション

  • 開始時に昨期順位が一意に定まっている
  • スイス式マッチングに関わる暫定順位は(勝数, SOS, SB, 昨期順位)でソートされる
  • スイス式マッチングかどうかに関わわず、最終成績は(勝数, 昨期順位)でソートされる

結果を予想する

ランダムマッチングでは例え最上位者であっても均等に下位陣とマッチングする権利を有する。
しかし、スイス式マッチングの場合は上位陣が強制的にマッチされるので下位陣と当たれない不利が生じる。
したがって最上位者から少しランクが落ちたところに漁夫の利を得る陣営が存在する。
さて、この予想は正しいだろうか。

コーディング

プレイヤークラス

battle_number = 10  # 対局数


# プレイヤーを表すクラス
class Player:
    def __init__(self, rank: int, rate: int):
        self.rank = rank  # 昨期順位
        self.rank_n = None  # 今期順位
        self.r = rate  # レーティング
        self.battle = [0] * battle_number  # 対戦相手
        self.result = [None] * battle_number  # 対局結果
        self.win = 0  # 勝ち数
        self.lose = 0  # 負け数
        self.sos = 0  # 対戦相手の勝数の合計
        self.sb = 0  # 対戦相手のうち勝った相手の勝数の合計

    def battled(self, p: int, i: int) -> bool:  # i回戦までにpと対戦したか
        return p in self.battle[0:i]

あるプレイヤーと対戦したかをよくチェックするので、メンバ関数化しておく。

ユーティリティ関数

import random
import numpy as np


def make_random_match(n: int):  # nまでのリストをランダムシャッフルして2個ずつに分割する
    return zip(*[iter(random.sample(range(n), n))]*2)


def shuffle_random_match(given_list):  # 与えられたリストをランダムシャッフルして2個ずつに分割する
    return [(given_list[pair[0]], given_list[pair[1]]) for pair in make_random_match(len(given_list))]


def colosseum(player1: Player, player2: Player, i: int):  # player1とplayer2をi回戦目に対戦させて結果を記録する
    def elorating(e):  # イロレーティングの勝率を求める
        return 1 - 1 / (1 + pow(10, (e / 400)))

    def elo(rating1, rating2):  # レートを与えると勝ち負けを確率で返す
        return np.random.rand() < elorating(rating1 - rating2)

    result = elo(player1.r, player2.r)
    player1.result[i] = result
    player2.result[i] = not result

make_random_matchはn人を2人ずつに分けて対戦表としれくれを満たす関数。
shuffle_random_matchはリストをランダムシャッフルしてから2個ずつに分けて対戦表とする関数。
colosseumはレーティングによる勝率の差を考慮して対局シミュレーションを行い、結果の記録まで行う関数。

リーグを表すクラス

player_number = 50  # リーグの人数 (偶数を与えること)
max_rating = 1800  # 最上位者のレーティング
rate_diff = 10  # n位とn+1位のレーティングの差


# リーグを表すクラス
class League:
    def __init__(self, player_number_: int):
        self.player_number = player_number_
        self.players = [Player(rank, max_rating - rank * rate_diff) for rank in range(self.player_number)]
        self.temp_rank_list = [None] * player_number_
        self.result_rank_list = [None] * player_number_

    def random_match(self, i: int):  # i回戦目のランダムマッチングを作成する
        for matching in make_random_match(self.player_number):
            if self.players[matching[0]].battled(matching[1], i):
                return self.random_match(i)  # 対戦経験ありなのでマッチング失敗
            self.players[matching[0]].battle[i] = matching[1]
            self.players[matching[1]].battle[i] = matching[0]
        return  # マッチングに成功

    def swiss_match(self, i: int):  # i回戦目のSwissマッチングを作成する
        def sub_random_match(remain_battle):
            matching_list = shuffle_random_match(remain_battle)
            for matching in matching_list:
                if self.players[matching[0]].battled(matching[1], i):
                    return None  # 対戦経験ありなのでマッチング失敗
                self.players[matching[0]].battle[i] = matching[1]
                self.players[matching[1]].battle[i] = matching[0]
            return matching_list  # マッチングに成功

        def sub_swiss_match(temp_rank_list, matching_list):
            remain_battle = list(temp_rank_list)
            while len(remain_battle) > 30:  # 2人ずつマッチングを繰り返す
                # 残りの候補から最上位をマッチングさせる
                p1 = remain_battle[0]
                p2 = None
                index = 0
                match_success = False
                while not match_success:
                    index += 1
                    p2 = remain_battle[index]
                    if self.players[p1].battled(p2, i):
                        match_success = True
                matching_list.append([p1, p2])
                remain_battle.remove(p1)
                remain_battle.remove(p2)

            # 30人以下になったらランダムマッチングにする
            random_match_list = None
            while not random_match_list:
                random_match_list = sub_random_match(remain_battle)

            matching_list.extend(random_match_list)
            for matching in matching_list:
                self.players[matching[0]].battle[i] = matching[1]
                self.players[matching[1]].battle[i] = matching[0]

        sub_swiss_match(self.temp_rank_list, [])

    def battles(self, i: int):  # i回戦目の対戦を実行する
        remain_battle = list(range(self.player_number))
        while len(remain_battle) >= 1:
            p1 = remain_battle[0]
            p2 = self.players[p1].battle[i]
            colosseum(self.players[p1], self.players[p2], i)
            remain_battle.remove(p1)
            remain_battle.remove(p2)

    def count_win(self):  # (現時点での)勝ち星をカウントする
        for player in self.players:
            player.win = player.result.count(True)
            player.lose = 10 - player.win

    def count_sos(self):  # (現時点での)SOSとSBをカウントする
        self.count_win()
        battled_num = self.players[0].win + self.players[0].lose  # 対局数は全員同じ
        for player in self.players:
            player.sos = 0
            player.sb = 0
            for i in range(battled_num):  # 対戦相手の勝数を順に足していく
                player.sos += self.players[player.battle[i]].win
                if player.result[i]:  # SBは勝った相手にだけ加算する
                    player.sb += self.players[player.battle[i]].win

    def temp_rank(self):  # 暫定の順位をつける
        self.temp_rank_list = []
        for i, player in enumerate(sorted(self.players, key=lambda x: (x.lose, x.sos, x.sb, x.rank))):
            self.players[player.rank].rank_n = i
            self.temp_rank_list.append(player.rank)

    def result_rank(self):  # 最終の順位をつける
        for i, player in enumerate(sorted(self.players, key=lambda x: (x.lose, x.rank))):
            self.players[player.rank].rank_n = i
            self.result_rank_list[i] = player.rank

1位が最もレーティングが高くて、そこから10ずつ下がっていくという設定で50人、10回戦のリーグを行う。

シミュレーション

simulation_number = 10000  # シミューレーションの回数
rank_up_number = 3  # 昇級人数


# 順位戦シミュレーション
def normal_simulation():
    rank_up = []
    runner_up = []
    for x in range(simulation_number):
        league = League(player_number)
        for i in range(battle_number):
            league.random_match(i)
            league.battles(i)
        league.count_win()
        league.result_rank()
        rank_up.extend(league.result_rank_list[0:rank_up_number])
        runner_up.append(league.players[league.result_rank_list[rank_up_number]].win)
        if x % 1000 == 0:
                print(x)
    return rank_up, runner_up


# スイス式シミュレーション
def swiss_simulation():
    rank_up = []
    runner_up = []
    x = 0
    while x < simulation_number:
        try:
            league = League(player_number)
            for i in range(4):
                league.random_match(i)
                league.battles(i)
            league.count_sos()
            for i in range(4, battle_number):
                league.temp_rank()
                league.swiss_match(i)
                league.battles(i)
                league.count_sos()
            league.result_rank()
            rank_up.extend(league.result_rank_list[0:rank_up_number])
            runner_up.append(league.players[league.result_rank_list[rank_up_number]].win)
            if x % 1000 == 0:
                print(x)
        except:
            print("expected error")
        else:
            x += 1
    return rank_up, runner_up

実行と結果の分析


def analyze_result(rank_up, runner_up):
    rank_up_list = [0] * player_number
    runner_up_list = [0] * 11
    for i in range(player_number):
        rank_up_list[i] = rank_up.count(i)
    for i in range(11):
        runner_up_list[i] = runner_up.count(i)
    return rank_up_list, runner_up_list


normal1, normal2 = normal_simulation()
swiss1, swiss2 = swiss_simulation()
normal_result1, normal_result2 = analyze_result(normal1, normal2)
swiss_result1, swiss_result2 = analyze_result(swiss1, swiss2)

print(f"ランダム, スイス式マッチングによる次点の勝数の差")
for win_num in range(6, 11):
    print(f"{win_num:2d}勝: {normal_result2[win_num]}: {swiss_result2[win_num]}")

print(f"ランダム・スイス式マッチングによる昇級確率の差")
for i, result in enumerate(zip(normal_result1, swiss_result1)):
    print(f"{i + 1:2d}位: {result[0]:.4f}: {result[1]:.4f}")

結果

ランダム, スイス式マッチングによる次点の勝数の差
 6勝: 0: 0
 7勝: 87: 756
 8勝: 6648: 7085
 9勝: 3255: 2142
10勝: 10: 17
ランダム・スイス式マッチングによる昇級確率の差
 1位: 46.3000: 42.0100
 2位: 39.9400: 35.9500
 3位: 34.6900: 32.4600
 4位: 30.1900: 28.0300
 5位: 24.4400: 23.7800
 6位: 21.0200: 20.2900
 7位: 16.9700: 17.3200
 8位: 14.2000: 15.0700
 9位: 12.0300: 12.5900
10位: 10.3200: 10.8300
11位: 8.4900: 9.1700
12位: 7.0600: 8.0100
13位: 5.8400: 6.6300
14位: 4.9500: 5.7200
15位: 3.8800: 5.1800
16位: 3.3000: 4.3400
17位: 2.8200: 3.3700
18位: 2.4800: 3.2800
19位: 1.9300: 2.7300
20位: 2.0300: 2.0800
21位: 1.3800: 2.0200
22位: 1.1000: 1.4700
23位: 1.0300: 1.3800
24位: 0.5200: 1.0600
25位: 0.6600: 1.0800
26位: 0.5800: 0.6600
27位: 0.4700: 0.7400
28位: 0.3700: 0.5500
29位: 0.2000: 0.4200
30位: 0.1300: 0.3500
31位: 0.2100: 0.3300
32位: 0.1100: 0.1600
33位: 0.0700: 0.1600
34位: 0.1100: 0.1400
35位: 0.0300: 0.1500
36位: 0.0400: 0.0500
37位: 0.0000: 0.0600
38位: 0.0400: 0.1100
39位: 0.0000: 0.0300
40位: 0.0200: 0.0700
41位: 0.0100: 0.0300
42位: 0.0000: 0.0900
43位: 0.0100: 0.0300
44位: 0.0100: 0.0000
45位: 0.0000: 0.0000
46位: 0.0000: 0.0100
47位: 0.0100: 0.0000
48位: 0.0000: 0.0000
49位: 0.0100: 0.0000
50位: 0.0000: 0.0100

まとめ

  • 全勝者4人以上の確率はおよそ0.1%
  • スイス式では次点のボーダーが下がっている(7勝での次点も現実的)
  • スイス式は上位陣が虐げられているという予想は正しかった
  • 1～6位の不利益は7位以下が享受するが、7～20位のゾーンではかなりの漁夫の利がある
1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2