人工智能游戏的论文(2)
人工智能游戏的论文
人工智能游戏的论文篇二
人工智能在拼石头游戏中的应用
引言
游戏的人工智能研究是人工智能的主要研究领域之一，它涉及人工智能中的搜索方法和决策规划等。俄罗斯方块游戏和七巧板游戏都是经典的具有启智、益智功能的平面拼图游戏。第18届日本全国高专编程竞赛竞技组的题目，便是借鉴这两款游戏的特点并引入竞标机制而发明的一款新游戏即拼石头。具体规则如下：
每次比赛有6至10支队伍参加，每支队伍各自拥有相同形状、面积的一面“墙”和相同金额的虚拟货币。“墙”是由若干个单元正方形构成的，如图1所示。
图1“墙”
裁判方在赛前给出若干种形状的“石头”， 每种“石头”有若干块以及各自的底价，“石头”也是由若干个单元正方形构成的，但面积要比“墙”小的多，如图2所示。
图2“石头”
每次比赛有若干轮的竞标，每轮竞标中有“最大竞标数M”和“最大中标数N”做限制(M>N>=1)。每支参赛队按照“最大竞标数M”提供竞标信息，竞标信息中包括参赛队要购买的“石头”种类、为每块石头报出的竞标价格(竞标价格不得低于“石头”底价)以及对竞标“石头”的排序，例如M等于5时，可能的竞标信息是{A100，A200，C20，B70，D5}，表示以价格100竞标“石头”A，以价格200竞标“石头”A……，并且该队本轮竞标的排序是AACBD。当有多支队伍竞争相同种类的“石头”时，该种“石头”优先卖给为其排序靠前的队伍;当多支队伍在相同排位上竞争相同种类的“石头”，且该种“石头”数量小于竞争队伍数量时，该种“石头”优先卖给出价高的队伍，若有两支或两支以上的队伍出价相同，则在参与竞争的，且出价相同的队伍中进行二次竞标，若出价仍然相同，则该“石头”本轮“流拍”。另外，若某支队伍在本轮已经获得了块数等于“最大中标数N”的“石头”，则其后面的竞标信息无效，即该队伍退出本轮竞标。，
以3支队伍为例，假设当前裁判方有2块“石头”A、1块“石头”B、1块“石头”C、2块“石头”D、3块“石头”E，本轮“最大竞标数M”和“最大中标数N”分别为4和2。参赛队伍的竞标信息如表1所示。
表1参赛队竞标信息队伍\排序[]1234aA10A200B50E20bC20A100B60D20cC21A300B100E25根据规则，在排序1上，队伍a以10获得1块“石头”A，队伍c以21获得1块“石头”C;在排序2上，队伍c以300获得1块“石头”A，此时队伍c在本轮已经达到“最大中标数”2，该队伍的排序3和4无效;在排序3上，队伍b以60获得1块“石头”B;在排序4上，队伍a以20获得1块“石头”E，队伍b以20获得1块“石头”D。
每轮竞标结束后，裁判方为各队伍分配所购得的“石头”，同时公布本轮竞标情况，并以剩余石头开始下一轮的竞标;各参赛队伍，在准备开始下轮竞标的同时，可以将购得的“石头”拼在“墙”上，拼“石头”时，“石头”不能悬空摆放，同时每块“石头”都可以像俄罗斯方块中的“石头”一样，旋转90°、180°或270°，但不能“里外”翻转，例如图2中的“石头”A不能“里外”翻转后当作“石头”B来使用。当最后一轮竞标结束的2min后，比赛结束，裁判方使用以下次序的评判规则为各队排名次：①拼到“墙”上的“石头”的总面积大者获胜;②面积相同者剩余货币多者获胜;③剩余货币相同者剩余“石头”(买到但没有拼到“墙”上的“石头”)总面积小者获胜;④剩余“石头”总面积相同者“墙上沿”占满率大者获胜;⑤以上条件全相同者，以“石头、剪刀、布”的方式确定名次。
“墙”的形状、石头的种类数、每种石头的形状、块数和底价、竞标轮数及每轮“最大竞标数”和“最大中标数”等信息，在赛前给定。参赛队伍需要在赛前编写程序，指导游戏过程中的竞标和拼图。
1问题分析
根据引言中对游戏规则的描述，可知理想状态下，使用单位面积价格最低的“石头”拼满整个“墙”时，一定能够获得胜利。但由于“石头”数量有限，往往会出现：不能以底价或低价买到“石头”;买到的“石头”拼不上;想买的“石头”买不到等现象。结合比赛结果评判标准中，“拼到‘墙’上的‘石头’的总面积大者获胜”为第一原则的情况，在诸多游戏者中，谁可以买到更大面积的“石头”，并尽量将买到的“石头”拼在“墙”上，谁就能在比赛中获胜。
通过上述的简单分析，参赛者编写的程序应至少在买什么“石头”和怎么拼“石头”两个方面给出决策和指导。也就是说，程序中要解决“竞标”和“拼图”两个问题，“竞标”负责帮助游戏者合理排位、合理出价;“拼图”帮助游戏者合理摆放“石头”。然而，“竞标”和“拼图”问题又不是相互孤立存在的，它们之间是相互制约、相互依赖的关系，即竞标时要买拼图能够使用上的“石头”;拼图时应选择竞标后买到的和在下一论竞标中容易买到的“石头”。同时，“竞标”和“拼图”对于“石头”的要求是相互矛盾的，形状规则的“石头”在拼图时更加容易被利用，例如图2中的“石头”D和E，但是，它们都是竞标时不愿去购买的“石头”，“石头”D面积小浪费中标名额，“石头”E面积大且形状规则，势必成为“紧俏”商品，很难买到;反之，竞标时容易买到的“石头”，例如图2中的“石头”C，但它在拼图中很难被用到。如何处理“竞标”和“拼图”对于“石头”要求不同的矛盾，成为获得胜利的关键。
2策略制定
根据对游戏规则的理解和问题的分析，我们为程序的编写在拼图算法选择、竞标排序等方面制定如下策略：
2.1拼图算法的选择
采用深度优先的搜索算法进行拼图，并且由“墙”的底部开始向上摆放“石头”，保证不悬空。拼图时在已经买到的“石头”和裁判方剩余“石头”两个集合中选择“石头”(两个集合分别记做Sed和S)，并优先选择Sed中的“石头”，在S中选择“石头”时，按照估值函数(后文中给出)给“石头”打分，根据每种“石头”的估值以堆结构存储S，每次选择堆顶的“石头”进行试探。
2.2拼图解的确定
深度优先搜索拼图解法时，不一定将拼满“墙”作为解，即产生的解允许与“墙”的面积相差一定的单元格。
2.3各轮竞标的货币分配
按照“少—多—少”的枣核形状整体分配各轮使用的虚拟货币，这样做的原因是：前期竞标时“石头”多、竞争小，中期竞标时竞争激烈应该尽量“花钱”，后期竞标时“石头”已经快卖光，为后期保留过多的货币没有用处。具体比例可适当调整。
2.4每轮竞标“石头”的选择
在每轮竞标之前进行拼图，并在拼图产生的解中，选择M块面积大的，且属于集合S的“石头”作为本轮参与竞标的“石头”(M等于本轮的最大竞标数)。
2.5每轮竞标的排序
每轮竞标时，先 按照需要购买的“石头”的面积排降序，然后按照当前裁判方各种类的“石头”数量，进行顺序调整，若在排序的前几位上，某种类的“石头”数量较多，可在一定能够买到的前提下，适当将其顺序向后调整。
2.6每轮竞标的出价
在每轮竞标中，为要购买的“石头”排好顺序后，要为本轮所要购买“石头”出价。由于“最大中标数”小于“最大竞标数”，所以出价的总额要略大于最初为本轮分配的货币数。出价时，首先为一定能够买到的“石头”出底价，然后为存在竞争的“石头”按照面积、数量、排序等因素出价，面积大(排序靠前)、数量少的出高价，反之出低价。具体比例可适当调整。
3“石头”估值函数设计
为保证组成解的各个“石头”中的大部分是我们认为的“好石头”，在使用深度优先的搜索算法进行拼图时，需要在裁判方提供的“石头”集合中优先选择“好的石头”进行试探。确定“石头”的好坏需要设计关于“石头”的估值函数。
影响“石头”好坏的因素包括面积、数量、形状等几个方面。在面积方面，由于受竞标次数的限制，拼图时应尽量选择面积大的“石头”，即面积越大“石头”越“好”;在数量方面，某种类的“石头”数量越多，竞争就越小，出低价甚至出底价就可买到，因此数量越多“石头”越“好”;在形状方面，形状规则的“石头”容易在拼图中使用，但是这样的“石头”不容易购买，反之，形状不规则“石头”不易在拼图中使用，但其面积大且容易购买，认为形状规则的“石头”好和认为形状不规则的“石头”好，都有各自的道理，这里我们选择形状不规则的“石头”作为“好石头”。 综合面积、数量、形状3方面的因素，我们给出的“石头”估值函数如公式(1)： F(x)=k1A(x)+k2R(x)+k3C(x)(1)其中，x表示“石头”;A(x)表示“石头”的面积;R(x)表示“石头”的“凹凸度”，即不规则程度，R(x)的值等于组成该“石头”矩形的个数，例如图2中的“石头”A和B的“凹凸度”为2，“石头”C的“凹凸度”为4，“石头”D和E的“凹凸度”为1;C(x)表示该类“石头”的数量;k1、k2和k3为非负系数，用于调节这3方面所占的比重。
4算法实现
针对之前制定的策略，我们使用Microsoft Visual C++ 6.0作为开发工具，开发了参赛程序。下面给出程序的伪代码：
读取本次比赛信息，包括墙、石头、竞标数等;
定义石头集合Sed和S，Sed初始为空，S初始为全部裁判方石头;
定义循环变量i，初始为0;
while(i<竞标轮次数)
{
//拼图
while(尚未求出拼图的解)
{
按照石头估值函数调整S为堆;
if(Sed中存在未试探过的石头)
从Sed中选择石头;
else
从S中选择石头;
if(试探选择石头能够摆放)
摆放石头;将该类石头的数量减1;
else
将该类石头的数量设为0;//使其估值函数值减小，在下一次选择中不会被选中}
//竞标
根据求得的拼图解给出竞标的排序和出价;
//竞标后的调整
读取本轮竞标信息;
调整集合Sed和S;
i++;
}
使用集合Sed中的石头进行最后一次拼图;
5结束语
选手使用以上策略和算法实现的程序，参加了第18届日本全国高专编程竞赛竞技组的比赛，在参赛的60多支队伍 中，经过两轮的淘汰赛，成功进入最后一轮比赛。两轮淘汰赛中，分别以小组第一和第二成绩晋级，但在最后一轮比赛中败北。失败的原因除了人为操作失误以外，算法也存在一定的缺陷。算法的主要缺陷在于：进行拼图时，我们只计算一个解，即使计算出多个解，使用深度优先的搜索算法得到的多个解也都是相近的。解的单一性造成了在比赛过程中，要买的某块面积较大的“石头”买不到时，不能及时调整拼图方案，最终导致拼得的面积较小。赛后，经过认真 总结以及与冠军队伍的交流之后，发现如果采用深度优先和广度优先结合的算法进行拼图，尽量得到差异较大的多个解，那么在某块面积较大的“石头”买不到时，便可及时地使用其它拼图方案指导竞标，从而争取拼出更大的面积。
看了“人工智能游戏的论文”的人还看了：
5.人工智能小论文