Initial commit

1 files changed, 249 insertions, 0 deletions

diff --git a/rank.py b/rank.py
new file mode 100644
index 0000000..c38ad76
--- /dev/null
+++ b/rank.py
@@ -0,0 +1,249 @@
+import math
+
+teams = [
+    "RNG",
+    "EDG",
+    "FPX",
+    "WE",
+    "RA",
+    "TES",
+    "JDG",
+    "SN",
+    "IG",
+    "LNG",
+    "BLG",
+    "V5",
+    "LGD",
+    "TT",
+    "OMG",
+    "ES",
+    "RW"
+]
+
+"""
+We first list a number of game histories
+"""
+matches = [
+    ("TES", "SN", 0, 2),
+    ("OMG", "EDG", 1, 2),
+    ("WE", "RW", 2, 0),
+    ("JDG", "IG", 0, 2),
+
+    ("BLG", "ES", 2, 1),
+    ("TT", "RNG", 0, 2),
+    ("OMG", "FPX", 0, 2),
+    ("RW", "TES", 2, 1),
+    ("WE", "V5", 2, 1),
+    ("LNG", "IG", 2, 0),
+    ("JDG", "BLG", 2, 0),
+    ("RNG", "SN", 2, 1),
+    ("RW", "ES", 0, 2),
+    ("TES", "RA", 2, 0),
+    ("V5", "LGD", 2, 1),
+    ("EDG", "FPX", 2, 1),
+    ("LNG", "TT", 2, 1),
+    ("WE", "IG", 2, 1),
+
+    ("OMG", "ES", 1, 2),
+    ("BLG", "V5", 1, 2),
+    ("RW", "FPX", 0, 2),
+    ("EDG", "LGD", 2, 0),
+    ("IG", "ES", 2, 0),
+    ("SN", "RA", 0, 2),
+    ("TT", "WE", 0, 2),
+    ("OMG", "RNG", 0, 2),
+    ("RA", "BLG", 0, 2),
+    ("EDG", "JDG", 2, 0),
+    ("TES", "LGD", 2, 0),
+    ("FPX", "SN", 2, 0),
+    ("RW", "V5", 0, 2),
+    ("LNG", "WE", 0, 2),
+
+    ("EDG", "TT", 2, 0),
+    ("JDG", "RA", 2, 0),
+    ("RNG", "V5", 2, 1),
+    ("LNG", "BLG", 2, 1),
+    ("ES", "FPX", 0, 2),
+    ("IG", "RW", 2, 0),
+    ("LGD", "BLG", 0, 2),
+    ("OMG", "SN", 0, 2),
+    ("ES", "LNG", 0, 2),
+    ("WE", "RNG", 0, 2),
+    ("TT", "V5", 2, 0),
+    ("IG", "FPX", 0, 2),
+    ("RA", "RW", 2, 0),
+    ("TES", "JDG", 2, 0),
+
+    ("SN", "LGD", 2, 0),
+    ("BLG", "RNG", 2, 1),
+    ("RA", "WE", 2, 0),
+    ("V5", "EDG", 0, 2),
+    ("ES", "TT", 1, 2),
+    ("JDG", "RW", 2, 0),
+    ("IG", "OMG", 2, 0),
+    ("FPX", "LNG", 2, 0),
+    ("LGD", "TT", 2, 0),
+    ("EDG", "SN", 2, 0),
+    ("BLG", "OMG", 1, 2),
+    ("JDG", "WE", 2, 0),
+    ("FPX", "TES", 2, 0),
+    ("LNG", "RA", 0, 2),
+    ("V5", "ES", 2, 1),
+    ("IG", "RNG", 1, 2),
+
+    ("SN", "JDG", 0, 2),
+    ("FPX", "WE", 0, 2),
+    ("BLG", "EDG", 0, 2),
+    ("TES", "LNG", 2, 0),
+    ("TT", "RA", 1, 2),
+    ("WE", "ES", 2, 0),
+    ("OMG", "V5", 0, 2),
+    ("RW", "RNG", 0, 2),
+    ("JDG", "TT", 2, 1),
+    ("IG", "EDG", 2, 0),
+    ("LGD", "RW", 2, 1),
+    ("ES", "TES", 0, 2),
+    ("RNG", "FPX", 2, 0),
+    ("V5", "LNG", 0, 2),
+    ("RA", "OMG", 2, 1),
+    ("SN", "IG", 2, 0),
+
+    ("RW", "EDG", 0, 2),
+    ("FPX", "JDG", 2, 0),
+    ("SN", "TT", 2, 0),
+    ("BLG", "IG", 0, 2),
+    ("ES", "RA", 0, 2),
+    ("LGD", "WE", 0, 2),
+    ("RNG", "LNG", 2, 0),
+    ("OMG", "TES", 0, 2),
+    ("ES", "JDG", 0, 2),
+    ("V5", "SN", 0, 2),
+    ("LNG", "LGD", 2, 1),
+    ("FPX", "RA", 1, 2),
+    ("RNG", "EDG", 2, 1),
+    ("RW", "OMG", 0, 2),
+    ("TT", "BLG", 0, 2),
+    ("IG", "TES", 1, 2),
+
+    ("V5", "JDG", 0, 2),
+    ("RNG", "ES", 2, 0),
+    ("FPX", "LGD", 2, 0),
+    ("TES", "BLG", 2, 0),
+    ("RA", "V5", 2, 0),
+    ("SN", "RW", 2, 0),
+    ("WE", "OMG", 2, 1),
+    ("EDG", "LNG", 2, 0),
+    ("ES", "LGD", 0, 2),
+    ("FPX", "TT", 2, 1),
+]
+
+team_dict = {}
+match_matrix = []
+for idx, name in enumerate(teams):
+    team_dict[name] = idx
+    match_matrix.append([])
+
+team_fac = [0] * len(teams)
+team_cnt = [0] * len(teams)
+
+# choices of different smoothing function
+def naive(team, weight):
+    return weight
+
+def exp(team, weight):
+    N = 5
+    return math.exp(-team_cnt[team]/N) * weight
+
+def normal(team, weight):
+    N = 5
+    return math.exp(-((team_cnt[team]/N)**2)) * weight
+
+def shock(team, weight):
+    N = 5
+    if team_cnt[team] < N:
+        return weight
+    else:
+        return 0
+
+filter_func = shock
+
+for match in reversed(matches):
+    l = team_dict[match[0]]
+    r = team_dict[match[1]]
+
+    # Normalize each match
+    tot = match[2] + match[3]
+    w = filter_func(r, match[2] / tot)
+    team_fac[r] += w
+    match_matrix[l].append([r, w])
+
+    w = filter_func(l, match[3] / tot)
+    team_fac[l] += w
+    match_matrix[r].append([l, w])
+    team_cnt[l] += 1
+    team_cnt[r] += 1
+
+total = 0
+for fac in team_fac:
+    total += fac
+
+total = total/len(teams)
+
+for matches in match_matrix:
+    for m in matches:
+        m[1] /= team_fac[m[0]]
+
+# page rank damping factor
+d = 0.85
+
+rank = [1] * len(teams)
+
+# iterations
+for it in range(100):
+    new_rank = [1 - d] * len(teams)
+    for (idx, matches) in enumerate(match_matrix):
+        for m in matches:
+            new_rank[idx] = new_rank[idx] + d * rank[m[0]] * m[1]
+    rank = new_rank
+
+team_rank = []
+for idx, name in enumerate(teams):
+    team_rank.append((name, rank[idx]))
+
+team_rank.sort(key=lambda x: x[1], reverse=True)
+
+# Tier list using K-mean
+K = 4 # S A B C
+means = [0] * K
+for i in range(K):
+    means[i] = team_rank[i * len(teams)//K][1]
+
+for i in range(1000):
+    # calculate distance
+    cnt = [0] * K
+    tot = [0] * K
+    for rank in team_rank:
+        bidx = 0
+        dist = 10000
+        for idx, m in enumerate(means):
+            if abs(m - rank[1]) < dist:
+                bidx = idx
+                dist = abs(m - rank[1])
+        cnt[bidx] += 1
+        tot[bidx] += rank[1]
+    for k in range(K):
+        means[k] = tot[k] / cnt[k]
+
+print("Result of k-means")
+rank_name = ["S", "A", "B", "C"]
+for idx, m in enumerate(means):
+    print("\t", rank_name[idx], m)
+
+for rank in team_rank:
+    bidx = 0
+    dist = 10000
+    for idx, m in enumerate(means):
+        if abs(m - rank[1]) < dist:
+            bidx = idx
+            dist = abs(m - rank[1])
+    print(rank_name[bidx], rank)
\ No newline at end of file