人工智能在拼石头游戏中的应用

1、人工智能在拼石头游戏中的应用人工智能在拼石头游戏中的应用引言论文联盟.Ll.游戏的人工智能研究是人工智能的主要研究领域之一，它涉及人工智能中的搜索方法和决策规划等。俄罗斯方块游戏和七巧板游戏都是经典的具有启智、益智功能的平面拼图游戏。第18届日本全国高专编程竞赛竞技组的题目，便是借鉴这两款游戏的特点并引入竞标机制而创造的一款新游戏即拼石头。详细规那么如下：每次比赛有6至10支队伍参加，每支队伍各自拥有一样形状、面积的一面墙和一样金额的虚拟货币。墙是由假设干个单元正方形构成的，如图1所示。图1墙裁判方在赛前给出假设干种形状的石头，每种石头有假设干块以及各自的底价，石头也是由假设干个单元正方形构成

2、的，但面积要比墙小的多，如图2所示。图2石头每次比赛有假设干轮的竞标，每轮竞标中有最大竞标数和最大中标数N做限制N=1。每支参赛队按照最大竞标数提供竞标信息，竞标信息中包括参赛队要购置的石头种类、为每块石头报出的竞标价格竞标价格不得低于石头底价以及对竞标石头的排序，例如等于5时，可能的竞标信息是A100，A200，20，B70，D5，表示以价格100竞标石头A，以价格200竞标石头A，并且该队本轮竞标的排序是AABD。当有多支队伍竞争一样种类的石头时，该种石头优先卖给为其排序靠前的队伍；当多支队伍在一样排位上竞争一样种类的石头，且该种石头数量小于竞争队伍数量时，该种石头优先卖给出价高的队伍，假

3、设有两支或两支以上的队伍出价一样，那么在参与竞争的，且出价一样的队伍中进展二次竞标，假设出价仍然一样，那么该石头本轮流拍。另外，假设某支队伍在本轮已经获得了块数等于最大中标数N的石头，那么其后面的竞标信息无效，即该队伍退出本轮竞标。，以3支队伍为例，假设当前裁判方有2块石头A、1块石头B、1块石头、2块石头D、3块石头E，本轮最大竞标数和最大中标数N分别为4和2。参赛队伍的竞标信息如表1所示。表1参赛队竞标信息队伍排序1234aA10A200B50E20b20A100B60D2021A300B100E25根据规那么，在排序1上，队伍a以10获得1块石头A，队伍以21获得1块石头；在排序2上，队

4、伍以300获得1块石头A，此时队伍在本轮已经到达最大中标数2，该队伍的排序3和4无效；在排序3上，队伍b以60获得1块石头B；在排序4上，队伍a以20获得1块石头E，队伍b以20获得1块石头D。每轮竞标完毕后，裁判方为各队伍分配所购得的石头，同时公布本轮竞标情况，并以剩余石头开场下一轮的竞标；各参赛队伍，在准备开场下轮竞标的同时，可以将购得的石头拼在墙上，拼石头时，石头不能悬空摆放，同时每块石头都可以像俄罗斯方块中的石头一样，旋转90、180或270，但不能里外翻转，例如图2中的石头A不能里外翻转后当作石头B来使用。当最后一轮竞标完毕的2in后，比赛完毕，裁判方使用以下次序的评判规那么为各队排

5、名次：拼到墙上的石头的总面积大者获胜；面积一样者剩余货币多者获胜；剩余货币一样者剩余石头买到但没有拼到墙上的石头总面积小者获胜；剩余石头总面积一样者墙上沿占满率大者获胜；以上条件全一样者，以石头、剪刀、布的方式确定名次。墙的形状、石头的种类数、每种石头的形状、块数和底价、竞标轮数及每轮最大竞标数和最大中标数等信息，在赛前给定。参赛队伍需要在赛前编写程序，指导游戏过程中的竞标和拼图。1问题分析根据引言中对游戏规那么的描绘，可知理想状态下，使用单位面积价格最低的石头拼满整个墙时，一定可以获得成功。但由于石头数量有限，往往会出现：不能以底价或低价买到石头；买到的石头拼不上；论文联盟.Ll.想买的石头

6、买不到等现象。结合比赛结果评判标准中，拼到墙上的石头的总面积大者获胜为第一原那么的情况，在诸多游戏者中，谁可以买到更大面积的石头，并尽量将买到的石头拼在墙上，谁就能在比赛中获胜。通过上述的简单分析，参赛者编写的程序应至少在买什么石头和怎么拼石头两个方面给出决策和指导。也就是说，程序中要解决竞标和拼图两个问题，竞标负责帮助游戏者合理排位、合理出价；拼图帮助游戏者合理摆放石头。然而，竞标和拼图问题又不是互相孤立存在的，它们之间是互相制约、互相依赖的关系，即竞标时要买拼图可以使用上的石头；拼图时应选择竞标后买到的和在下一论竞标中容易买到的石头。同时，竞标和拼图对于石头的要求是互相矛盾的，形状规那么的

7、石头在拼图时更加容易被利用，例如图2中的石头D和E，但是，它们都是竞标时不愿去购置的石头，石头D面积小浪费中标名额，石头E面积大且形状规那么，势必成为紧俏商品，很难买到；反之，竞标时容易买到的石头，例如图2中的石头，但它在拼图中很难被用到。如何处理竞标和拼图对于石头要求不同的矛盾，成为获得成功的关键。2策略制定根据对游戏规那么的理解和问题的分析，我们为程序的编写在拼图算法选择、竞标排序等方面制定如下策略：2.1拼图算法的选择采用深度优先的搜索算法进展拼图，并且由墙的底部开场向上摆放石头，保证不悬空。拼图时在已经买到的石头和裁判方剩余石头两个集合中选择石头两个集合分别记做Sed和S，并优先选择S

8、ed中的石头，在S中选择石头时，按照估值函数后文中给出给石头打分，根据每种石头的估值以堆构造存储S，每次选择堆顶的石头进展试探。2.2拼图解确实定深度优先搜索拼图解法时，不一定将拼满墙作为解，即产生的解允许与墙的面积相差一定的单元格。2.3各轮竞标的货币分配按照少多少的枣核形状整体分配各轮使用的虚拟货币，这样做的原因是：前期竞标时石头多、竞争小，中期竞标时竞争剧烈应该尽量花钱，后期竞标时石头已经快卖光，为后期保存过多的货币没有用途。详细比例可适当调整。2.4每轮竞标石头的选择在每轮竞标之前进展拼图，并在拼图产生的解中，选择块面积大的，且属于集合S的石头作为本轮参与竞标的石头等于本轮的最大竞标数

9、。2.5每轮竞标的排序每轮竞标时，先论文联盟.Ll.按照需要购置的石头的面积排降序，然后按照当前裁判方各种类的石头数量，进展顺序调整，假设在排序的前几位上，某种类的石头数量较多，可在一定可以买到的前提下，适当将其顺序向后调整。2.6每轮竞标的出价在每轮竞标中，为要购置的石头排好顺序后，要为本轮所要购置石头出价。由于最大中标数小于最大竞标数，所以出价的总额要略大于最初为本轮分配的货币数。出价时，首先为一定可以买到的石头出底价，然后为存在竞争的石头按照面积、数量、排序等因素出价，面积大排序靠前、数量少的出高价，反之出低价。详细比例可适当调整。3石头估值函数设计为保证组成解的各个石头中的大局部是我们

10、认为的好石头，在使用深度优先的搜索算法进展拼图时，需要在裁判方提供的石头集合中优先选择好的石头进展试探。确定石头的好坏需要设计关于石头的估值函数。影响石头好坏的因素包括面积、数量、形状等几个方面。在面积方面，由于受竞标次数的限制，拼图时应尽量选择面积大的石头，即面积越大石头越好；在数量方面，某种类的石头数量越多，竞争就越小，出低价甚至出底价就可买到，因此数量越多石头越好；在形状方面，形状规那么的石头容易在拼图中使用，但是这样的石头不容易购置，反之，形状不规那么石头不易在拼图中使用，但其面积大且容易购置，认为形状规那么的石头好和认为形状不规那么的石头好，都有各自的道理，这里我们选择形状不规那么的

11、石头作为好石头。综合面积、数量、形状3方面的因素，我们给出的石头估值函数如公式1：F(x)=k1A(x)+k2R(x)+k3(x)1其中，x表示石头；A(x)表示石头的面积；R(x)表示石头的凹凸度，即不规那么程度，R(x)的值等于组成该石头矩形的个数，例如图2中的石头A和B的凹凸度为2，石头的凹凸度为4，石头D和E的凹凸度为1；(x)表示该类石头的数量；k1、k2和k3为非负系数，用于调节这3方面所占的比重。4算法实现针对之前制定的策略，我们使用irsftVisual+6.0作为开发工具，开发了参赛程序。下面给出程序的伪代码：读取本次比赛信息，包括墙、石头、竞标数等;定义石头集合Sed和S，

12、Sed初始为空，S初始为全部裁判方石头;定义循环变量i，初始为0;hile(i竞标轮次数)hile(尚未求出拼图的解)按照石头估值函数调整S为堆;if(Sed中存在未试探过的石头)从Sed中选择石头;else从S中选择石头;if(试探选择石头可以摆放)摆放石头;将该类石头的数量减1;else根据求得的拼图解给出竞标的排序和出价;读取本轮竞标信息;调整集合Sed和S;i+;使用集合Sed中的石头进展最后一次拼图;5完毕语选手使用以上策略和算法实现的程序，参加了第18届日本全国高专编程竞赛竞技组的比赛，在参赛的60多支队伍论文联盟.Ll.中，经过两轮的淘汰赛，成功进入最后一轮比赛。两轮淘汰赛中，分别以小组第一和第二成绩晋级，但在最后一轮比赛中败北。失败的原因除了人为操作失误以外，算法也存在一定的缺陷。算法的主要缺陷在于：进展拼图时，我们只计算一个解，即