竞技游戏中的ELO算法与匹配算法研究

作     者：王瑞 

作者单位：安徽大学 

学位级别：硕士

导师姓名：吴建国

授予年度：2019年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：ELO算法 收敛速度 匹配算法 MOBA游戏 邻域匹配算法 

摘      要：随着网络通信技术的高速发展和人们生活水平的提高,以及移动设备的快速普及,越来越多的人开始在网络上或者是移动设备上进行各类游戏和比赛项目。现如今,在很多游戏平台中,例如棋类、台球、斗地主等游戏中,人们需要一种有效的排名体系,用来评判玩家或者是参与者在游戏或者比赛中展示的实力。现在竞技游戏中常用的排名算法就是国际象棋中的ELO算法。在有了比较准确的实力得分后,匹配系统就可以根据玩家的实力分进行匹配,从而帮助玩家找到合适的队友和对手。网络游戏的发展同样也推动了匹配系统的发展,目前游戏中常用的匹配算法有根据实力分组匹配算法和根据玩家角色进行分组的匹配算法。本文为了克服ELO算法运用在竞技游戏中收敛速度过慢的缺陷,采用了模拟实验的方法检测ELO算法的性能,选取了 3项基本指标:收敛速度,收敛半径,收敛密度,在此基础上对ELO算法进行性能检测。并根据实际需求提出了改进后的ELO算法,该算法引入连胜阈值与连胜奖励,经模拟实验检测,并与改进前的ELO算法进行比较,发现收敛速度有了明显提升。同时将改进后的ELO算法运用在围棋棋盘模式提取中,设计了模式提取规则,用两种ELO算法分别对棋谱数据进行了 LCP模式提取,获得了两套不同的局部棋盘情况下落子的ELO分,并根据模拟实验证明了改进ELO算法提取到更好的LCP模式。同时为了优化传统的线上匹配算法的效果,对传统的匹配算法进行研究,并提出了贪心匹配算法和邻域规划匹配算法。贪心匹配算法主要有三个机制:匹配容量检查、替换机制、半衰机制,并期待用实验证明该算法对比传统分组匹配算法的优势。邻域规划算法则根据匹配系统设计了算法模型,把不同的匹配目标通过不同系数组合成目标函数,同时根据邻域搜索算法进行迭代计算,可以有效提升匹配的寻优效率,同时用贪心算法的半衰机制进行时间上的约束。本文对一款国内MOBA游戏一台服务器上18年3月11日存储的2个多小时大约2000场5v5组队匹配数据作为实验数据,将其用在贪心匹配算法和邻域规划匹配算法上面,与实际线上分组匹配算法进行比较,二者相对于当时使用的算法都能获得较好的匹配结果。