LOM-領隊導向多人連線遊戲自動匹配演算法 Adaptive Computing and Networking Lab National Central University Department of Computer Science and Information Engineering 研究生: 宋管翊 指導教授: 江振瑞 博士 2013/07/11

OUTLINE 序論 相關研究 提出方法 模擬 結論 問題定義 解法 Adaptive Computing and Networking Laboratory

序論 多人連線遊戲(Multiplayer Online Games) 讓多位玩者(Players)透過網路，連線在一起進行遊戲的一種遊戲模式。 玩者之間的互動種類有： 敵對(Rivalry) 競爭(Competition) 合作(Partnership) 知名多人連線遊戲Uncharted 3 : Drake’s Deception Adaptive Computing and Networking Laboratory

序論 自動匹配(Matchmaking) ‧‧‧‧ Matchmaking ‧‧‧‧ 在多人連線遊戲中，其定義為： 將多位玩者匹配在一起，共同進行遊戲的過程。 ‧‧‧‧ Matchmaking Lobby 1 Lobby 2 Lobby N ‧‧‧‧ Adaptive Computing and Networking Laboratory

序論 現存二大匹配玩者準則： ‧‧‧‧ ‧‧‧‧ Connection Based Skill Based 將互相連線速度較快的玩者匹配在一起進行遊戲。 Skill Based 將技能評分(Skill Rating)較接近的玩者匹配在一起進行遊戲。 Lobby 1 Lobby 2 Lobby N ‧‧‧‧ Lobby 1 Lobby 2 Lobby N ‧‧‧‧ Adaptive Computing and Networking Laboratory

序論 本論文針對玩者互動種類中的合作(Partnership)，提出一項新的玩者匹配準則： ‧‧‧‧ Association Based 將一群關聯度高的玩者匹配再一起進行遊戲。 例如： 玩者過去互動的緊密程度。 玩者的默契高低。 玩者個人檔案(profile)的相關程度。 Lobby 1 Lobby 2 Lobby N ‧‧‧‧ Adaptive Computing and Networking Laboratory

序論 並依Association Based玩者匹配準則，提出一項自動匹配演算法Leader-Oriented Matchmaking(LOM)： 使用到Minimum Cost Maximum Flow演算法的概念。 以最佳化的方式去匹配系統中的玩者。 亦可套用於Connection Based與Skill Based準則中去匹配玩者。 ‧‧‧ Adaptive Computing and Networking Laboratory

相關研究 Matchmaking for Online Games and Other Latency-Sensitive P2P Systems 發表於2009年SIGCOMM ’09 使用球體狀的維瓦第網路座標系統，來估計玩者之間的互相連線速度。 Beyond Skill Rating: Advanced Matchmaking in Ghost Recon Online 發表於2012年Computational Intelligence and AI in Games, IEEE Transactions 從玩者的個人檔案(Profile)與記錄檔(Log)取出一些資訊，再將之代入類神經網路模型中，來預估出他和各玩者進行比賽的勝率是多少，再將一群勝率接近0.5：0.5的玩者匹配在一起進行遊戲。 Adaptive Computing and Networking Laboratory

提出方法(問題定義) ‧‧‧‧‧ n 系統中有n位玩者想進行遊戲。 此遊戲需要玩者分成若干隊。 Adaptive Computing and Networking Laboratory

提出方法(問題定義) ‧‧‧ ‧‧‧ ‧‧‧ 每一隊皆需i人。 i人 i人 i人 Adaptive Computing and Networking Laboratory

提出方法(問題定義) k n-k n 我們先從n位玩者中推派k個隊長，其中k= ‧‧‧ ‧‧‧ Adaptive Computing and Networking Laboratory

提出方法(問題定義) k n-k n 每位隊長需在這n-k位剩下的玩者中各選出i-1位來當自己的隊員。 ‧‧‧ ‧‧‧ Adaptive Computing and Networking Laboratory

提出方法(問題定義) 每位隊長和隊員間皆存在可以代表他們之間關聯度高低之值，稱為Association Factor，值愈小代表關聯度愈高。 k ‧‧‧ ‧‧ n n-k ‧‧ ‧‧ ‧‧‧ Adaptive Computing and Networking Laboratory

提出方法(問題定義) ‧‧‧ i-1 i-1 i-1 因此我們的目標為： 1.為每位隊長分配i-1位隊員。 2.最小化系統中之Association Factor的平均值。 ‧‧‧ ‧‧‧ ‧‧‧ ‧‧‧ i-1 i-1 i-1 Adaptive Computing and Networking Laboratory

提出方法(解法) S T 先讓隊長和隊員節點形成一完全二分圖(Complete Bipartite Graph)。 再新增二個虛擬節點S和T，讓S去連到所有隊長，T去連到所有隊員。 Fully Connected S ‧‧‧ ‧‧‧ ‧‧‧ T ‧‧‧ Adaptive Computing and Networking Laboratory

提出方法(解法) S T 定義邊上的權重值為二維向量(CP,AF)。其中： AF(Association Factor)=兩節點間的關聯度。 有了下圖後，我們可將之視為Minimum Cost Maximum Flow的問題。 (1, AF) (1, AF) (1, 0) (i-1, 0) (1, AF) (1, 0) (i-1, 0) (1, AF) ‧‧‧ (1, 0) S ‧‧‧ T ‧‧‧ (1, AF) ‧‧‧ ‧‧‧ (1, 0) (i-1, 0) (1, AF) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (0/1,1) (1,1) (0/1,2) (0/1,0) (1,2) (1,0) (0/2,0) (0/1,10) (2,0) (1,10) (0/1,0) (1,0) (0/1,20) (1,20) S (0/1,0) T S (1,0) T (0/1,12) (1,12) (0/1,0) (1,0) (0/2,0) (0/1,10) (2,0) (1,10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (0/1,1) (1/1,1) (1,-1) (1,1) (0/1,2) (0/1,0) (1/1,0) (1,2) (1,0) (1,0) (0/2,0) (1/2,0) (0/1,10) (1,0) (2,0) (1,10) (0/1,0) (1,0) (0/1,20) (1,20) (1,0) S (0/1,0) T S (1,0) T (0/1,12) (1,12) (0/1,0) (1,0) (0/2,0) (0/1,10) (2,0) (1,10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (1/1,1) (1,-1) (1,-2) (0/1,2) (1/1,2) (1/1,0) (1,2) (1,0) (1,0) (1/2,0) (2/2,0) (0/1,10) (2,0) (1,0) (1,10) (0/1,0) (1/1,0) (1,0) (1,0) (0/1,20) (1,20) (1,0) S (0/1,0) T S (1,0) T (0/1,12) (1,12) (0/1,0) (1,0) (0/2,0) (0/1,10) (2,0) (1,10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (1/1,1) (1,-1) (0/1,2) (1/1,2) (1/1,0) (1,-2) (1,2) (1,0) (1,0) (2/2,0) (1/1,10) (0/1,10) (2,0) (1,-10) (1,10) (1/1,0) (1,0) (1,0) (0/1,20) (1,20) S (0/1,0) (1/1,0) T S (1,0) (1,0) T (1,0) (0/1,12) (1,12) (0/1,0) (1,0) (0/2,0) (1/2,0) (0/1,10) (1/1,10) (2,0) (1,0) (1,10) (1,-10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (1/1,1) (0/1,1) (1,-1) (1,1) (0/1,2) (1/1,0) (1,2) (1,0) (1,0) (2/2,0) (1/1,10) (2,0) (1,-10) (1/1,0) (1,0) (1,0) (1/1,20) (0/1,20) (1,-20) (1,20) S (1/1,0) T S (1,0) T (1,0) (0/1,12) (1/1,12) (1,-12) (1,12) (0/1,0) (1/1,0) (1,0) (1,0) (2/2,0) (1/2,0) (1/1,10) (2,0) (1,0) (1,-10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

提出方法(解法) 我們以S為流量網路的起點，T為流量網路的終點。 用Successive Shortest Paths Algorithm解之。 每次從剩餘網路(Residual Network)找出一條從S到T中成本最低的路徑，並沿著它送出一條最大且可容納於此路徑的網路流，再來更新剩餘網路的資訊，直到從剩餘網路中找不到一條可以從S通到T的路徑為止。 已被證明可得最佳解。 例如： Flow Network Residual Network (0/1,1) (1,1) (0/1,2) (1/1,0) (1,2) (1,0) (1,0) (2/2,0) (1/1,10) (2,0) (1,-10) (1/1,0) (1,0) (1,0) (1/1,20) (1,-20) S (1/1,0) T S (1,0) T (1,0) (1/1,12) (1,-12) (1/1,0) (1,0) (1,0) (2/2,0) (1/1,10) (2,0) (1,-10) (0/1,100) (1,100) (0/1,200) (1,200) Adaptive Computing and Networking Laboratory

模擬 比較對象： 比較方式 L2M Greedy M2L Greedy Random 執行結果的好壞。 執行時間之複雜度。 ‧‧‧ ‧‧‧ ‧‧‧ ‧‧‧ ‧‧‧ ‧‧‧ Adaptive Computing and Networking Laboratory

模擬 隊員和隊長間之關聯度呈平均分佈(Uniform Distribution)。 Adaptive Computing and Networking Laboratory

模擬 隊員和隊長間之關聯度呈常態分佈(Normal Distribution)。 Adaptive Computing and Networking Laboratory

模擬 各演算法的執行時間複雜度。 為何LOM需要 ? Successive Shortest Paths Algorithm 在LOM 中: : 總網路流量數 : 總邊數 : 總點數 Adaptive Computing and Networking Laboratory

模擬 各演算法的執行時間模擬結果。 硬體規格為： AMD Phenom(tm) 9650 Processor 2.41 GHZ、2.00 GB Memory、Windows XP32 bits Adaptive Computing and Networking Laboratory

結論 在此論文中，我們首先提出了一項新的應用於自動匹配的玩者匹配準則，稱為Association Based，並依此準則提出了一項新的自動匹配演算法Leader-Oriented Matchmaking(LOM)。 在Association Based中，關聯度較高的玩者被匹配在一起進行遊戲。 LOM使用到Minimum Cost Maximum Flow演算法的概念，以最佳化的方式去匹配系統中的玩者。 我們做了模擬與分析，發現LOM能產生最佳的平均關聯度，但執行時間複雜度較高。 Adaptive Computing and Networking Laboratory

Q&A Thank you for listening and participating. Adaptive Computing and Networking Laboratory