导语：自走棋是目前市场上最受欢迎的游戏类型之一。在此游戏中，玩家构建自己的游戏阵容，自动与其他玩家进行战斗。游戏中的棋子、羁绊组合种类繁多，对游戏平衡性进行分析极具挑战性。本文以战歌竞技场为例，探讨了自走棋游戏中阵容强度的快速评估方法，研究使用遗传算法进行阵容挖掘。然后，通过遍历不同约束进行阵容挖掘，通过统计所得到的阵容的棋子和羁绊个数，从而帮助游戏开发人员在游戏上线前进行平衡性分析。除此之外，所提出的方法可以推广到其他游戏的平衡性分析。
---
▌引言
自走棋类型游戏是源于2019年初基于自定义的DotaA2定制地图。自走棋游戏是8名玩家从公共牌库购买棋子，并将棋子放置棋盘上，通过合理的阵容安排，最终决出最后的胜者。整个战斗的过程是全部自动的。游戏中的棋子拥有不同的种族和职业划分，包括战士、法师、哥布林、人类等。如果棋盘上相同种族和职业的棋子达到一定的数量时，即会触发羁绊奖励。例如战士将会获得一个Buff来增加所有己方战士的护甲。高星级棋子可以显著提高棋子的战斗力。目前市场上的主流游戏包括腾讯的王者荣耀自走棋、战歌自走棋、巨鸟多多的多多自走棋等。因此自走棋游戏的阵容挖掘及平衡性分析成为游戏开发者的研究课题。
在自走棋游戏中，平衡性是影响玩家体验的最重要因素之一。一款具有良好平衡性的自走棋游戏拥有多套不同的阵容组合，玩家可以根据所抽到的棋子进行合适的组合进行游戏。如果平衡性不好，所有玩家都会倾向组合同一套阵容，从而使得难以组合成型，从而影响玩家的操作体验。多样化和平衡的阵容会带给玩家新奇感，给与有经验的玩家更大的操作空间，可以保持良好的游戏活跃度。
自走棋平衡性分析虽然非常重要，但是在实际的体验中有非常多的困难需要克服。首先，自走棋一般包含200多个不同星级的棋子，以及20多个不同种类的种族和职业，一旦某个棋子或者职业得到加强，就会影响到众多阵容组合，难以进行量化和分析。其次，自走棋是八位玩家进行多轮比赛从而决出胜负，因此有必要对阵容的实力进行综合的考量。最后，不同的棋子和羁绊拥有不同的特殊效果，很难进行量化表述。
本研究的目的就是通过阵容挖掘，找到在不同约束条件下的最强阵容，并且通过分析异常阵容调整棋子及羁绊，从而提高游戏平衡性。除此之外，还可以通过阵容挖掘算法进行玩家实时阵容推荐。本文的所有数据和实验都是基于腾讯的战歌自走棋为例进行。该款游戏在国际市场上取得了成功，在中国、韩国、泰国等多个国家拥有众多玩家。
---
▌研究方法
为了解决平衡性问题，首先需要确定一个阵容强度评价系统。只有一个合理的阵容强度评价系统，才能为阵容挖掘制定评价依据。除此之外我们需要找到一个合适的阵容挖掘算法，该算法可以在不同的约束条件下，例如等级、花费、羁绊等约束下找到最强的阵容组合。最后根据挖掘出来的阵容进行统计，从而对较强的羁绊和棋子进行调整，整体过程如图1所示。
[图1 阵容挖掘系统整体流程]
图1首先建立了一个阵容强度评估系统，该系统使用历史阵容或者随机阵容的强度作为训练数据。神经网络模型经过训练可以快速得到阵容的强度预测。快速的阵容强度预测是挖掘算法的关键。
当训练好阵容评估模型后，首先确定挖掘的约束条件，例如花费、棋子数等。挖掘算法在约束下利用阵容评估模型进行阵容强度评估，通过多轮迭代从而得到较强的阵容。通过对花费及羁绊的遍历条件下，如果发现某个羁绊的出现频率明显高于其他羁绊，那么可以认为该羁绊过于强大需要在上线前进行调整。该系统除了可以应用于平衡性调整之外，还可以应用于阵容推荐，玩家托管等方面，具有良好的应用前景。
-A.阵容评估模型
由于自走棋阵容强度影响因素众多，所以其评价模型非常复杂，直接采用棋牌类游戏的评价模型比较困难。阵容强度需要综合考虑，一个阵容不能因为克制另外一个阵容而获得较高的阵容强度。一个阵容需要更平衡表现才能得到更高的强度。本研究中提取玩家历史对战阵容最常用的前1000套阵容。当一套阵容需要评估其强度时，将其对战提取出来的提取的1000套阵容从而计算该胜率，胜率越高证明该阵容强度越高。单核CPU上完成1000次对战大概需要花费5分半钟。因此我们采用分布式计算机集群进行并行计算，所得到的阵容强度结果保存到数据库中，以备后续模型训练。
[图2 分布式阵容强度计算]
在明确了阵容强度评价衡量标准后，接下来的步骤就是选择适合的特征作为阵容评估神经网络模型的输入。特征选择是模型训练效果的关键，如果选取不适合的特征，模型难以收敛。棋子时游戏中最为重要的因素，而血量魔法及攻击力与棋子特征紧密挂钩，并且棋子的历史胜率在版本上线前无法取得，因此只将棋子作为输入特征。在本项目中，为了综合考虑羁绊的作用，将在不同羁绊作用下的相同棋子定义为不同的棋子。在不同羁绊的影响下，阵容实力完全不同。在这个版本的战歌竞技场中，棋子等级和羁绊组合总共有2012种可能性。将2012维向量定义为模型输入。当某种羁绊作用下的棋子上场时，相应的位置编码被设置为1。编码示意图如图3所示。经过上述编码后，能够全面反映棋子的羁绊生效状况，从而有效地提高了阵容强度预测的准确性。阵容强度模型是一种回归模型，因此选择了深度神经网络模型进行阵容强度评价，能够表达高度复杂特征之间的非线性关系。
[图三：棋子阵容模型编码]
-B.基于遗传算法的阵容挖掘算法
遗传算法（GA）是一种模拟自然选择的生物进化过程的计算模型。它通过模拟自然进化过程来寻找最优解。它的主要特点是不受导数和函数连续性的限制。此外，它具有并行性和良好的全局优化能力，不需要一定规则的概率优化方法，能够自动获取并引导优化后的搜索空间自适应调整搜索方向。遗传算法以群体中的所有个体为目标，使用随机化技术指导编码参数空间的有效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作，而参数编码、初始种群设置、适应度函数设计、遗传操作设计和控制参数设置五个要素构成了遗传算法的核心内容，如图4所示。
[图4 遗传算法主要流程]
在战歌竞技场阵容挖掘中，针对性地对遗传算法进行调整和优化，以获得所需的结果。对于遗传算法来说，羁绊是否生效与遗传算法没有直接的关系，因此遗传算法编码是直接基于棋子进行。在传统的遗传算法中，初始种群设置是按一定概率随机产生的。然而，对于战歌竞技场阵容挖掘来说，一个纯粹随机生成的初始种群会导致挖掘速度变慢。挖掘之前确定棋子的个数。如果棋子个数限制为8，则初始个体从162个编码中选择8个棋子。此方法减少了遗传算法的迭代次数和时间。通过上面得到的阵容评价模型对生成的阵容进行评价，如果阵容强度更强，这样它在进化中就有更大的交叉和变异选择机会。以这种方式迭代进化，最终得到一个近似最优解。如果一个阵容不满足约束条件，它的适应度函数被设置为0.01，以加强个体的约束并保持特定的种群多样性。在初始群体产生后，根据个体的适应度选择个体，并基于基因进行交叉和突变。
交叉是指两个个体之间基因编码的交换，而突变是指单个个体的编码随机变化。由于自走棋阵容挖掘的特点，其遗传个体需要满足棋子总数的约束。在交叉时，两个个体需要在基因中选择一个合适的位置进行交换，这样杂交后棋子的数量不会发生变化。当突变从一个基因上取下编码为1和0的位置并将其逆转时，也需要获得恒定数量的片段。遗传算法的控制参数需要根据实验结果进行优化，以达到效率和结果的平衡。
---
▌实验结果
-A.阵容评价模型
本文提取了一千个未经训练的阵容，并计算了比赛的实际胜率和由评估模型得出的胜率。数据绘制在图5中。横坐标是真实的胜率，纵坐标是预测的胜率。理想的预测结果应该是45°斜线。然而，由于预测误差，实际点位于45°斜线的两侧。尽管如此，所有的点都更接近理想值，证明具有较好的预测效果。其中，胜率接近1和0两端时预测结果最好，中间值的预测效果较差。图中上下虚斜线表示预测偏差范围为±0.06。97%阵容强度预测值与真实值误差在0.06范围内。预测精度满足下一步遗传算法挖掘的要求。
[图5 阵容预测胜率与真实胜率关系]
-B.阵容挖掘分析
一般来说，遗传算法需要多次迭代。随着迭代次数的增加，它可以逐渐收敛到区域最优解，但在接近最优解时会振荡。图6描述了迭代次数和阵容强度之间的关系。遗传算法进入第100轮迭代后，阵容强度趋于稳定。
在使用遗传算法挖掘阵容时，需要确定阵容的约束条件，因为玩家在组合阵容时，抽取概率的存在以及总成本也有限。四费和五费棋子最高仅为二星，一个阵容中的三星棋子不超过两个，且三星棋子必须是花费最低的棋子。只有在满足上述约束条件的情况下，挖掘出的阵容才与玩家的实际情况相一致。历史玩家阵容强度和遗传算法挖掘得到的阵容强度关系如图7所示。
[图6 阵容强度与遗传算法迭代轮数的关系]
[图7 历史阵容强度与挖掘得到阵容强度的对比]
如图7所示，当棋子个数为10个时，历史阵容与挖掘得到的阵容强度比较。图中显示，最高阵容强度随着花费的增加而增加。该阵容挖掘算法具有很强的优势，挖掘所得到的阵容强于绝大部分历史阵容，该算法可以有效地帮助游戏开发者优化游戏平衡。然而，随着成本的增加，该算法的优势并不明显，但仍然比95%的历史阵容强。
然而，上述算法得到的结果会有一定的随机性。经过多次迭代，它们将趋向于单一羁绊阵容。事实上，得到的结果可能是局部最优的。如果能对每一职业和每一种族进行遗传算法计算，这将产生更好的效果。因此，使用分布式计算进行羁绊遍历。每台计算机负责在单个种族或职业约束下进行挖掘。经过多轮迭代，汇总所有计算结果，可以得到一个趋于全局最优解的阵容。使用分布式计算的羁绊遍历挖掘阵容强度高于不进行遍历的挖掘算法。
-C.平衡性分析
[图 8 不同种族及职业的使用率]
图8显示了挖掘后所得到的阵容和玩家历史最常使用的Top300阵容之间的种族和职业的使用率差异。从阵容挖掘得到的阵容在玩家历史阵容分布上具有一定的相似性。其中，Race0、Race2、Race7和Class1在挖掘得到阵容和历史阵容中的使用率较高，这表明该羁绊更强，有必要削弱该羁绊。而阵容中Class4和Class8使用率很低，有必要对其进行增强。
阵容平衡分析值得广泛研究，需要综合考虑棋子和羁绊的平衡。该阵容强度评估模型和阵容挖掘方法为开发人员提供了参考。游戏新版本发布前可以利用该技术预测棋子和羁绊的强度，为游戏开发者提供理论和技术支持。
---
▌总结
本文针对自走棋类型游戏进行平衡性分析进行研究，以参考阵容为基准，以待评价阵容对参考阵容的胜率作为阵容强度。将大量阵容及强度作为输入，训练深度神经网络模型得到了一个阵容强度评价模型。使用阵容评价模型的结果作为适应度函数，利用遗传算法进阵容挖掘和优化。最后，得到了多约束条件下的阵容挖掘结果。挖掘得到阵容的表现优于现有的历史阵容。游戏开发者可以使用获得的阵容来优化游戏棋子和羁绊，并在游戏发布前进一步调整整体平衡。
参考文献：
1. Aung, V. Bonometti,A. Drachen, et al. “Predicting skill learning in a large, longitudinal moba dataset,”IEEE Conference on Computational Intelligence and Games, 2017.
2. Katona, R. Spick,V. J. Hodge, et al. “Time to die: death prediction in dota 2 using deeplearning,” IEEE Conference on Games, 2019.
3. Yang, Qin T, Y. H.Lei. “Real-time esports match result prediction,” arXiv preprintarXiv:1701.03162, 2016.
4. Kalyanaraman. “Towin or not to win? A prediction model to determine the outcome of a DotA2match,” Technical report, University of California San Diego, 2014.
5. Kinkade, L. Jolla,and K. Lim. "Dota 2 win prediction." Univ. California, Tech. Rep.2015.
6. Hodge, S. Devlin,N. Sephton, et al. “Win prediction in esports: Mixed-rank match prediction inmulti-player online battle arena games,” arXiv preprint arXiv:1711.06498, 2017.
7. Wang, W. Shang.“Outcome prediction of DOTA2 based on Naïve Bayes classifier,” 16thInternational Conference on Computer and Information Science, pp.591-593, 2017.
8. E. Almeida, R. C.Correia, D. M. Eler, et al. “Prediction of winners in MOBA games,” 12th IberianConference on Information Systems and Technologies, pp. 1-6, 2017.
9. Porokhnenko, P.Polezhaev, A. Shukhman. “Machine Learning Approaches to Choose Heroes in Dota2,” 24th Conference of Open Innovations Association, pp. 345-350, 2019.
10. Y. Wang, J. J.Zhang, X. Zheng, et al. “Where does AlphaGo go: From church-turing thesis toAlphaGo thesis and beyond,” IEEE/CAA Journal of Automatica Sinica, vol. 3(2),pp. 113-120, 2016.
11. F. Sironi, M. H. M.Winands. “Analysis of self-adaptive monte carlo tree search in general videogame playing,” IEEE Conference on Computational Intelligence and Games, 2018.
12. Świechowski, T.Tajmajer, A. Janusz. “Improving hearthstone ai by combining mcts and supervisedlearning algorithms,” IEEE Conference on Computational Intelligence and Games,2018.
13. Bravi, D. Perez-Liebana,S. M. Lucas, et al. “Shallow decision-making analysis in general video gameplaying,” IEEE Conference on Computational Intelligence and Games, 2018.
14. Jiang, K. Li, B.Du, et al. “DeltaDou: expert-level doudizhu AI through self-play,” Proceedingsof the 28th International Joint Conference on Artificial Intelligence,pp.1265-1271, 2019.
15. Zhang, H. Pan, Q.Fan, et al. “GBDT, LR \& Deep Learning for turn-based strategy game AI,”IEEE Conference on Games, 2019.
16. G. Diaz, P. Perry,R. Fiebrink. “Interactive machine learning for more expressive gameinteractions,” IEEE Conference on Games, 2019.
17. Yang, D. L.Roberts. “Knowledge discovery for characterizing team success or failure in (A)RTS games,” IEEE Conference on Computational Inteligence in Games, 2013.
18. F. Gudmundsson, P.Eisen, E. Poromaa, et al. “Human-like playtesting with deep learning,” IEEEConference on Computational Intelligence and Games, 2018.
19. J. Kim, C. W. Ahn.“Hybrid fighting game AI using a genetic algorithm and Monte Carlo treesearch,” Proceedings of the Genetic and Evolutionary Computation ConferenceCompanion, pp.129-130, 2018.
20. J. Nielsen, M.Scirea. “Balanced map generation using genetic algorithms in the siphonboard-game,” International Conference in Software Engineering for DefenceApplications, pp. 221-231, 2018.
21. Morosan, R. Poli.“Speeding up genetic algorithm-based game balancing using fitness predictors,”Proceedings of the Genetic and Evolutionary Computation Conference Companion,pp.91-92, 2017.
