基于Pierre_Dell...e算法的AI俄罗斯方块设计_薛鹏.pdf

SCI-TECH INNOVATION&PRODUCTIVITYNo.1 Jan.2023，Total No.348基于 PierreDellacherie算法的AI俄罗斯方块设计收稿日期：20220411；修回日期：20220605作者简介：薛鹏（2001），男，四川德阳人，在读本科，主要从事软件工程研究，E-mail：。通信作者：陶岚菊（1991），女，四川宜宾人，硕士，讲师，主要从事工商管理、企业管理研究，E-mail：。薛鹏，陶岚菊摘要：本文基于 Pierre Dellacherie 算法，设计实现了俄罗斯方块的人工智能（AI）程序。通过对俄罗斯方块游戏进行分析，将游戏的各种状态抽象成变量，结合 Pierre Dellacherie 算法，实现了 AI 程序自动选择较优方案的目的，以达到模拟真人玩俄罗斯方块游戏的效果。关键词：Pierre Dellacherie 算法；俄罗斯方块；人工智能中图分类号：TP301.6；TP317.6；TP18文献标志码：ADOI：10.3969/j.issn.1674-9146.2023.01.018（成都锦城学院，四川成都611700）文章编号：1674-9146（2023）01018031AI 俄罗斯方块的研究背景俄罗斯方块是一款经典的益智型游戏，如何在俄罗斯方块里实现不同形状的板块的智能旋转、下落并最终摆放到合适的位置上，是人工智能（Artificial Intelligence，AI）领域的一个问题1。俄罗斯方块的游戏规则如下：由小方块组成的不同形状的板块陆续从屏幕上方落下来，玩家通过调整板块的位置和方向，使它们在屏幕底部拼出完整的一条满行或几条满行，这些完整的满行会随即消失，给新落下来的板块腾出空间；与此同时，玩家得到分数奖励。没有被消除掉的方块不断堆积起来，一旦堆到屏幕顶端的游戏上边界，玩家便告输，游戏结束2。学者 Heidi Burgiel 经过研究，已证明俄罗斯方块游戏最终一定会结束。因此，设计 AI 的目的就是为了让 AI 程序获得更多的分数。AI 俄罗斯方块的实现方法非常多，其中 Thiery&Scherrer 算法、Pierre Dellacherie 算法、DFS 算法都可以实现俄罗斯方块的 AI 程序。本文主要通 过 PierreDellacherie 算法来实现该程序。2问题分析与变量抽象定义俄罗斯方块的“不死性”：由于游戏的规则是未消除的方块累计高度达到游戏上边界的时候游戏失败，因此方块高度越低，整局游戏“不死性”就越强。随着方块的积累，整局游戏的“不死性”也在下降。通过对“不死性”的分析，将问题抽象成以下 6 个变量。2.1最大高度该变量用于统计放置后方块距离底部的距离。俄罗斯方块游戏结束的条件就是通过决策放置后的方块有一部分超出游戏规定的上边界，这时判定游戏失败。在游戏过程中，方块累计高度越高，整局游戏的“不死性”也就越低。因此，通过决策放置方块后所有方块中的最大高度是决策的重要考察因素之一。2.2消除的满行中属于本次下落板块的方块数量由于决策期望是消除更多的行数，因此通过决策放置方块后，消除的满行中存在本次放置的板块的方块数量越多，则说明这次板块放置的位置越好。需要设置一个全局的数组，数组中存放每一行方块的空格数量，就可以通过全局的数组算出消除的满行中有多少方块是属于本次放置的板块的。游戏过程中，方块模拟放下的过程中只需要记住方块放下去后能够消除的行的编号，遍历出所有的情况，将消除的满行行数作为数组的下标进行相加，变量 Max_count 为其最大值。2.3行变换行变换是指原本这个位置没有方块但是经过填充后变成有方块，或者这个位置本来有方块但是变成没有方块，这两种情况都可以视为发生过一次行变换。统计出所有的变换量，并返回这个参数，行变换的数量从侧面上反映出了方块的平整程度。如果游戏中方块摆放得不够平整，特别是在方块高度累计过高时，会出现某个高度接近游戏上边界的方块从而导致游戏的结束。方块整体上越平整，游戏整体局面的“不死性”就越强。通过逐层的遍历来实现行变换的统计。创新 思 维Innovative Thinking-018-2023 年 1 月总第 348 期2.4列变换列变换是指原本这个位置没有方块但是通过决策导致方块下落在该位置后变成了有方块，或者这个位置原本有方块但是通过决策导致方块被消除变成了该位置没有方块。与行变换几乎相同，不过列变换反映的是空洞的密集程度。空洞对游戏整体局面的影响非常大，列变换的数值越大，出现空洞的概率也就越大。游戏的失败往往也是由于空洞数量过多而导致的。列变换的统计和行变换的统计二者的差别就是：列变换是先遍历列，而行变换是先遍历行。2.5空洞数游戏的失败往往都是由空洞数过多而引起的。在方块的摆放序列中，当一个或者多个空格的周围全部都是方块时决策就将这个或这些空格视为空洞。当空洞累计到一定程度的时候，对于底部方块的消除也将变得困难。空洞数的多少也直接决定着游戏的“不死性”。2.6“井”总和“井”的定义是：它的形状就像生活中的井。中间没有被方块填充，两边都有连续的方块（将游戏的边界也算作方块）。此函数计算的是“井”的高度之和。如果“井”的大小就是 1 个空格，那么算作这个“井”的大小是 1；如果“井”的大小是3 个空格组成，那么“井”总和是 3+2+1。需要注意的地方是，“井”的类比和生活中的井非常相似，方块两边的高度不相同的时候遵循“短板效应”，当中间为空格的时候，如果左边方块的高度是 4，右边方块的高度是 3，那么“井”总和依旧是按照 3+2+1 来作为计算结果进行返回。“井”的存在对游戏整体局面的影响和空洞一样，同样是致命的，当“井”没有被落下来的方块填充反而是将“井”给覆盖起来的时候，“井”就会变成空洞，从而降低游戏整体局面的“不死性”。2.7分析总结通过对问题的分析，可通过抽象出的以上 6 个变量，将问题具体化。将以上 6 个变量相结合且作为变量代入评估函数，就可以对所有方块放置的情况进行打分处理，选出分数最高的一种情况来进行方块的放置。如果有多种情况的分数一样，则优先选择靠近左边落下的方案。3程序实现程序采取的是 C 语言，基于 Dev-C+6.5 进行实现。俄罗斯方块 AI 程序的实现分为两部分：第一部分是最基本的游戏内容的实现，这个部分能够实现最原始的俄罗斯方块的玩法；第二部分就是决策评估部分，通过枚举每一种方式的摆放方式并且结合决策评估函数，直接将方块放置在当前游戏整体局面的最佳位置上面，这一部分也是 AI 功能的重要部分。3.1游戏重要函数实现3.1.1游戏边界的打印游戏边界使用二维数组，通过遍历的方式配合语句 printf();进行相应的打印。并且将边界数组所存在的值设置为 1，空白的位置的值设置为 0。需要注意的是，当方块下落触底的时候，不能将方块位置数组的值也设置为 1，这是因为这样就会让墙面和触底的方块没有区别，可能导致消除游戏的边界问题，所以应该将触底的方块位置数组的值设置为 2，以便和边界产生区分。3.1.2方块的打印以及变化方块的显示问题使用结构体数组来定义，一共有 6 种结构体数组，这些结构体数组通过在地图数组的对应位置上打印方块来达到生成方块的目的。方块的变化也是结构体数组，根据方块的类型来进行相应的变化，从而选择最优方案进行下落。3.1.3随机方块的生成随机方块通过随机函数 struct block*proBlock(int n)来生成，其中 n 对应的值是 rand()%k+1。这样就可以生成从 1 到 k 的数字，这些生成的随机数字对应的正是不同的初始方块。3.1.4检测方块的状态检测方块的状态是指检测这个方块是不是应该被固定在这个位置无法移动。方块无法移动的条件就是四周是边界或者其他的方块，如果方块的四周有其他的方块或者边界，那么这个方块就不能继续向下移动。根据游戏的初始化设定，地图中没有方块的位置的值是 0。通过遍历，如果方块处往下一格位置的值是 1，那么方块就应该停止下来。3.1.5方块满行的消除以及相应分数的增加当方块在一行排满的时候，需要将这一行方块进行消除。每一次方块下落之后，都从游戏的底部向上面开始遍历。方块位置数组赋值是 2，当检查完一行之后，如果统计为 2 的变量的数值等于方块的宽度，那么就认为这一行为满行；再次遍历这一行，并且在地图数组上打印出空格，代表这一行已经被消除。继续向上遍历，将上面每一行的方块都向下移动一格，从而达到视觉上的方块消除效果。每一次方块满行被消除后，全局变量 score 加上对应的分数。3.2评估函数实现枚举出所有的情况，模拟每个位置摆放的情创 新 思维Innovative Thinking-019-SCI-TECH INNOVATION&PRODUCTIVITYNo.1 Jan.2023，Total No.348况，并评估出该位置对应的价值，找出其中的最大值。若其中有两个相同的最大值，则方案就是从左边到右边依次摆放。评估函数具体实现的程序代码如下。t1=getLandingHeight(bb);/放置后，滑块距离底部的距离;t2=getRemoveBlock(bb);/放置后，消掉的行数有多少块是属于这个滑块的;t3=getRowTransitions(bb);/统计每一行的变换;t4=getColTransitions(bb);/统计每一列的变换;t5=getHole(bb);/统计空洞的个数;t6=getWell(bb);/统计“井”的个数;return k1*t1+k2*t2+k3*t3+k4*t4+k5*t5+k6*t6;在评估完所有的情况之后，就可以进行 AI 的具体实现。具体实现方法就是通过枚举的方式再次模拟方块所有下落的位置，从左到右再次算出评分，如果算出来的评分等于前面算出来的最佳评分，那么方块就摆放在这个位置。4通过遗传算法和强化学习的方法选取权重评估函数为k1*t1+k2*t2+k3*t3+k4*t4+k5*t5+k6*t6，这里 ki的权重用于评估当前游戏整体局面的优劣程度，如何获得更加准确的权重是很重要的一件事情。如果想引入新的变量来评估游戏整体局面的优劣程度，那么就需要考虑原本的权重系数是否还适用于新的评估函数，新的权重系数怎样设置才能让消除的行数更多。本文选择遗传算法（Genetic Algorithm），遗传算法非常广泛地应用于参数的优化问题，对于系数的选择也可以看作参数的优化问题。初始设置一个种群（可能存在的解集），通过层层筛选以及交叉组合、变异等方式优胜劣汰，根据得分来判断系数是否合适，从而不断接近目标解集。比如，初始化1 000 个解集，通过得分来判断适应度，选择表现相对良好的解集继续进行交叉组合，设置一点扰动，从而构成下一代的解集继续筛选，如此反复。强化学习也可以作为优化权重的一个选择。在给定的一个解集中，对其中某个系数进行改动，同时程序获得一个反馈值，这个反馈值可以由分数的改变来体现，再通过反馈值不断地调整权重，以便获得更多的激励，如此往复便可以获得更好的权重分布。5结束语本文采用 Pierre Dellacherie 算法，实现了 AI 版本的俄罗斯方块，通过多次的试验，最高消除行数是 16 万行左右，平均消除行数是 12 万行左右。还有非常多值得改进的地方：一是程序中有多个地方的复杂度都是 n2，有的地方甚至达到了 n3，这将会让决策计算消耗大量的时间，如果游戏地图开得更大一些就会导致性能有所下降，以至于出现明显的停顿现象，某些部分可以通过动态规划算法的思想来进行优化。二是算法的评估参数不够准确，评估函数前面的参数不够精准导致不能消除更多的行数，参数的调整涉及深入的算法，需要大量的重复试验来测试。遗传算法和强化学习还有很多的方式都可以获得更加合适的权重，是一个非常值得探讨的问题，笔者会在未来进行更多的调整。参考文献：1BHM N,KKAIG,MANDLS.An evolutionary approachto tetris C.MIC.The Sixth Metaheuristic