チームレーティングシステムの考察

前回、Trueskillについて調べたことを整理した。

https://qiita.com/nishiha/items/afa8d8a741ec3b2820b7

# イロレーティング、Trueskillの問題点
しかし、個人的にはイロレーティング、Trueskillに以下の不満がある。
・Trueskillのレート移動がゼロサムでない点
・戦力均衡のマッチング(ランダムウォーク)
・チーム内の戦力のばらつき度合を考慮してない

一般にイロレーティングでは$W_{AB}$をレートからの予測勝利確率、勝敗結果$s$(勝利1、敗北0)とおいてレート更新量は以下で示される。
$R_{new}=R+K(s-W_{AB})$
ここで
$W_{AB}=\frac{1}{1+10^{(R_A-R_B)/400}}$

しかしながらネット上のゲームのチームマッチにおいてはランダムマッチングではなくなるべく実力が拮抗するようにマッチング操作するから常に$W_{AB}≒0.5$であり、勝った時$+K/2$移動、負けた時$-K/2$移動の一次元のランダムウォークとほぼ等しくなる。

# イロレーティングの集団戦
一般的にはイロレーティングは集団戦を考えることは出来ないとされている。
しかし、チーム総戦力をチーム構成員のレート平均とみなし、勝敗の決定した時、チームのメンバーのレートを増やすか減らすだけの拡張を与えるとする。
総プレイヤー数$n$、1チームメンバー$m$として$loss=mean(abs(Elo_{true}-Elo_{pred}))$を調べた。対戦する時のチームメンバーが多いほど収束は早くなるが、代わりにノイズが大きくなる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/dc651de8-4bf4-cab4-7efa-de71bc92e0dc.png)


```python
import numpy as np
import matplotlib.pyplot as plt
import random

a = np.log(10)
fig = plt.figure()
ax = []
for index, m in enumerate([1,2,3,5]):
    K = 32
    ax.append(fig.add_subplot(2, 2, index+1))
    for n in [16, 32, 64, 128, 256]:
        print(n,m)
        Elo_true = np.random.randn(n) * 400 / np.sqrt(2) + 1500
        Elo_true = Elo_true - (np.mean(Elo_true) - 1500)
        Elo_pred = np.ones(n) * 1500
        l = list(range(n))
        loss = []
        for t in range(20000):
            sample = random.sample(l, 2*m)
            A_team, B_team = sample[:m], sample[m:]
            
            A_score_true, A_score_pred = np.mean(Elo_true[A_team]), np.mean(Elo_pred[A_team])
            B_score_true, B_score_pred = np.mean(Elo_true[B_team]), np.mean(Elo_pred[B_team])
            
            R_AB_true = A_score_true - B_score_true
            R_AB_pred = A_score_pred - B_score_pred
            W_AB_true = 1/(1+np.exp(-a*R_AB_true/400))
            W_AB_pred = 1/(1+np.exp(-a*R_AB_pred/400))

            s = 1 if W_AB_true > np.random.rand() else 0
            Elo_pred[A_team] += K * (s - W_AB_pred)
            Elo_pred[B_team] -= K * (s - W_AB_pred)
            loss.append(np.mean(np.abs(Elo_true-Elo_pred)))
        print(Elo_true[:8])
        print(Elo_pred[:8])
        ax[index].plot(range(len(loss)), loss, label='n=%d,m=%d'% (n,m))
        ax[index].legend()
plt.show()
```

マッチングの収束回数を同じくらいにするには$K=\frac{32}{\sqrt{m}}$にすると良い。
これは勾配の絶対値総和はチーム内人数が増えると$m$倍に増えるが、勾配期待値はチーム内人数が増えても$\sqrt{m}$倍にしか増えないからである。

```python
    K = 32/np.sqrt(m)
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/fdca6576-31a8-79b7-a778-2dc19a4b3a31.png)

# 5vs5の戦力均衡のマッチング
前節ではランダムな相手とチームを組んで対戦するランダムマッチングを考えた。
ここではチーム戦を行う場合、実際には仮想レートの合計戦力を等しくなるようチーム組み合わせは操作される。以下の様にチーム分割関数を与え、例えば5vs5のゲームでは最初に総プレイヤー$n$からランダムに10人を選出し、その10人のプレイヤーをレートの仮想合計戦力がなるべく等しいようにチームを2つに分割する。要するに$W_{AB}≒0.5$が勝手に設定される。これは隣接しあうプレイヤーレート間でしかレートが移動しなくなるのでバブルソートのように収束が遅くなると思われる。
この時、条件によって**損失は途中から増大する。** 前述の通りランダムマッチングでは損失が下がるのに、仮想レートで戦力均衡になるようチームメンバーを操作すると損失が増えて行くのは不思議である。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/a6b4d061-24cf-509a-a4bb-fc7513b8f4a3.png)


```python
import numpy as np
import matplotlib.pyplot as plt
import random

def team_split(member, member_index, m=5):
    mean_score = np.mean(member)
    best_score = 10000000
    l = list(range(2*m))
    for i in range(60*m):
        team = random.sample(l, m)
        team_mean_score = np.mean(member[team])
        score = np.abs(team_mean_score - mean_score)
        if score < best_score:
             best_score = score
             best_team = team

    best_member_index = np.array(member_index)[best_team]
    list.sort(best_team, reverse=True)
    for i in best_team:
        member_index.remove(member_index[i])
    return best_member_index, member_index

a = np.log(10)
fig = plt.figure()
ax = []
for index, m in enumerate([1,2,3,5]):
    K = 32/np.sqrt(m)
    ax.append(fig.add_subplot(2, 2, index+1))
    for n in [16, 32, 64, 128, 256]:
        print(n,m)
        Elo_true = np.random.randn(n) * 400 / np.sqrt(2) + 1500
        Elo_true = Elo_true - (np.mean(Elo_true) - 1500)
        Elo_pred = np.ones(n) * 1500
        l = list(range(n))
        loss = []
        for t in range(20000):
            sample = random.sample(l, 2*m)
            team_score = Elo_pred[sample]
            A_team, B_team = team_split(team_score, sample, m)
            
            A_score_true, A_score_pred = np.mean(Elo_true[A_team]), np.mean(Elo_pred[A_team])
            B_score_true, B_score_pred = np.mean(Elo_true[B_team]), np.mean(Elo_pred[B_team])
            
            R_AB_true = A_score_true - B_score_true
            R_AB_pred = A_score_pred - B_score_pred
            W_AB_true = 1/(1+np.exp(-a*R_AB_true/400))
            W_AB_pred = 1/(1+np.exp(-a*R_AB_pred/400))

            s = 1 if W_AB_true > np.random.rand() else 0
            Elo_pred[A_team] += K * (s - W_AB_pred)
            Elo_pred[B_team] -= K * (s - W_AB_pred)
            loss.append(np.mean(np.abs(Elo_true-Elo_pred)))
        print(Elo_true[:8])
        print(Elo_pred[:8])
        ax[index].plot(range(len(loss)), loss, label='n=%d,m=%d'% (n,m))
        ax[index].legend()
plt.show()
```

# KLダイバージェンス
Elo rateの更新項にKLダイバージェンスの微分項を考慮してみる。
```math
D_{KL}=-\frac{1}{2}(-2\log{\sigma}+(\mu-\mu_0)^2+\sigma^2-1)
```
```math
\frac{\partial D_{KL}}{\partial \mu}=\mu_0-\mu
```

```math
\frac{\partial D_{KL}}{\partial \sigma}=\frac{1}{\sigma}-\sigma
```

この時、チーム戦力均衡のマッチングを採用しても、損失が際限なく増大するという現象は抑えられた。しかし、$n,m$が大きい場合、500以下の初期ステップでlossが逆に増大する副作用が見られた。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/64aca09e-9be3-67e9-b719-3f4cfa387a84.png)


```python
import numpy as np
import matplotlib.pyplot as plt
import random

def team_split(member, member_index, m=5):
    mean_score = np.mean(member)
    best_score = 10000000
    l = list(range(2*m))
    for i in range(60*m):
        team = random.sample(l, m)
        team_mean_score = np.mean(member[team])
        score = np.abs(team_mean_score - mean_score)
        if score < best_score:
             best_score = score
             best_team = team

    best_member_index = np.array(member_index)[best_team]
    list.sort(best_team, reverse=True)
    for i in best_team:
        member_index.remove(member_index[i])
    return best_member_index, member_index

a = np.log(10)
fig = plt.figure()
ax = []
for index, m in enumerate([1,2,3,5]):
    K = 32/np.sqrt(m)
    ax.append(fig.add_subplot(2, 2, index+1))
    for n in [16, 32, 64, 128, 256]:
        print(n,m)
        Elo_true = np.random.randn(n) * 400 / np.sqrt(2) + 1500
        Elo_true = Elo_true - (np.mean(Elo_true) - 1500)
        Elo_pred = np.ones(n) * 1500
        l = list(range(n))
        loss = []
        for t in range(20000):
            sample = random.sample(l, 2*m)
            team_score = Elo_pred[sample]
            A_team, B_team = team_split(team_score, sample, m)
            
            A_score_true, A_score_pred = np.mean(Elo_true[A_team]), np.mean(Elo_pred[A_team])
            B_score_true, B_score_pred = np.mean(Elo_true[B_team]), np.mean(Elo_pred[B_team])
            
            R_AB_true = A_score_true - B_score_true
            R_AB_pred = A_score_pred - B_score_pred
            W_AB_true = 1/(1+np.exp(-a*R_AB_true/400))
            W_AB_pred = 1/(1+np.exp(-a*R_AB_pred/400))

            s = 1 if W_AB_true > np.random.rand() else 0
            Elo_pred[A_team] += K * (s - W_AB_pred)
            Elo_pred[B_team] -= K * (s - W_AB_pred)
            loss.append(np.mean(np.abs(Elo_true-Elo_pred)))

            # KL Divergence
            mu = np.mean(Elo_pred)
            sigma = np.std(Elo_pred)/(400/np.sqrt(2))
            mu_new = mu + (1500 - mu) * 0.001
            sigma_new = sigma + (1/sigma - sigma) * 0.001
            Elo_pred = (Elo_pred - mu)*sigma_new/sigma + mu_new

        print(Elo_true[:8])
        print(Elo_pred[:8])
        ax[index].plot(range(len(loss)), loss, label='n=%d,m=%d'% (n,m))
        ax[index].legend()
plt.show()
```
# Adam
機械学習のAdamのように動的に勾配の大きさを変えてみたい。Elo rateの場合は変動の大きさは定数Kに比例する。定義があまり分かってないため適当なコード例を示すが、以下の場合ある程度安定した挙動をした。しれっとBatch学習を取り入れているがKL Divergenceとは少し相性が悪いため更新方法に工夫がいる。

・ランダムマッチング
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/b0a0f3a4-ff61-8ea5-d047-1f9df85af794.png)


・戦力均衡マッチング
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/cbb25bca-8d8a-7563-c014-54bac7eaf290.png)



```python
import numpy as np
import matplotlib.pyplot as plt
import random

def team_split(member, member_index, m=5):
    mean_score = np.mean(member)
    best_score = 10000000
    l = list(range(2*m))
    for i in range(12*m*m):
        team = random.sample(l, m)
        team_mean_score = np.mean(member[team])
        score = np.abs(team_mean_score - mean_score)
        if score < best_score:
             best_score = score
             best_team = team

    best_member_index = np.array(member_index)[best_team]
    list.sort(best_team, reverse=True)
    for i in best_team:
        member_index.remove(member_index[i])
    return best_member_index, member_index

a = np.log(10)
fig = plt.figure()
ax = []
for index, m in enumerate([1,2,3,5]):
    ax.append(fig.add_subplot(2, 2, index+1))
    for n in [16, 32, 64, 128, 256]:
        print(n,m)
        Elo_true = np.random.randn(n) * 400 / np.sqrt(2) + 1500
        Elo_true = Elo_true - (np.mean(Elo_true) - 1500)
        Elo_pred = np.ones(n) * 1500
        l = list(range(n))
        loss = []
        for t in range(20000):
            sample = random.sample(l, 2*m)
            #A_team, B_team = sample[:m], sample[m:]
            team_score = Elo_pred[sample]
            A_team, B_team = team_split(team_score, sample, m)
            
            A_score_true, A_score_pred = np.mean(Elo_true[A_team]), np.mean(Elo_pred[A_team])
            B_score_true, B_score_pred = np.mean(Elo_true[B_team]), np.mean(Elo_pred[B_team])
            
            R_AB_true = A_score_true - B_score_true
            R_AB_pred = A_score_pred - B_score_pred
            W_AB_true = 1/(1+np.exp(-a*R_AB_true/400))
            W_AB_pred = 1/(1+np.exp(-a*R_AB_pred/400))

            s = 1 if W_AB_true > np.random.rand() else 0
            # Adam
            if t==0:
                alpha = 1.0 * m
                beta1 = 0.9
                beta2 = 0.999
                eps=1e-08
                
                g = np.zeros(n)
                u = np.zeros(n)
                v = np.zeros(n)
                w = Elo_pred
                w2 = np.zeros(n)

            if t%m==m-1:
                g[A_team] += (s - W_AB_pred) * 1500
                g[B_team] -= (s - W_AB_pred) * 1500

                u = beta1 * u + (1 - beta1) * g
                v = beta2 * v + (1 - beta2) * g * g
                w = w + alpha * u / np.sqrt(v+eps)
                Elo_pred = w + w2
                g = np.zeros(n)
            else:
                g[A_team] += (s - W_AB_pred) * 1500
                g[B_team] -= (s - W_AB_pred) * 1500
            
            loss.append(np.mean(np.abs(Elo_true-Elo_pred)))

            # KL Divergence
            if t>300 and (t%m==m-1):
                mu = np.mean(Elo_pred)
                sigma = np.std(Elo_pred)/(400/np.sqrt(2))
                mu_new = mu + (1500 - mu) * 0.001
                sigma_new = sigma + (1/sigma - sigma) * 0.001
                w2 += (Elo_pred - mu)*sigma_new/sigma + mu_new - Elo_pred
                Elo_pred = w + w2

        print(Elo_true[:8])
        print(Elo_pred[:8])
        print('last_loss=', loss[-1])
        ax[index].plot(range(len(loss)), loss, label='n=%d,m=%d'% (n,m))
        ax[index].legend()
plt.show()
```

https://qiita.com/omiita/items/1735c1d048fe5f611f80

# 学習率
学習率$\alpha$が高過ぎれば収束は早くてもlossが高い値で収束する確率が高くなるし、学習率が低過ぎればlossが低い値で収束する確率が高くなっても収束は遅くなる。

ランダムマッチングにおける以下の初期$\alpha$の場合の結果を参考までに示す。

```python
alpha = 4.0 * m
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/90b88ef6-4ac6-40cc-4dac-5c88a4f621f4.png)

```python
alpha = 1.0 * m
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/b0a0f3a4-ff61-8ea5-d047-1f9df85af794.png)

```python
alpha = 0.25 * m
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/e54cb6e4-a764-9f73-05b6-b641c70c63d1.png)


# 新規プレイヤー
Adamのu,vは初期値0であり、勾配gが0の限りはずっと0である。
ということはAdamは参加頻度の低いプレイヤーや新規プレイヤーに対してもu,vはあとからでも適切に決められるはずである。


ただ、個人的に休眠プレイヤーに対する扱いが若干気になった。突然ゲームに参加しなくなるとプレイヤーの以降の新規勾配g=0となるが、u,vはしばらくは0にならない。一応、beta1＝0.9でuは徐々にその値を小さくするものの、ゲームに参加しなくなったプレイヤーのレート移動は休止後もAdamのモーメント(慣性)分しばらく続くという事である。


```python
        u = beta1 * u + (1 - beta1) * g
        v = beta2 * v + (1 - beta2) * g * g
        w = w + alpha * u / np.sqrt(v+eps)
```




プレイヤーの総数$r$を以下の様にtに依存して徐々に変える。$t>10000$以降は元の値$n$と同じである。既存プレイヤーもしくは新規プレイヤーのみ学習が進んでないということは無いようである。

```python
        for t in range(20000):
            r = np.minimum(int(4*m+t/10000*(n-4*m)),n)
            sample = random.sample(l[:r], 2*m)
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/a2bf35ff-8ee0-348a-de86-a649cccb0444.png)

# プレイヤーの成長
プレイヤーが突然その能力を覚醒したとする。
この場合、既に安定している筈のレートに対して追従可能かどうか。単純なAdamでは結果は問題なく見える。


```python
            if t==10000:
                Elo_true[:(n//2)] += 100
                Elo_true[(n//2):] -= 100
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/f3ad5e78-62b6-baf7-8c62-2cba5b76ce08.png)


# 学習率スケジュール
以下のコードを足して2000step毎に学習率を0.90倍にする。
このとき収束はそれほど遅くならず、それでいて最終到達lossは前回より良く見える。

```python
            if t>0 and t%2000==0:
                alpha *= 0.90
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/48989e0f-a52a-cc72-593f-d47b927eb55e.png)

しかし、この場合はプレイヤーが後に成長した場合、その成長分のレート移動の更新が学習率の下がった状態では遅くなる。また新規プレイヤーの追加、参加する頻度の低いプレイヤーにおいても学習率の低減は上手く働かない。
このため、学習率の計画的な低減はプレイヤー人数、頻度やそのレートが固定である場合しか上手く行かない。


# プレイヤー毎の試合数カウント
プレイヤーの経験した試合数をカウントしてその試合数30試合毎にプレイヤー毎の学習率を0.90ずつ下げる。ただし、長期間試合に参加しないプレイヤーは経験試合数を徐々に減らして学習率を戻す。もしかしたらAdamの亜種に似たような仕組みがあるのかもしれないが、把握してない。

メリットとしては学習率スケジュールと同じように最終到達lossが小さくなる。懸念は低頻度プレイヤーは学習率を下げる機構が実質ない点である。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/0230fec7-aee7-a1d9-4afd-fbf85e1562d2.png)


```python
            # Adam
            if t==0:
                alpha = 1.0 * m
                beta1 = 0.9
                beta2 = 0.999
                eps=1e-08
                
                g = np.zeros(n)
                u = np.zeros(n)
                v = np.zeros(n)
                w = Elo_pred
                w2 = np.zeros(n)
                b = np.zeros(n)

            if t%m==m-1:
                g[A_team] += (s - W_AB_pred) * 1500
                g[B_team] -= (s - W_AB_pred) * 1500
                b[A_team] += 1/m
                b[B_team] += 1/m
                b         -= 1/n
                b = np.where(b > 0, b, 0)

                u = beta1 * u + (1 - beta1) * g
                v = beta2 * v + (1 - beta2) * g * g
                c = (np.ones(n) * 0.90)**(b//30)
                w = w + alpha * u / np.sqrt(v+eps) * c
                Elo_pred = w + w2
                g = np.zeros(n)
            else:
                g[A_team] += (s - W_AB_pred) * 1500
                g[B_team] -= (s - W_AB_pred) * 1500
                b[A_team] += 1/m
                b[B_team] += 1/m
                b         -= 1/n
```



# 未来の戦績

チーム戦ではプレイヤーをランダムにマッチングするわけではなく、実際には仮想戦力合計レートが近いようにマッチングが行われる。このため強いプレイヤーは弱いプレイヤーと組まされることが必然的に多くなるが、この試合に負けたからと言って強いプレイヤーに責任があるかは必ずしも不明瞭である。たった一人のために残りの四人も責を負う場合、一体誰が戦犯なのかを上手く特定しておかなければレート収束までの回数は効率的とはならなくなるかもしれない。

チーム戦を考えた時、誰が戦犯なのかを特定するようにレートを考えるようにしたい。
戦力均衡のマッチングと仮定すると常に$W_{AB}≒0.5$であり、このイロレーティングはほとんど1次元のランダムウォークに近いと知られている。
過去の試合をピックした場合、その時点では仮想戦力合計レートが近いようにマッチングされているが、実際にはこの時点の仮想戦力はそれほど正確ではない。もし、この時のチームの味方が本当はもっと弱いなら、この時のレート移動に正の補正を足すべきだし、この時のチームの味方が本当はもっと強いなら、この時のレート移動に負の補正を引くべきである。また、この時の相手チームの敵が本当はもっと強いなら、この時のレート移動に正の補正を足すべきだし、この時の相手チームの敵が本当はもっと弱いなら、この時のレート移動に負の補正を引くべきである。(この試合の勝敗結果自体には補正への影響はない)

未来の戦績を考慮するのは過去のこの時点では不可能である。しかしながら(敵プレイヤーのその後の戦績の勝ち越し)-(味方プレイヤーのその後の戦績の勝ち越し)が分かれば後からでも当時の勝率補正を掛けれよう。ここでこのレート移動は1次元のランダムウォークに近いから、過去の試合からの勝ち越し回数は過去のレートと現在のレートの差から求まるはずである。
このように考えれば味方になった回数と味方の時の平均レート、敵になった回数と敵の時の平均レート、および現時点のレートを記録すれば後からでも補正可能ではと考えた。

これはアイデアだけで実装は試してない。


# チーム内の戦力のばらつき度合の考慮
いまチーム分割関数はチーム内のプレイヤー戦力の平均値が等しくなるようにしか考えてない。
例えば二個のチームに分けた時、一つのチームは全員同じ実力でロボットみたいなチームで、もう一つのチームは5人全員の実力がばらばらの斑気(むらけ)のあるチームとする。プレイヤー戦力の平均値が等しいとしてもこの二つのチームを戦わせるとどちらかが大勝、あるいは大敗する可能性が高いのではないだろうか。
このため、チーム内の戦力の平均値が等しい、かつ戦力のばらつきも等しいチーム分割方法を考えたい。ここでばらつきを以下の様に定義したい。

```math
variation=mean(|r_i-mean(r)|)
```
通常のAdamでこれを採用しても結果はあまり変わらない。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/e4fbe7e2-86dc-edc2-0d2a-3c167b81ec76.png)


```python
def team_split(member, member_index, m=5):
    mean_score = np.mean(member)
    variation = np.mean(np.abs(member-mean_score))
    best_score = 10000000
    l = list(range(2*m))
    for i in range(12*m*m):
        team = random.sample(l, m)
        team_mean_score = np.mean(member[team])
        team_variation = np.mean(np.abs(member[team]-team_mean_score))
        score = np.abs(team_mean_score - mean_score) + np.abs(variation-team_variation)/np.sqrt(m)
        if score < best_score:
             best_score = score
             best_team = team

    best_member_index = np.array(member_index)[best_team]
    list.sort(best_team, reverse=True)
    for i in best_team:
        member_index.remove(member_index[i])
    return best_member_index, member_index
```


なお、Trueskillではプレイヤーレートの$\mu$と$\sigma$はマッチング品質に依存するがチーム内の戦力ばらつきはマッチング品質において影響しない。例えば$\mu$が(1200,1600,800)のチームと(1200,1200,1200)のチームのマッチング品質は(1200,1200,1200)のチームと(1200,1200,1200)のチームのマッチング品質と同じである。

```python
import trueskill

mu = 1200.
sigma = 400.
beta = 200.
tau = sigma / 100.
draw_probability = 0.1
backend = None

env = trueskill.TrueSkill(
    mu=mu, sigma=sigma, beta=beta, tau=tau,
    draw_probability=draw_probability, backend=backend)

for i in range(9):
    r0 = env.create_rating(mu=mu, sigma=30)
    r1 = env.create_rating(mu=mu+i*50, sigma=30)
    r2 = env.create_rating(mu=mu-i*50, sigma=30)
    q0 = env.quality(((r0,r0,r0),(r0,r0,r0),))
    q1 = env.quality(((r1,r1,r1),(r1,r1,r1),))
    q2 = env.quality(((r2,r2,r2),(r2,r2,r2),))
    q3 = env.quality(((r0,r1,r2),(r0,r0,r0),))
    print(i*50, q0,q1,q2,q3)
--------------------------------------------------
0 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
50 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
100 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
150 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
200 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
250 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
300 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
350 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
400 0.9889363528682975 0.9889363528682975 0.9889363528682975 0.9889363528682975
```

# ランチェスターの法則
戦力に関する有名な法則にランチェスターの法則がある。


https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%81%E3%82%A7%E3%82%B9%E3%82%BF%E3%83%BC%E3%81%AE%E6%B3%95%E5%89%87

二次法則によれば$(1200,1600,800)$人の3部隊の軍隊と$(1200,1200,1200)$人の3部隊の軍隊とが3つに分かれて戦った後に生き残りが集合して戦うとすると、前者の方が有利で$\sqrt{(1200^2+1600^2+800^2)-3*1200^2}=565.7$人分、前者の軍隊が生き残る。
レートと戦力は同じではないのだが、前述のチーム内の戦力のばらつき度合を整える理由付けにはなるのかもしれない。

# Trueskillとの比較
Eloの集団戦ではなくTrueskillの集団戦を考え、ランダムマッチングと戦力均衡マッチングの時の損失の変化を見てみる。
ランダムマッチングではチーム内人数が多いほど収束が早く、代わりに最終到達損失が大きい。
戦力均衡マッチングではプレイヤー数が少ないと損失が増える場合があり、上記でやったKL Divergence+Adam型の方が安定しているように見える。

・ランダムマッチング
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/911c718b-0c33-de9b-d936-cfd7ab7f343e.png)


・戦力均衡マッチング
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/299928/b8fea127-d905-86e4-6dea-c2a16ab3445e.png)



```python
import numpy as np
import matplotlib.pyplot as plt
import random
import trueskill

def team_split(member, member_index, m=5):
    mean_score = np.mean(member)
    variation = np.mean(np.abs(member-mean_score))
    best_score = 10000000
    l = list(range(2*m))
    for i in range(12*m*m):
        team = random.sample(l, m)
        team_mean_score = np.mean(member[team])
        team_variation = np.mean(np.abs(member[team]-team_mean_score))
        score = np.abs(team_mean_score - mean_score) + np.abs(variation-team_variation)/np.sqrt(m)
        if score < best_score:
             best_score = score
             best_team = team

    best_member_index = np.array(member_index)[best_team]
    list.sort(best_team, reverse=True)
    for i in best_team:
        member_index.remove(member_index[i])
    return best_member_index, member_index

a = np.log(10)
fig = plt.figure()
ax = []
for index, m in enumerate([1,2,3,5]):
    ax.append(fig.add_subplot(2, 2, index+1))
    for n in [16, 32, 64, 128, 256]:
        print(n,m)
        Elo_true = np.random.randn(n) * 400 / np.sqrt(2) + 1500
        Elo_true = Elo_true - (np.mean(Elo_true) - 1500)
        ts_mu_pred = np.ones(n) * 1500
        ts = []
        
        mu = 1500.
        sigma = 400.
        beta = 200.
        tau = sigma / 100.
        draw_probability = 0.1
        backend = None

        env = trueskill.TrueSkill(
            mu=mu, sigma=sigma, beta=beta, tau=tau,
            draw_probability=draw_probability, backend=backend)
        for i in range(n):
            ts.append(env.create_rating())
        
        l = list(range(n))
        loss = []
        for t in range(20000):
            sample = random.sample(l, 2*m)
            #A_team, B_team = sample[:m], sample[m:]
            team_score = ts_mu_pred[sample]
            A_team, B_team = team_split(team_score, sample, m)
            
            A_score_true, B_score_true = np.mean(Elo_true[A_team]), np.mean(Elo_true[B_team])
            R_AB_true = A_score_true - B_score_true
            W_AB_true = 1/(1+np.exp(-a*R_AB_true/400))
            s = (0,1) if W_AB_true > np.random.rand() else (1,0)
            
            if m==1:
                r1, r2 = ts[A_team[0]], ts[B_team[0]]
                (r1,),(r2,), = env.rate(((r1,),(r2,),), ranks=s)
                ts[A_team[0]], ts[B_team[0]] = r1, r2
            if m==2:
                r1, r2, r3, r4 = ts[A_team[0]], ts[A_team[1]], ts[B_team[0]], ts[B_team[1]]
                (r1,r2),(r3,r4), = env.rate(((r1,r2),(r3,r4),), ranks=s)
                ts[A_team[0]], ts[A_team[1]], ts[B_team[0]], ts[B_team[1]] = r1, r2, r3, r4
            if m==3:
                r1, r2, r3, r4, r5, r6 = ts[A_team[0]], ts[A_team[1]], ts[A_team[2]], ts[B_team[0]], ts[B_team[1]], ts[B_team[2]]
                (r1,r2,r3),(r4,r5,r6), = env.rate(((r1,r2,r3),(r4,r5,r6),), ranks=s)
                ts[A_team[0]], ts[A_team[1]], ts[A_team[2]], ts[B_team[0]], ts[B_team[1]], ts[B_team[2]] = r1, r2, r3, r4, r5, r6 
            if m==5:
                r1,r2,r3,r4,r5,r6,r7,r8,r9,r10 = ts[A_team[0]],ts[A_team[1]],ts[A_team[2]],ts[A_team[3]],ts[A_team[4]],ts[B_team[0]],ts[B_team[1]],ts[B_team[2]],ts[B_team[3]],ts[B_team[4]]
                (r1,r2,r3,r4,r5),(r6,r7,r8,r9,r10), = env.rate(((r1,r2,r3,r4,r5),(r6,r7,r8,r9,r10),), ranks=s)
                ts[A_team[0]],ts[A_team[1]],ts[A_team[2]],ts[A_team[3]],ts[A_team[4]],ts[B_team[0]],ts[B_team[1]],ts[B_team[2]],ts[B_team[3]],ts[B_team[4]] = r1,r2,r3,r4,r5,r6,r7,r8,r9,r10

            for i in range(n):
                ts_mu_pred[i] = ts[i].mu

            loss.append(np.mean(np.abs(Elo_true-ts_mu_pred)))

        print(Elo_true[:8])
        print(ts_mu_pred[:8])
        print('last_loss=', loss[-1])
        ax[index].plot(range(len(loss)), loss, label='n=%d,m=%d'% (n,m))
        ax[index].legend()
plt.show()
```

# まとめ
イロレーティングのチーム戦はランダムマッチなら別に特に問題なく考えることが出来る。とはいえランダムマッチにおいてはイロレーティングのチーム戦よりもTrueskillの方が優秀で、かなり高速に収束する。しかし、仮想チーム戦力を均衡させるマッチング操作を加えると収束が遅くなり、場合によっては損失が何故か増大する。

イロレーティングに機械学習的なKL DivergenceとAdamを採用した集団戦のレート戦を検討してみた。