机器学习技术在游戏中的应用研究――解决鼠标轨迹识别问题

摘要：通过赋予游戏中智能体识别鼠标轨迹的能力，提高了游戏的可操作性，增加了游戏的趣味性。鼠标轨迹识别属于多分类问题，该文提出的解决方案是采用BP神经网络和支持向量机(SVM)求解8种鼠标轨迹的识别问题，并且完成了实验对比，封闭测试中两种方法对鼠标轨迹的正确识别率分别为93.75%和98.75%。

关键词：游戏；轨迹平滑；鼠标轨迹识别；BP神经网络；支持向量机

中图分类号：TP18文献标识码：A文章编号：1009-3044(2011)13-3100-03

Application on the Research of Machine Learning Techniques in Games

LIU Tian-bai, ZHANG Shu-bai

(The 28 Research Institute of China Electronics Technology Group Corporation, Nanjing 210007, China)

Abstract: Through attaching the ability of recognizing mouse track to agent in games, the controlling of games is simplified and the interesting of games is improved. Mouse track recognition is a multi-classification problem, which is resolved by BP neural network and Support Vector Machine (SVM), the number of mouse track patterns is 8, according to contrastive analysis of BP neural network and SVM, the precision is 93.75% and 98.75% respectively.

Key words: games; track smoothing; mouse track recognition; BP neural network; support vector machine

近年来，游戏的图形质量已发展到近乎极致的地步，人工智能(AI)已经成为决定一款游戏以及游戏开发工作室命运的重要因素。下一代的3D游戏不仅会有优秀的视觉效果，更会像人一样狡猾和聪明[1]。游戏中人工智能下一个大的变革就是机器学习理论[2]，将来的游戏角色应该能够进化、学习以及推理。

鼠标轨迹识别可以增加游戏的趣味性，更加方便玩家的操作，使得玩家不需要记忆大量的快捷键来进行各种各样的操作。在国产RPG游戏“刀剑封魔录”中[3]，玩家控制角色的必杀技是通过鼠标轨迹的识别来发出的，对于角色“霜刀女侠”来说，当玩家在屏幕上画出“>”轨迹后，“霜刀女侠”首先识别该轨迹，然后会发出必杀技“天女散花”，画出“M”的话发出必杀技“洛神凌波”等。

出于商业上的原因，“刀剑封魔录”中的解决方案无从得知，本文提出的解决方案是利用机器学习中的BP神经网络和支持向量机技术来解决游戏中智能体的鼠标轨迹识别问题。由“刀剑封魔录”可知在游戏中加入鼠标轨迹识别会带给游戏更多的趣味性，同时使用机器学习技术可以赋予游戏角色学习和推理的能力，因此本文的解决方案有一定的实际应用价值。

1 实验数据的获取方法

由于游戏中该问题的特殊性，没有开放式的数据集可以使用，因此实验数据采用自主获取的方式获得。

1.1 鼠标轨迹的组成

每个鼠标轨迹由12个相互连接的单位向量组成，图1所示是一个“W”字形鼠标轨迹。

其中12个单位向量首尾相连（首向量和尾向量除外），则一条鼠标轨迹一共有13个点组成，这12个单位向量作为神经网络和SVM的输入。

1.2 鼠标轨迹数据的获取

以图1所示的“W”形鼠标轨迹为例，鼠标轨迹数据获取的方法如下：

1）按下鼠标左键不放并且不移动鼠标，记下鼠标此时在屏幕中的坐标，记为 (xhead,yhead) ；

2）移动鼠标划出“W”的形状，在移动鼠标的过程中会产生很多中间点，记录下鼠标在这些中间点的屏幕坐标，记为(xi,yi)，其中0

3）划完“W”轨迹之后释放鼠标，并记下释放鼠标时的终点屏幕坐标，记为(xtail,ytail)；

4）对划出的轨迹进行平滑，使得该轨迹的点数限制为13个（即12个向量），平滑方法如下：

如果n+2

如果n+2=13，轨迹有效，不需要平滑，直接计算每一个向量并且归一化；

如果n+2>13，轨迹有效，需要平滑，使得鼠标轨迹的点的个数减少到13个，平滑的具体方法是，查询10个向量（首尾向量除外）中长度最短的一个，用该向量的中点代替两个端点，然后重复这个过程直到鼠标轨迹点的个数等于13个为止；

5）起始点记为(x1,y1)，终点记为(x13,y13)，中间点记为(xi,yi)，其中2≤i≤12，那么该轨迹的12个向量为j，其中1≤j≤12，jx = xk-xk-1，vjy = yk -yk-1，2≤j≤13；归一化所有12个向量，即

，

最后把所有12个向量保存到文件里作为一个训练或者测试数据。

根据以上数据获取方法，本文获取了8种鼠标轨迹数据，每种300个轨迹数据，共2400个，其中1200个用作分类器的训练数据，另外1200个用作训练好的分类器的测试数据。

2 鼠标轨迹识别问题的分类器设计

本文求解了8种鼠标轨迹的识别问题，这8种鼠标轨迹如图2所示。

2.1 BP神经网络的设计

神经网络设计为3层，权值设置在[-1,1]的区间内，由反向传播算法来对权值进行学习更新。由于该多分类问题是非线性问题，因此本文使用表征能力更强的Sigmoid单元[4]作为BP神经网络的基本组成单元。

2.1.1 BP神经网络的输入

每个鼠标轨迹由12个单位向量组成，以这12个单位向量作为神经网络的输入，因此神经网络的输入为24个（因为每个单位向量有两个分量），即为每个向量的两个分量值的组合。例如（1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0）是向右轨迹的12个单位向量的分量组合。

2.1.2 BP神经网络的输出

该问题是多分类问题，目标是使智能体识别8种鼠标轨迹，因此神经网络的输出有8个，表示8种鼠标轨迹的标志，根据这8个输出中的最大输出来决定样本所属的类型。

2.1.3 BP神经网络的隐藏层

根据经验公式选择隐藏层神经元的个数。其中包含两种经验公式[5]：

(1)

其中，nH为隐藏层神经元个数，nI为输入层神经元个数，nO为输出层神经元个数，L为1～10之间的整数。

(2)

其中 是隐藏层神经元个数， 是输入层神经元个数， 是输出层神经元个数。

根据公式1计算可知，隐藏层的个数为7～16，公式2计算可知隐藏层个数为13。隐藏层神经元个数对收敛速度和神经网络的能力的影响比较大，隐藏层神经元越多，神经网络的求解能力越强，但是训练时间增加，且容易造成训练过度；隐藏层神经元越少，网络所获得解决问题的信息就越少，难以处理复杂问题。本文经过误差收敛分析，综合考虑了收敛速度和网络的求解能力，确定选择隐藏层的神经元个数为13较为合理。

2.1.4 BP神经网络的学习率

BP神经网络的学习率对神经网络的学习能力影响也较大[6]，学习率越大，收敛速度越快，误差收敛曲线起伏越大，反之学习率越小，收敛速度越慢，误差收敛曲线越光滑。通过对收敛速度和误差收敛曲线的综合分析，确定学习率为0.05较为合理。

2.2 支持向量机的设计

由于支持向量机理论的高复杂性，对于应用而言，本文采用台湾大学的林智仁（C.J.Lin）等人开发出的LIBSVM软件包。

根据多次实验对支持向量机的参数进行了调整，最后确定如下参数设置[7]较为合理：

1）支持向量机类型：c_svc；

2）核函数采用多项式：(r*u'v + coef0)^degree，其中degree为3，coef0为1，r为1；

3）分类器类别为8；

训练完成后，总共的支持向量个数为232个，决策函数中常数项b的值分别

-0.0873484 0.028086 -0.0158987 0.665355 0.698556 0.482181 0.60059 0.16046 0.115076 0.720934 0.742779 0.217058 0.474723 -0.0232876 0.633551 0.695379 0.156374 0.44867 0.676731 0.687293 0.179702 0.421568 0.0461662 -0.532837 -0.312952 -0.58308 -0.380752 0.396621。

类别标签为1,2,3,4,5,6,7,8，分别对应的支持向量个数为13,14,16,9,59,65,22, 34。

3 实验及其结果分析

实验的图形引擎使用了自主开发的Engine3D引擎[8]，该引擎基于DirectX9.0。游戏的运行界面如图3所示。

本文获取的实验数据样本大小为2400，其中1200个用作分类器的训练数据，另外1200个用来对训练好的分类器进行测试。

使用BP神经网络作为分类器时，图4是神经网络在训练过程中，实际输出相对目标输出的误差相对于权值更新次数变化的过程。实验中误差阈值设置为34.0037，由图中可看出，权值更新了37270次之后(为了便于显示，图中截取了前1500次迭代)，误差落在34.0037之下，权值更新结束，神经网络训练完成。

神经网络训练完成后，使用剩下的1200个测试样例进行测试后，得出如表1结果。

使用支持向量机作为分类器时，使用1200个测试样例进行测试后，得出如表2结果。

神经网络和SVM分类器的实验结果对比如表3所示。

分析结果可以得出以下结论：

结论1：由于游戏的特殊性，在玩家实际的操作中，智能体对玩家的鼠标轨迹识别的正确率能够达到90%以上可以令人满意，一方面该正确率能够令玩家感到智能体很聪明，从而提高了游戏的趣味性，另一方面识别的时候出现一些错误会使得智能体看起来更加人性化更加有趣，因为即使是人来做这个工作，也会存在错误分类的可能性。

结论2：通过对比SVM的正确率98.75%高于BP神经网络的93.75%，因此在实际应用的时候应该根据具体需求来有选择地使用分类器，以发挥其的最大性能。

4 结束语

本文针对游戏中智能体的鼠标轨迹识别问题，提出了采用BP神经网络和SVM的解决方案，实验结果表明，该解决方案较好地解决了这个问题，并且在封闭测试中得到了令人满意的正确识别率(正确识别率都达到90%以上)，因此本文提出的解决方案具有一定的实际应用价值。

下一步工作希望将本文提出的解决方案应用到具体的游戏项目当中，使得机器学习技术能够真正在游戏中发挥作用，从真正意义上提高游戏的趣味性。

参考文献：

[1] Rabin S.人工智能游戏编程真言[M].庄越挺,吴飞,译.北京:清华大学出版社,2005:17-18.

[2] Bourg D M,Glenn Seemann.AI for Game Developers(影印本)[M].南京:东南大学出版社,2005:23-24.

[3] Mitchell T M.机器学习[M].曾华军,张银奎,译.北京:机械工业出版社,2003:33-35.

[4] 沈富可,常潘,任肖丽.基于BP神经网络的P2P流量识别研究[J].计算机应用,2007,27(S2):44-45.

[5] Buckland M.I Techniques for Game Programming[M].United States of America: Premier Press,2002:18-20.

[6] Cristianini N,Shawe-Taylor J.支持向量机导论[M].李国正,王猛,曾华军,译.北京:电子工业出版社,2004:3-5.

[7] LaMothe A.Tricks of the 3D Game Programming Gurus―Advanced 3D Graphics and Rasterization[M].United States of America:Sams Publishing,2003:5-7.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文