基于Python实现贪心搜索下的俄罗斯方块【100012059】

# 贪心搜索下的俄罗斯方块 ## 1. 算法介绍 贪婪局部搜索算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。该实 现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。 ## 2. 项目问题介绍 ### 2.1. 俄罗斯方块问题 #### 2.1.1 原问题 由小方块组成的不同形状的板块陆续从屏幕上方落下来，玩家通过调整板块的位置和方向，使它们在屏幕底部 拼出完整的一条或几条。这些完整的横条会随即消失，给新落下来的板块腾出空间，与此同时，玩家得到分数奖励。 没有被消除掉的方块不断堆积起来，一旦堆到屏幕顶端，玩家便告输，游戏结束，本游戏得分越高越好。 #### 2.1.2 改编问题 在原问题的基础上我增加了俄罗斯方块的目标状态—指定目标状态需要达到的分数，达到时即为贪心搜索成 功。如果未达到目标状态就违反了俄罗斯方块的规则，就认为贪心搜索失败。同时搜索成功或失败时，输出整个搜 索路径中随机产生的俄罗斯方块形状、方块放置的状态和其中心被放置的位置，这个作为本次贪心搜索的搜索路 径。 ### 2.2. 俄罗斯方块规则 #### 2.2.1 游戏窗口 一个用于摆放小型正方形的平面虚拟场地，其标准大小：行宽为 10，列高为 20，以每个小正方形为单位。 #### 2.2.2 游戏规则 一组由 4 个小型正方形组成的规则图形，英文称为 Tetromino，中文通称为方块。共有 7 种，分别以 S、Z、L、 J、I、O、T 这 7 个字母的形状来命名。 I：一次最多消除四层 J（左右）：最多消除三层，或消除二层 L：最多消除三层，或消除二层 O：消除一至二层 S（左右）：最多二层，容易造成孔洞 Z （左右）：最多二层，容易造成孔洞 T：最多二层 主要规则如下： （1）玩家可以做的操作有：以 90 度为单位旋转方块，以格子为单位左右移动方块，让方块加速落下。 （2）方块移到区域最下方或是着地到其他方块上无法移动时，就会固定在该处，而新的方块出现在区域上方开 始落下。 （3）随着玩的时间越来越长，方块下落的速度也越来越快，难度越来越高。 （4）当固定的方块堆到区域最上方而无法消除层数时，则游戏结束。 （5）当区域中某一列横向格子全部由方块填满，则该列会消失并成为玩家的得分。计分规则：如果一个方块消 除了 n 行，则本次消除得分为 n(n-1)+1 分，即一次消除行数越多，得分越高。 （6）一般来说，游戏还会提示下一个要落下的方块，熟练的玩家会计算到下一个方块，评估要如何进行。 #### 2.2.3 总结 通过设计者预先设置的随机发生器不断地输出单个方块到场地顶部，以一定的规则进行移动、旋转、下落和摆 放，锁定并填充到场地中。每次摆放如果将场地的一行或多行完全填满，则组成这些行的所有小正方形将被消除， 并且以此来换取一定的积分或者其他形式的奖励。而未被消除的方块会一直累积，并对后来的方块摆放造成各种影 响。 ## 3. 项目问题分析 对于改编的俄罗斯方块问题，可以把每放一个方块的窗口界面状况和得分情况看做一个状态，只有当前的窗口 界面状况较好才能在未来获得较高的分数，状态转化的目的就是使得获得的分数可以达到目标状态的分数值，并且 状态转化的每一步都对未来状态有影响，同时只有保证自己能够存活下去才可能获取足够高的分数，因此综合考 虑，我决定选择在保证界面状态较好的情况下，使得每一次获取的分数值尽可能大这样的贪心搜索算法，只有每一 个状态最优，才能较快地搜索到目标状态。 俄罗斯方块问题由于下落方块具有随机性，并且当前仅提供两个方块的信息，无法获得未来 2 步以上的方块 信息，因此由于信息的局限性，本问题无法求出全局最优解，但通过构造代价评估函数，可以确保每步可以选择最 优的状态，进而在整体上能够实现较好的性能。但当最终将要抵达目标状态时，要判断此时每一次的得分情况，放 置分数超过目标状态。 ### 3.1. 问题的表示 对于问题的表示有以下的的元组表示法 p = (I, G, O, C) (1) 而对于本问题中 I 为游戏的开始阶段，即 10 列 20 行的空白游戏窗口，0 分的初始分数，G 为目标状态，即达到 了预定的分数和目标窗口（主要以是否达到目标分数来评判是否达到目标状态）。而对于 O 的选择则包括游戏规则 和贪心搜索方法，C : O × S → R+ #### 3.1.1 O 中的游戏规则 游戏规则如 2.2 所诉，这是贪心搜索算法索要遵循的规则。 #### 3.1.2 O 中贪心搜索 对于俄罗斯方块每次产生一个方块，遍历整个游戏窗口，找到方块可以放置的所有位置，放置过方块后改变的 游戏窗口均对应了一个状态，相当于在图中找到了当前结点的相邻点，然后通过构造出的代价评估函数，比较这些 相邻状态中，哪个状态的函数值最大（这个构造出的代价函数函数值越大，表示状态越优），当有多个状态的函数 值相等时，则比较其最优先函数值，值小的优先被选。以下算法将以构造代价评估函数为中心进行叙述。 ### 3.2. 基本共识 #### 3.2.1 经验共识 构造问题的评估函数，要以一定的基本共识作为基础，该共识是人们的经验总结和分析的结果。 共识一：尽可能地消除行，不要累积高度。 共识二：一次尽可能地多消除行，以便利用加分规则，多加分。 共识三：出现板块复杂的局面，要尽量避免“气泡”的数量，让空的格子较少。 总结以上共识可以得出以下五个参数 [[2](#_bookmark2)]。 #### 3.2.2 参数设置 当一块板块摆放之后，与这个板块接触的小方块的数量是一个需要考虑的参数。很显然，与值接触的小方块 越多，说明这个板块摆放再改位置后产生的“空洞”的数量越少，如果一个“棋盘”局面中空的小方块或者 “空洞”数量少则说明这个局面对玩家有利。 当一个板块摆放在某个位置之后，这个板块的最高点的高度是一个需要考虑的参数。这个高度会影响整体的 高度，当有两个位置可选择摆放位置时，应该优先放置再板块最高点的高度比较低的位置上。 当一个板块摆放在某个位置之后能消除的行数是一个重要参数。毫无疑问，消除的行越多越好。 游戏区域中已经被下落板块填充的区域中空的小方格的数量也是评价游戏局面的一个重要参数。很显然，每 一行中空的小方格数量越多，局面对玩家越不利。 游戏区域中已经下落板块填充的区域中“空洞”的数量也是一个重要参数。如果一个空的小方格上方被其他 板块的小方格挡住，则这个小方格就形成了“空洞”，“空洞”是俄罗斯方块游戏中最难处理的情况，必须等 上层的小方块都消除之后才有可能填充“空洞”，很显然，这是一个能恶化局面的参数。 所以摆放策略是板块放置的位置越靠下越好，方块之间越紧密越好，自身对消除行的方块贡献数量越多越好。 因此，要在追求消除行数最大化的同时，又要保证产生的“气泡”最少。 通过阅读论文 [[1](#_bookmark3)]得知，以上策略可以通过六个属性来抽象。 #### 3.2.3 属性抽象 landingHeight: 指当前板块放置之后，板块重�