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

《人工智能在拼石头游戏中的应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、人工智能在拼石头游戏中的应用人工智能在拼石头游戏中的应用引言.L和最大中标数N做限制（M>N>=1）。每支参赛队按照最大竞标数M提供竞标信息，竞标信息中包括参赛队要购买的石头种类、为每块石头报出的竞标价格（竞标价格不得低于石头底价）以及对竞标石头的排序，例如M等于5时，可能的竞标信息是{A100，A200，C20，B70，D5}，表示以价格100竞标石头A，以价格200竞标石头A，并且该队本轮竞标的排序是AACBD。当有多支队伍竞争相同种类的石头时，该种石头优先卖给为其排序靠前的队伍；当多支队伍在相同排位上竞争相同种类的石头，且该种石头数量小于竞争队伍数量时，该种

2、石头优先卖给出价高的队伍，若有两支或两支以上的队伍出价相同，则在参与竞争的，且出价相同的队伍中进行二次竞标，若出价仍然相同，则该石头本轮流拍。另外，若某支队伍在本轮已经获得了块数等于最大中标数N的石头，则其后面的竞标信息无效，即该队伍退出本轮竞标。，　　以3支队伍为例，假设当前裁判方有2块石头A、1块石头B、1块石头C、2块石头D、3块石头E，本轮最大竞标数M和最大中标数N分别为4和2。参赛队伍的竞标信息如表1所示。　　表1参赛队竞标信息队伍排序[]1234aA10A200B50E20bC20A100B60D20cC21A300B100E25根据规则，在排序1上，队伍a以1

3、0获得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中的

4、石头A不能里外翻转后当作石头B来使用。当最后一轮竞标结束的2min后，比赛结束，裁判方使用以下次序的评判规则为各队排名次：①拼到墙上的石头的总面积大者获胜；②面积相同者剩余货币多者获胜；③剩余货币相同者剩余石头（买到但没有拼到墙上的石头）总面积小者获胜；④剩余石头总面积相同者墙上沿占满率大者获胜；⑤以上条件全相同者，以石头、剪刀、布的方式确定名次。　　墙的形状、石头的种类数、每种石头的形状、块数和底价、竞标轮数及每轮最大竞标数和最大中标数等信息，在赛前给定。参赛队伍需要在赛前编写程序，指导游戏过程中的竞标和拼图。　　1问题分析根据引言中对游戏规则的描述，可知理想状态下，使用单

5、位面积价格最低的石头拼满整个墙时，一定能够获得胜利。但由于石头数量有限，往往会出现：不能以底价或低价买到石头；买到的石头拼不上；.L块面积大的，且属于集合S的石头作为本轮参与竞标的石头（M等于本轮的最大竞标数）。　2.5每轮竞标的排序　　每轮竞标时，先.LicrosoftVisualC++6.0作为开发工具，开发了参赛程序。下面给出程序的伪代码：　　读取本次比赛信息，包括墙、石头、竞标数等;　　定义石头集合Sed和S，Sed初始为空，S初始为全部裁判方石头;　　定义循环变量i，初始为0;　　while(i<竞标轮次数)　　{　　//拼图　　while(尚未求出拼图的解)

6、　　{　　按照石头估值函数调整S为堆;　　if(Sed中存在未试探过的石头)　　从Sed中选择石头;　　else　　从S中选择石头;　　if(试探选择石头能够摆放)　　摆放石头;将该类石头的数量减1;　　else　　将该类石头的数量设为0;//使其估值函数值减小，在下一次选择中不会被选中}　　//竞标　　根据求得的拼图解给出竞标的排序和出价;　　//竞标后的调整　　读取本轮竞标信息;　　调整集合Sed和S;　　i++;　　}　　使用集合Sed中的石头进行最后一次拼图;　　5结束语　　选手使用以上策略和算法实现的程序，参加了第18届日本全国高专编程竞赛竞技组的比赛，在参赛的60

7、多支队伍.L.中，经过两轮的淘汰赛，成功进入最后一轮比赛。两轮淘汰赛中，分别以小组第一和第二成绩晋级，但在最后一轮比赛中败北。失败的原因除了人为操作失误以外，算法也存在一定的缺陷。算法的主要缺陷在于：进行拼图时，我们只计算一个解，即使计算出多个解，使用深度优先的搜索算法得到的多个解也都是相近的。解的单一性造成了在比赛过程中，要买的某块面积较大的石头买不到时，不能及时调整拼图方案，最终导致拼得的面积较小。赛后，经过认真总结以及与冠军队伍的交流之后，发现如果采用深度优先和广度优先结合的算法进行拼图，尽量得到