智能算法在剪刀石头布游戏中的应用

摘要：石头剪子布游戏作为猜拳游戏的一种，用来产生随机结果以作决策。但有时它并不随机，因为游戏者可以根据经验，判断对手的手法。将此应用于人机对战中，计算机根据“经验”来模拟人类出拳策略，使计算机具备一定的人工智能性[1]。文章通过对遗传算法和模拟退火算法的研究[2]，阐述了算法的基本原理和各自特点及其实现过程，在Visual Studio编译环境下实现了应用于该游戏的这两种算法。通过两算法之间的相应参数和各自算法中不同参数的游戏胜率对比来选定更优的智能算法与设置更优的参数[3]。

Abstract： The game rock-paper-scissors as a kind of finger-guessing game used to produce random results for decision making. But sometimes it is not random， because players can judge technique according to experience. Applied it to the war machine and according to the "experience" of computer to simulate human’s strategy， make a computer with artificial intelligence. For the research of genetic algorithm and simulated annealing algorithm in this paper， it elaborates the fundamentals and characters as well as their realization process， I have been realized these two algorithms in the Visual Studio compiling environment and applied to the game rock-paper-scissors. By comparing the different parameters and win rates between genetic algorithm and simulated annealing algorithm to select the better algorithm and parameters.

关键词：遗传算法；模拟退火算法；游戏设计；参数设定

Key words： genetic algorithm （GA）；simulated annealing（SA）；game design；parameter setting

中图分类号：TP18 文献标识码：A 文章编号：1006-4311（2016）02-0169-03

0 引言

石头剪刀布游戏常在两个或多个玩家进行，将石头剪刀布游戏应用于人机对战中，电脑可以根据玩家和电脑过去的出拳策略，总结一定的“经验”――我们可以据此“经验”来提高电脑在游戏中的胜率，展现计算机在此应用上的人工智能性。

遗传算法、模拟退火算法和神经网络算法是最优化理论的三大非经典算法[4]，但是神经网络算法在解决最优化问题中容易陷入局部极值，本文选择采用遗传算法和模拟退火算法模拟解决最优化问题。

遗传算法（Genetic Algorithm-GA）是基于自然界生物进化过程提出的一种全局随机搜索优化算法，具有较强的全局搜索能力，可以有效的避免局部最优解[5]。模拟退火算法（simulated Annealing-SA）是基于Mon-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质退火过程与一般组合优化问题之间的相似性，是一种通用的优化算法，算法理论上具有概率的全局优化性能，算法通过赋予搜索过程一种时变并且最终趋于零的概率突跳性；从而可以有效地避免陷入局部极小并最终趋于全局最优的串行结构的优化算法[6]。

1 定义游戏问题模型

1.1 游戏规则

石头剪子布游戏有一般在两个玩家之间进行，玩家从三种出拳类型中选择一种与对方进行对战，根据游戏规则来确定胜负情况。玩家A、B间的游戏规则如表1所示。

1.2 用智能算法设计游戏的出拳策略

游戏的三种出拳类型：“剪子”，“石头”，“布”分别用0，1，2来表示，用R={0，1，2}来表示出拳类型的集合。游戏的读取深度（表示根据电脑和人类玩家过去的对战次数来决定电脑的下次出拳）为depth，那么游戏的某一出拳策略Rdepth*2可以用R的函数S来进行表示。如果出拳策略的读取深度为1，那么电脑玩家的出拳策略Rdepth*2（即S）可以用下面的例子来表示：

S（0，0）= 0； S（0，1）= 2； S（0，2）= 0；

S（1，0）= 1； S（1，1）= 1； S（1，2）= 0；

S（2，0）= 1； S（2，1）= 2； S（2，2）= 1；

其中：S（0，1）=2表示电脑出拳为0，玩家出拳为1时，电脑下一次的出拳策略为2，以此类推。例如电脑（用C表示）过去4次的出拳类型和人类玩家（用P表示）相应4次的出拳类型分别为：

C={0012} P={1010}

那么出拳策略的评价如下：

第1次出拳：出拳策略H没有过去的对战情况，无法评价。

第2次出拳：前一次出拳电脑为0（剪刀），人类玩家为1（石头）；如果电脑采取策略H选择出拳类型S（0，1）=2（布），那么电脑会失败，而实际电脑选择了0（剪刀），平局。

第3次出拳：前一次的出拳类型为C=0、P=0，若采用出拳策略S（0，0）=0，此时对战对手的出拳为1，采用策略电脑将获得胜利，而实际出拳类型也是1，电脑获胜。

第4次出拳：前一次出拳类型为C=1、P=1，采用出拳策略S（1，1）=1。对战对手的出拳策略为0，如果电脑根据出拳策略选择1将获得胜利，而实际出拳类型为2，电脑输。

本文中，读取深度设置为1和2两种情况分别进行讨论。

2 智能算法游戏流程

2.1 遗传算法的游戏流程

①初始种群的生成，采用随机生成的方法进行产生初始种群，这些解也称之为染色体，是种群的第一代。

②评价适应值，根据每个解（每条染色体）算出相应的适应度，算法会根据适应度的大小来选择相应的解。

③选择，选择会把优秀的个体遗传到下一代染色体中。本文采用最优选择与随机遍历选择法进行选择操作。

④交叉，交叉会染色体中的部分个体进行替换和重组得到新的染色体。

⑤突然变异，按照一定的突变概率，将染色体中的个体随机进行变动。

⑥终止条件，若达到的终止条件，那么选择适应度最大的个体作为最优解进行输出；否则返回②继续计算。

2.2 模拟退火算法的游戏流程

①随机产生一个新的解，同时赋给当前解和最优解；计算新解的评价值，同时赋给当前解的评估值和最优解的评估值。

②比较新解和当前解的评估值之差delta，若delta>=0则保存新解为当前解；同时比较新解和最优解的评估值之差delta2，若delta2>=0则保存新解为最优解。

③若delta

模拟退火的接受概率P1=exp（delta/T）与随机概率P2的差值P=P1-P2；若P>0则接受新解作为当前解，否则不接受。

④随温度的递减，在一定条件下循环②到③，程序始终接受最优解进行返回。

3 实验过程

3.1 遗传算法实验

进行100次游戏为例，设置人类玩家自动出拳类型为“石头”以及“石头-布-剪刀-布”，在深度depth分别为1和2两种情况下进行实验。实验电脑的得分计算是：胜为1，平为0，败为-1，得分采用累加式计算。实验进行10次取其平均值，所得的实验分析如图1和图2以及对应的表1和表2所示。

3.2 模拟退火算法实验

为与遗传算法进行对照，采用模拟退火算法时同样采取100次游戏为例，采取同样的出拳类型，深度depth也分别选择1和2两种情况进行。实验分析如图3和图4以及对应的表3和表4所示。

4 实验分析

4.1 纵向分析

遗传算法实验从图1以及表1中可看出，当出拳类型为单一的“石头”时，depth=1和depth=2的得分曲线相当，但是depth=1时，其效率明显于depth=2；从图2及表2中可以看出，当出拳类型变复杂（“石头-布-剪刀-布”）时，depth=2明显高于depth=1时的得分。

模拟退火算法实验从图3及表3中可看出，同样的当出拳类型为单一的“石头”时，depth=1和depth=2的得分曲线相当，但是depth=1时，其效率明显于depth=2；从图4及表4中可以看出，当出拳类型变复杂（“石头-布-剪刀-布”）时，depth=2低于depth=1的得分且depth=2时的效率明显更低。

4.2 横向分析

对比图1和图3以及对应的表1和表3，可以看出：出拳类型为单一的“石头”时，遗传算法和模拟退火算法两者在depth=1和depth=2时的胜率相当，但是遗传算法的运行效率明显数倍于模拟退火算法。

同样的，对比图2和图4以及对应的表2和表4，可以看出：出拳类型为“石头-布-剪刀-布”，在depth=1时，模拟退火算法高于遗传算法的得分，但效率低于遗传算法；而当depth=2时遗传算法无论在得分还是在运行效率上明显优于模拟退火算法。

5 结束语

从实验的分析和结果可知，在石头剪子布游戏中，条件相同的情况下，遗传算法的效率明显高于模拟退火算法。当游戏的出拳策略较为简单（如只出“石头”）时，深度为1是智能算法更好的选择；依据试验结果和推测，当出拳策略更为复杂时，遗传算法在结果和效率上更显示其优越性。下一步工作将会扩大游戏规模与出拳复杂度，选取更合适的游戏参数进行分析。

参考文献：

[1]卓金武主编.MATLAB在数学建模中的应用[M].北京：北京航空航天大学出版社，2011.

[2]曹文梁，康岚兰.基于遗传算法的混合蚁群算法及其在TSP中的应用研究[J].制造业自动化，2011（02）：91-93.

[3]董健.一种单纯形遗传算法及其应用[J].电信工程技术与标准化，2013（07）：86-88.

[4]胡志伟，郄培，赵新超，等.一种新的混合遗传算法求解旅行商问题[J].计算机与现代化，2010（11）：12-15.

[5]刘宝坤，石红瑞，王慧，等.基于遗传算法的神经网络自适应控制器的研究[J].信息与控制，1997（04）.

[6]王雪梅，王义和.模拟退火算法与遗传算法的结合[J].计算机学报，1997（04）.