在多人連線遊戲(Multiplayer Online Games)中，自動匹配(Matchmaking)的定義為將多位玩者(player)匹配在一起共同進行遊戲的程序。目前自動匹配將玩者匹配在一起的準則可以分為兩大類：Connection Based與Skill Based。前者將一群彼此網路互相連線速度較快的玩者匹配在一起進行遊戲 而後者則將一群彼此技能評分(Skill Rating)接近的玩者匹配在一起進行遊戲。本論文首先提出一項稱為Association Based的玩者匹配準則，並依此準則提出一個新的自動匹配演算法LOM (Leader-Oriented Matchmaking)來匹配系統中所有的玩者。在Association Based準則下，關聯度(Association)較高的玩者被匹配在一起進行遊戲，關聯度代表兩位玩者之間的關聯程度，例如玩者在遊戲中之個人檔案(profile)的相關程度。LOM使用到了Minimum Cost Maximum Flow演算法的概念，以最佳化的方式來匹配系統中的玩者。值得一提的是，LOM亦可套用於現存的Connection Based與Skill Based玩者匹配準則，並皆可依照個別匹配準則的需求輸出最佳的結果。我們針對LOM與基本的貪婪式玩者匹配演算法及隨機玩者匹配演算法進行模擬與分析，以評估其效能。我們發現，隨機玩者匹配演算法的執行時間複雜度最低，但產生出來的平均關聯度不佳。貪婪式玩者匹配演算法的執行時間複雜度較高，產生出的平均關聯度較佳。雖然LOM執行時間複雜度最高，但可產生最佳的平均關聯度。 In Multiplayer Online Games, the definition of the term Matchmaking is a process that arranging players for online play sessions. Currently, Matchmaking arranging players together according to two types of criteria Connection Based and Skill Based. In Connection Based criterion, players with higher mutual network connection speed are arranged together. In Skill Based criterion, players with close value of Skill Rating are arranged together. In this paper, we propose a new criterion. Also, according to proposed criterion, we propose a new Matchmaking algorithm to arrange players together. Proposed new criterion called “Association Based”. In this criterion, players with higher Association to each others are arranged together. Proposed new Matchmaking algorithm called “LOM”(Leader-Oriented Matchmaking). It uses the concept of Minimum Cost Maximum Flow algorithm to arrange players in optimized way. It is worth mentioning that abovementioned two existing criteria, Connection Based and Skill Based, both of them can be substituted into LOM. And they are also able to acquire the optimized execution result with respect to their requirements. Besides, we did simulation to make comparisons between LOM, Greedy and Random. As for the result, the time complexity of Random is the lowest but it produces the worst average Association. The time complexity of Greedy is higher and it produces better average Association. Although the time complexity of LOM is highest, it produces the best average Association.
