摘要(英) |
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. |
參考文獻 |
[1] Sharad Agarwal, Jacob R. Lorch . (2009). Matchmaking for Online Games and Other Latency-Sensitive P2P Systems. SIGCOMM ’09 Proceedings of the ACM SIGCOMM 2009 conference on Data communication on pages 315-326.
[2] Justin Manweiler, SharadAgarwaly, Ming Zhangy, Romit Roy Choudhury and Paramvir Bahly. (2011). Switchboard: A Matchmaking System for Multiplayer Mobile Games. MobiSys ’11 Proceedings of the 9th international conference on Mobile systems, applications, and services on pages 71-84.
[3] Olivier Delalleau, Emile Contal, Eric Thibodeau-Laufer, Raul Chandias Ferrari, Yoshua Bengio and Frank Zhang. (2012). Beyond Skill Rating: Advanced Matchmaking in Ghost Recon Online. Computational Intelligence and AI in Games, IEEE Transactions on pages 167-177.
[4] R. Herbrich, T. Minka, and T. Graepel. (2007).TrueSkill: A Bayesian skill
rating system. in Advances in Neural Information Processing Systems
19 (NIPS’06), B. Scholkopf, J. Platt, and T. Hoffman, Eds. MIT Press, ¨
2007 on pages 569-576.
[5] A. E. (1978). Elo, The rating of chessplayers, past and present. Batsford.
[6] D. Ramirez-Cano, S. Colton, and R. Baumgarten. (2010).Player classification
using a meta-clustering approach. in Proceedings of the International
Conference on Computer Games, Multimedia and Allied Technology.
[7] R. C. Weng and C.-J.Lin. (2011). A Bayesian approximation method for online
ranking. Journal of Machine Learning Research on pages 267-300.
[8] R. Coulom. (2008). Whole-history rating: A Bayesian rating system for players
of time-varying strength. in Proceedings of the 6th International
Conference on Computers and Games, ser. CG ’08. Berlin, Heidelberg:
Springer-Verla on pages 113–124.
[9] R. Thawonmas and K. Iizuka. (2008). Haar wavelets for online-game player
classification with dynamic time warping. Journal of Advanced Computational Intelligence and Intelligent Informatics, Special issue on
Intelligence Techniques in Computer Games and Simulations on pages
150–155.
[10] F. Dabek, R. Cox, F. Kaashoek, and R. Morris. (2004). Vivaldi: A
decentralized network coordinate system. In Proc.
SIGCOMM Conference on pages 426–437.
[11] Michael T. Goodrich and Roberto Tamassia. (2001). Algorithm Design :Foundations, Analysis and Internet Examples.
[12] Colin DeLong and JaideepSrivastava. (2012). TeamSkill Evolved: Mixed Classification Schemes for Team-Based Multi-player Games.Advances in Knowledge Discovery and Data Mining on pages 26-37
[13] R. C. Weng and C.-J. Lin. (2011). A Bayesian approximation method for online
ranking, J. Mach. Learn. Res on pages 267–300.
[14] S. Nikolenko and A. Sirotkin. (2011). A new Bayesian rating system for team competitions, in Proc. 28th Int. Conf. Mach. Learn on pages 601–608.
[15] P. Dangauthier, R. Herbrich, T. Minka, and T. Graepel. (2007). TrueSkill
through time: Revisiting the history of chess, in Advances in Neural
Information Processing Systems, M. Press, Ed. Cambridge, MA:
MIT Press.
[16] J. S. Tobias Fritsch and B. Voigt. (2008). The next generation of competitive
online game organization, presented at the Netgames,Worcester,MA.
[17] League of Legends. (2010). League of Legends matchmaking,
Available: http://na.leagueoflegends.com/learn/gameplay/Matchmaking.
[18]J. Riegelsberger, S. Counts, S. Farnham, and B. C. Philips. (2007). Personality
matters: Incorporating detailed user attributes and preferences into the
matchmaking process, in Proc. 40th Annu. Hawaii Int. Conf. Syst. Sci on
pages 87.
[19] J. Jimenez-Rodriguez, G. Jimenez-Diaz, and B. Diaz-Agudo. (2011). Matchmaking and case-based recommendations, in Proc. Workshop Case-
Based Reason.Comput. Games/19th Int. Conf. Case Based Reason on
pages 53–62.
[20] R. Thawonmas and K. Iizuka. (2008). Visualization of online-game players
based on their action behaviors, Int. J. Comput. Games Technol. |