第一部分（代码分析）在这里：
https :
//habr.com/post/420725/ 。
演算法
内容描述
该算法连续执行以下步骤：
- 他等到创建新的tetrimino。
- 检查新创建的tetrimino的类型，下一个tetrimino的类型（预览字段中的数字）以及比赛场的内容。
- 探索所有可能的方法在比赛场上添加两个Tetriminos并评估每种可能性。
- 移动新创建的tetrimino，使其与检测到的最佳概率的位置匹配。
这些步骤的每一个将在下面详细描述。
锁定搜寻
考虑俄罗斯方块的简化版本，其中形状不会自动掉落。 降低图形的唯一方法是轻轻降低图形。 从游戏中删除计时后，我们可以通过其位置和方向来充分描述活动的Tetrimino的状态。 该图具有初始创建的已知位置，并且以下操作用于将一种状态转换为另一种状态：
- 一步向下
- 还剩一步
- 向右移动一步
- 逆时针旋转一步
- 顺时针旋转
这些操作仅在所得四聚体的平方对应于运动场的空白单元时适用。 如果无法向下移动一级，则认为该状态为阻塞。 但是，由于我们简化了Tetris，等待锁定实质上是无限的，因此可以通过其他操作通过滑动和滚动进一步转换锁定状态。
使用广度优先搜索（BFS）可以找到许多阻塞状态，这些阻塞状态的操作序列最少。 如下所述，它使用队列来存储中间结果。
- 我们在创建时将状态排队。
- 我们从队列中推断出状态。
- 使用转换操作，我们得到以下状态。
- 如果它们之间没有向下移动，则将从队列中删除的状态被阻止。
- 我们将尚未访问的后续状态排入队列。
- 如果队列不为空，请从步骤2开始重复。
该程序使用以下字段将每个状态表示为一个对象：
{ x, y, rotation, visited, predecessor }在准备过程中，程序将创建一个三维状态对象数组（20行×10列×4圈），分别初始化
x ，
y和
rotation 。
当状态处于排队状态时，将标记
visited字段。 在BFS中，这是有效的，因为每个后续状态都会将总路径长度增加1。也就是说，通过增加路径长度，不可能创建需要插入队列末尾以外的位置以保持顺序的后续状态。
predecessor字段指示从中导出当前状态的状态对象。 当状态排队时设置。 创建状态没有以前的状态。
在搜索过程中检测到的一组阻止状态由Tetrimino的类型和运动场上填充的块确定。 通过遵循
predecessor链接到创建状态，可以阐明生成这些动作的顺序（以相反的顺序）。 在程序开始时将常量
PLAY_FAST设置为
true时，它会通过直接将tetrimino放在字段上并阻止它来完全跳过以前的状态。
一个状态对象的三维数组，一个队列和BFS被打包到一个类中。 他有一个搜索方法，可以接收运动场（二维数组），tetrimino的类型和侦听器。 每次检测到锁定状态时，通过将tetrimino添加到适当的位置来更新运动场。 然后，将改变后的比赛场以及关于改变的信息一起发送到收听者以进行处理。 收听者完成返回之后，将恢复比赛环境。
侦听器用于将多个搜索操作组合在一个链中，这使得可以找到所有可能的方法来向运动场添加两个（或更多）四聚体。 链中的第一个搜索引擎仅执行一次BFS。 但是，每当第一次搜索检测到锁定状态时，第二个搜索引擎就会执行BFS。 依此类推，如果链中还有其他搜索引擎。
最后一个搜索引擎的侦听器评估更改后的竞争环境。 当他找到比以前调查的结果更好的竞争环境时，他写下了处于锁定状态的已用对象，该对象此时使用了链中的第一个搜索引擎。 由于第一个搜索引擎仅执行一次BFS，因此其状态对象的
predecessor字段将保持有效，直到完成整个搜索过程为止。 也就是说，最后一个听众实质上记录了第一个tetrimino应该沿着的路径，从而最终达到了运动场的最佳配置。
评估功能
计分功能为改变后的比赛场地分配一个值-各种影响参数的加权和。 在这种情况下使用的评估功能基于
Islam Al-Ashi开发的功能。 它使用以下参数：
- 已清除的总行数：这是通过添加两个tetriminos将清除的总行数。
- 总阻挡高度 ： 阻挡高度是将人物锁定在运动场地板上方的高度。 这是如果您删除运动场上所有其他占用的正方形并保持图形的方向，则锁定图形将掉落的垂直距离。 总的阻断高度是两个tetriminos的阻断高度之和。
- “阱”单元的总数 ：阱单元是一个空单元，位于一列中所有被占据单元的上方，因此其左，右邻居为被占据单元； 在确定水井时，运动场的墙壁被视为占用的小室。 想法是，一口井是在顶部打开，在底部关闭并且两侧都被墙壁包围的结构。 孔壁中出现间歇性间隙的可能性意味着孔单元不一定会出现在列内的连续堆中。
- 列中的孔总数 ： 列中的孔是一个位于所占用单元格正下方的空单元格。 不将运动场的性别与其上方的单元格进行比较。 空列中没有孔。
- 列中的转换总数 ： 列中的转换是在单个列中与繁忙单元相邻的空单元（反之亦然）。 最上面占用的列块与其上方的空白区域的组合不视为过渡。 同样，也没有将运动场的地板与其上方的单元格进行比较。 因此，在完全空的列中没有过渡。
- 行中的转换总数 ： 行中的转换是在同一行中与繁忙单元相邻的空单元（反之亦然）。 运动场壁附近的空单元被视为过渡。 计算出比赛场地的所有行的总金额。 但是，在转换总数中不考虑完全空白的行。
El-Ashi建议，可以使用粒子群优化（PSO）算法找到有用的权重，该算法通过模仿自然界中观察到的群行为来迭代地改进解决方案集。 在我们的例子中，每个解决方案都是一个权重向量，选项的适用性由俄罗斯方块中的游戏决定； 这是他生存到比赛结束为止的tetriminos总数。
这些想法将在下面描述的Java版本中应用； 它运行在FCEUX之外，并且可以配置为以更高的速度运行的非图形内存游戏。 在准备好PSO之后，我很惊讶地看到算法在初始迭代之后没有进一步移动。 在此迭代之后，几个随机生成的解决方案变体已经表现良好。 几天来，这个集合的大小一直减小，直到只剩下一个选项为止。 以下是此解决方案的值：
| 参量 | 机重 |
|---|
| 已清除的总行数 | 1.000000000000000 |
| 总阻塞高度 | 12.885008263218383 |
| 孔细胞总数 | 15.842707182438396 |
| 列中的孔总数 | 26.894496507795950 |
| 列中的转换总数 | 27.616914062397015 |
| 总跳线数 | 30.185110719279040 |
通过将参数乘以它们各自的权重并将结果相加来估算运动场。 值越低，解决方案越好。 由于所有参数和权重均为正值，因此所有参数均会损害整体评估。 每个都必须最小化。 这也意味着最佳分数是0。
由于这些权重是随机选择的，因此合适值的范围可能非常宽。 这个特定的数字集和每个参数的估计相对重要性可能不相关。 尽管如此，密切关注它们还是很有趣的。
危害最小的参数是清除的总行数。 此选项有害的事实是违反直觉的。 但是，人工智能的主要目标是生存。 他没有争取最多的积分。 取而代之的是，他保守地打球，通常一次将队伍排位。 要获得Double，Triple或Tetris，您必须增加一些与长期目标背道而驰的目标。
列表中的下一个是总阻挡高度。 可以通过将Tetrimino降低到尽可能靠近地板的程度来将其最小化。 这是一种简单的策略，从长远来看有助于生存，从短期内有助于提高产品的包装质量。
分配给孔单元总数的权重似乎有些令人惊讶，因为经验丰富的玩家通常会故意建造深孔来连续收集多个Tetris（四行组合）。 但是如上所述，这是一个冒险游戏，与主要目标-生存相反。 另外，孔的数量是桩的“粗糙度”的指标。 当放置某些图形或图形组合时，一定程度的不均匀性是有益的。 但是高粗糙度会造成紧密包装的损坏。
列中孔的总数大约是列中过渡总数的一半。 这些参数可以组合并折叠为一个通用的相关参数，以获得更广泛，最有害的参数：过渡总数。
密集区域在各个方向上都有少量的过渡。 因此，由人工智能驱动的主要策略可以简述如下：将各个块尽可能地彼此包装。
其他选择
这是我在开发AI时尝试过的一些其他参数的列表：
- 堆高 ：繁忙的块可能会悬空在单元格上，从而形成突起和孔洞； 但是，不可能将占用的块锁定在完全空的行上。 因此，堆高是包含至少一个忙块的行数。
- 占用列总数 ：这是包含至少一个占用单元格的列数。
- 占用单元总数 ：在运动场上的占用单元数。
- 连接区域总数 ：此处使用填充算法计算连续连接区域的数量。 除了寻找被占领的“岛屿”之外，他还发现了沿两个轴延伸的孔。
- 柱高分散度 ：这是柱高变化的统计量度。 它是表面粗糙度的指标。
- 总适应值 ：计算下一个未知图形的堆的适应值。 它计算了可以在不出现新洞的情况下将7种形状添加到运动场的总数。 为了进行精确计数，将需要重复使用BFS。 但是，为了进行近似计算，搜索树可能会被截断。
- 下一个图形的平均评级 ：此参数通过分析下一个未知图形的所有可能性来加深搜索。 它使用其他参数来分隔每种图形的位置，然后返回7个等级的平均值。 对于该图的每个位置，都需要BFS。
- 平均模拟游戏 ：该参数模拟俄罗斯方块中的一系列游戏，使用其自己的伪随机数生成器选择棋子，并使用AI与它们一起工作。 在每个游戏结束时，使用其他参数评估比赛场地。 返回所有批次的平均值。
可以通过添加定制因子来定制所有参数。 例如，您可以为点，双，三和俄罗斯方块分配自己的权重，而不是简单地计算清除的行，从而模拟一个点系统。 如果同时清洗几行会损害生存的长期目标，则可以为单行分配负重量，而其他行则可以分配正值。
另一个有用的因素是偏移值。 例如，堆的完全平坦的表面的列高度分散为0。但是，完全平坦的表面不适合S和Z以及其他形状组合。 因此，通过减去常数，方差必须以最佳粗糙度为中心。
可以将调整后的参数和有偏差的参数提高到一定程度，以便在计算加权和之前可以对数或指数对比例进行缩放。 所有这些概率都可以视为可以通过PSO之类的方法优化的其他权重。
许多参数可以理解堆如何处理其他部分，例如处理表面粗糙度的部分，但是“总适应量”，“下一个图形的平均评分”和“模拟游戏的平均”评估更改后的游戏环境插入未包含在两个已知图中的图形。 在后续数字的研究中，由于快速消除了该系列，因此获得的附加知识的数量随着深度的增加而减少。 这意味着党的悠久历史不是那么重要，遥远的将来党的走向也不是很重要。 实际上，如果错误地随机设置了一小段数字，那么AI会使用以下几条数字清除受影响的行，从而迅速恢复游戏。 确定用于分析后续图形的最佳值需要进一步的研究。
参数有用性的另一方面是计算成本。 由于对两个图形的每个可能位置都调用了评估函数，因此成本大大增加。 由于AI必须能够实时播放俄罗斯方块，因此可以将提供有价值信息的成本因素交换为运行速度更快的更近似技术。
人工智能培训
无论采取何种策略，都有一些病理序列可以导致游戏结束。 最简单的例子是四联蛋白S和Z的无尽序列，如动画所示，它很快导致AI失败。
由于在完成多个批次之前需要运行几天的AI变量并计算平均值，因此将平均批次持续时间用作PSO控制指标是完全不切实际的。 取而代之的是，您可以通过增加S和Z的频率来以受控的速度来增加游戏的复杂性，随着时间的推移，这将导致仅创建这对数字。
我尝试使用这种教学方法，但发现教学AI频繁使用S和Z会实际上损害应付均匀分布的随机形状的能力。
在B型游戏启发下的另一种方法中，PSO度量标准控制行清洗的频率。 公平竞争的领域是由10条线组成的随机垃圾块图，每次清除该行时，下面都会出现一条新的垃圾线，以恢复堆的高度。 由于运动场的宽度为10列，每个Tetrimino平均由4个正方形组成，因此AI应该每2.5个Tetrimino清除一行。 为了摆脱垃圾，他必须更快地做到。
不幸的是，该技术也没有提高性能。 一个可能的原因是随机垃圾孔与AI在真实游戏中处理的字符串不完全匹配。 另外，清洁行是短期目标。 贪婪的行清洁并不一定会改善长期生存率。 有时，不应触摸这些行来处理后续图形的某些组合。
Colin Fei在他的网页上提出了另一种方法。 他创建了直方图，以显示试批期间每一行中被阻塞的形状的百分比。 有趣的是，无论创建多少图形，所有直方图看起来都几乎相同。 基于此，他建议您在评估在创建行中阻塞人物的统计期望时，可以对任何试用批使用功能的近似图像，从而获得AI玩到游戏结束为止的时间。 我决定探索这种可能性。
下图是许多试验批次的热图，总计包含20.939亿特替米诺。 每个单元格根据锁定在其中的形状的百分比进行着色。 为了增强视觉对比度，选择了非线性调色板。 通过将单元格值除以最大单元格百分比来归一化单元格值，然后将其声明为0.19的幂（请参见
“伽马校正” ）来创建该图。
| | 色泽 | 百分比 |
|---|
| ■ | 0.00000000 | | ■ | 0.00000315 | | ■ | 0.00024227 | | ■ | 0.00307038 | | ■ | 0.01860818 | | ■ | 0.07527774 | | ■ | 0.23582574 | | ■ | 0.61928352 | | ■ | 1.42923040 | | ■ | 2.98867416 | | ■ | 5.78182519 |
|
第17和18行中的深橙色和红色条纹表示绝大多数图形都位于该位置。 下方的淡绿色是图形几何形状的结果：7种Tetrimino类型中只有4种可以显示在底线上。 下角是黑色的，因为不可能到达那里。
沿着每条线的颜色几乎是均匀的，这表明形状在水平方向上是均匀分布的。 可以通过查看各种形状的直方图来解释微小的差距：
事实证明T是最通用的类型：其直方图比其他所有类型的直方图更均匀。 直方图J中的异常-墙壁影响的结果； 侧面列中只有
Jr和
Jl ，这使得AI会更频繁地使用第1列和第9列进行补偿，而L的情况也是如此。彼此不是完美的镜像。 类型O被限制为19×9的比赛场地，看起来AI在侧面而不是在中央使用O的可能性更大。 Tetrimino I移至右侧，因为其起点位于此处； 因此，很少在第1列锁定。
该表显示了每一行中被阻止的数字的百分比。
| 弦乐 | 百分比 |
|---|
| 0 | 0.0000000000 |
| 1个 | 0.0000000000 |
| 2 | 0.0000004902 |
| 3 | 0.0000026472 |
| 4 | 0.0000066180 |
| 5 | 0.0000172557 |
| 6 | 0.0000512280 |
| 7 | 0.0001759400 |
| 8 | 0.0006681210 |
| 9 | 0.0023187901 |
| 10 | 0.0077928820 |
| 11 | 0.0259672043 |
| 12 | 0.0866187068 |
| 13 | 0.2901315751 |
| 14 | 0.9771663807 |
| 15 | 3.3000408353 |
| 16 | 10.6989059268 |
| 17 | 28.5687976371 |
| 18岁 | 50.0335706162 |
| 19 | 6.0077671454 |
这是值的图形：
如果不考虑第19行，则该图将显示指数增长。
以下是相邻行中锁定形状的数量比率的列表。| 字符串A /字符串B | 比例（％） |
|---|
| 1/2 | 0.00 |
| 2/3 | 18.52 |
| 3/4 | 40.00 |
| 4/5 | 38.35 |
| 5/6 | 33.68 |
| 6/7 | 12/29 |
| 7/8 | 26.33 |
| 8/9 | 28.81 |
| 9/10 | 29.76 |
| 10/11 | 01/30 |
| 11/12 | 29.98 |
| 12/13 | 29.85 |
| 13/14 | 29.69 |
| 14/15 | 29.61 |
| 15/16 | 30.84 |
| 16/17 | 37.45 |
| 17/18 | 57.10 |
| 18/19 | 832.81 |
这些线条16–19考虑了与运动场地板互动的人物，因此可以将其丢弃。在行中，0–5选择太小而没有意义。其余比率，对6 / 7-14 / 15，几乎相同；他们的平均值是29.24％。这意味着无论堆的高度如何，堆增长一行的概率几乎相同。这是合乎逻辑的，因为当紧密打包时，Tetris规则会限制堆顶部的交互。下图显示了第6-15行中10％的数字的对数。它接近于确定系数接近1的完美直线。假设第0行中的形状百分比约为10 -7.459％，则从上述线性回归得出的公式给出了与Y轴的交点。该值的倒数使我们对统计值的期望达到2,877,688,349 tetrimino或1,151,175,340行，直到游戏结束。这使我们了解日志10每行中的数字百分比一直保持线性直到0行。但是，当堆几乎达到运动场的上限时，活动自由度受到限制，以致违反了此属性。此外，在第0行挡住一块并不一定意味着游戏结束。如果有创建新图形的地方，您仍然可以保存。评估AI强度的另一种方法是，在完全清洁运动场之间，测量所创造形状的平均数量。仅需5个Tetriminos即可完全清洁。例如，除其他可能性外，这可以通过在运动场的地板上布置五个O形来实现。通常，由于每个tetrimino都由4个正方形组成，并且运动场的宽度为10个正方形，因此在完全清洁之间创建的数字应为5的倍数（从4×5n = 2×10n）。我的AI在全场清洗之间创建的平均形状数量为1,181，这是一个相当小的数目。由于完全清除就像重新启动游戏一样，整批可以看作是重新启动游戏的漫长过程，然后快速进入游戏结束。像上述替代序列一样SZ，导致游戏结束的病理序列通常很短。下面的直方图显示了AI在指定数量的已创建图形之后完全清除该字段的概率（以百分比为单位）。上式中的度数顺序决定了AI的下降率以及强度。根据这个公式，大约0.4％，即253场比赛中大约1场是从空的比赛场开始的，仅用5个Tetriminos进行了彻底清洗。与Faye的建议相反，线性近似和指数近似中的常数需要非常大的样本量，因此R 2接近1，因此此方法不适用于PSO。但是，长批次获得的常数可用于优化近似函数，该近似函数可为短批次产生可能的常数值。在一种开发反馈回路中，可以在PSO中使用优化的逼近函数，从而改善AI，然后可以将AI用于计算新的常数，作为逼近函数的参考标准。Java版本
关于程序
对于不熟悉Lua的开发人员，我在源zip文件中添加了Java AI端口。类几乎是基于闭包的Lua对象的逐行转换。配套
该代码分为两个包：tetris.ai 包含AI类和接口。tetris.gui 创建运动场的图形模型。
AI类和接口
具有适当名称的类Tetriminos描述tetrimino。它的用法类似，enum并且包含所有类型的Tetrimino的常数： public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6;
NONE表示未分配的值。它用于运动场的空白单元格。还Tetriminos包含定向表的两个模型。PATTERNS-这是一个4维整数数组（类型×旋转×正方形×坐标），其中包含正方形的相对坐标；排列这些线，以使每种类型中的形状创建方向都最先。ORIENTATIONS是另一个模型，是对象的二维数组（类型×旋转）Orientation。每个都Orientation包含正方形的坐标作为对象数组Point。它还具有描述相应方向允许位置范围的字段。 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... }
public class Point { public int x; public int y; ... }
在StateBFS操纵的对象中使用Tetrimino旋转（两个方向表中的第二个索引）。 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... }
x，y并rotation一起描述图中的位置和方向。由于Tetrimino类型从创建到阻塞一直保持不变，因此它的字段是可选的。包含BFS算法的类在创建时会创建Searcher所有可能对象的完整集合State： private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } }
尽管Java具有丰富的Collections API，但它Searcher包含自己的队列实现。该类Queue用于State.next将对象State连接到链表中。由于所有对象State都是预定义的，并且每个对象State最多可以添加到队列中一次，因此该队列可以就地工作，从而消除了在一般队列实现中使用的不必要的临时容器对象的需求。BFS的“心脏”是如下所示的方法search。 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; }
它生成具有创建的tetrimino状态的队列，然后从已从队列中删除的状态中顺序检索子元素，并在出现在运动场上时将它们重新添加到队列中。将search包含已占用和空单元格，已创建的Tetrimino类型和任意标识符的游戏字段传递给method 。在执行BFS期间，只要检测到锁定位置，就会调用一个侦听器。 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); }
侦听器将收到一个已更改的竞争环境，其中包含锁定在适当位置的tetrimino。还发送创建的Tetrimino的类型和任意标识符。最后一个参数State是阻止Tetrimino的参数。通过遵循链接链State.predecessor，您可以恢复到State创建形状的所有方式。State.visited可以实现为boolean;但随着搜索之前理清所需的所有设施State救济visited上false。取而代之的是，我将一个visited值int与计数器进行了比较，并随每次调用增加。方法addChild预先排队后续状态。后续状态必须在场地内，并且位于比赛场地的4个空白单元中。此外，必须不访问后续状态State。如果该位置有效，则即使由于已经访问了后续状态而无法将其排队，也addChild将返回true。该方法search使用返回addChild值来确定是否可以创建形状。如果无法创建该图，则说明该堆已到达顶部，无法再执行搜索；因此它返回false。可退还addChild还研究了其重要性，以寻求进一步发展的可能性。如果无法完成此操作，则当前状态为锁定位置，并且呼叫开始lockTetrimino。该方法lockTetrimino更改了运动场，调用了侦听器，然后恢复了运动场。数组的每一行playfield包含1个其他元素，用于存储该行中已占用的单元格数。通过该方法执行元素的递增，lockTetrimino因为它会将单元标记为繁忙。收听者收到修改后的比赛场地时，他会打电话PlayfieldUtil.clearRows删除填充的行该方法通过检查数组的附加元素中的值来识别它们。为了删除字符串，代码利用了以下事实：在Java中，二维数组本质上是数组的数组。它只是按下链接到字符串。PlayfieldUtil包含自由行；他通过插入其中一个链接来完成清洁过程。在执行移位之前，要清除的行的索引存储在其他行元素中。然后，到该行的链接被压入堆栈。然后听众打电话PlayfieldUtil.restoreRows放弃对比赛场地所做的更改。步骤以相反的顺序被取消。首先，我们从顶部获得一个自由行。然后，从堆栈中检索已填充的行，并还原其他元素的索引。它用于移动行参考并返回到删除行的位置。最后，恢复一个附加元素，为它分配比赛场地的宽度值-填充行中占用的单元数。还有PlayfieldUtil一种方法evaluatePlayfield可以计算4个评估参数并将其写入以下所示的容器类中。 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; }
班级管理所有这一切AI。它包含Searcher通过如下所示的侦听器连接在一起的两个对象。 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); }
一个类AI可以处理任意数量的对象Searcher，但是Nintendo Tetris仅预先显示一个形状。对象Searcher存储在数组中，上面显示的代码用作其公共侦听器。传递给该方法的随机标识符Searcher.search实际上是数组的索引，这也是搜索的深度。调用侦听器时，标识符会将调用定向到Searcher链中的下一个。如果他到达阵列的末尾，则评估比赛场地。当他找到一个健身得分更高的运动场时，他会State从Searcher链中的第一个开始写下被封锁的那个。AI包含一个search接收比赛场地的方法和一个包含所创建和下一个Tetrimino类型的数组。他回来了State包含应该阻止第一个Tetrimino的位置和旋转。他不专注于第二种四聚体。下次调用它时，它将重新计算分数。如果堆太高并且链Searcher无法放置两个tetriminos，则它将AI.search返回null。 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; }
人工智能挑战
由于Java版本与FCEUX无关，因此它有可能用于其他项目。对于那些对将AI集成到其他地方感兴趣的人，本节描述了您需要的一切。首先，创建一个instance AI，instance PlayfieldUtil和array来保存所有已知类型的tetrimino。另外，PlayfieldUtil.createPlayfield通过调用创建运动场的实例。它返回带有附加列的二维数组，我们在上面进行了检查。您可能还需要一个随机数生成器。 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random();
最初，比赛场地为空，并且所有单元格都是相关的Tetriminos.NONE。如果您以编程方式填写单元格，则不要忘记写下playfield[rowIndex][AI.PLAYFIELD_WIDTH]每一行中已占用单元格的数量。用最初创建的形状和下一个形状的类型填充tetrimino类型的数组，这些类型通常是手动选择的。 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7);
然后，我们将竞争环境和类型数组传递给方法AI.search。他将返回State您需要封锁第一个Tetrimino的地方。如果他返回null，那么比赛结束是不可避免的。 State state = ai.search(playfield, tetriminos);
如果需要从创建图形到锁定的State方法，则将其传递给method AI.buildStateList。 State[] states = ai.buildStatesList(state);
要更新游戏环境，我们将PlayfieldUtil.lockTetrimino其及其类型和对象传递给它State。此方法自动清除填充的行。 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state);
再次致电之前，AI.search您需要随机选择下一个tetrimino。 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7);
在一起，看起来像这样： AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) {
您可以使用更有趣的方式来显示正在发生的事情，而不必以文本形式显示比赛场...运动场显示
该类TetrisFrame模仿Nintendo Tetris图形，包括本文前面部分中描述的行为功能。要查看实际效果，请运行它tetris.gui.Main。与Lua版本一样，我们可以通过更改文件开头的常量值来调整游戏速度。 public static final boolean PLAY_FAST = true;
TetrisFrame有4种操作屏幕的方法。该方法displayTetrimino在指定的坐标中渲染活动的tetrimino。它接收一个delay参数，该参数使方法等待返回指定数量的动画帧。 public void displayTetrimino(int type, int rotation, int x, int y, int delay)
该方法lockTetrimino将图形锁定在适当的位置。行计数器，点，级别和tetrimino颜色会相应更新，从而表明当值超过允许值时的预期好奇行为。为参数分配animate值true包括接收俄罗斯方块时的行清理动画和屏幕闪烁。该方法将被阻止，直到动画结束。 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate)
updateStatisticsAndNext 对新创建的tetrimino执行统计计数器的增量，并更新下一个图形的显示。 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino)
该方法dropTetrimino创建形状并允许其在“重力”的影响下下降，而无需尝试旋转或移动它。返回Main时将它用于最后两个数字。如果参数很重要，那么如果不可能创建人物，那么游戏结束的帷幕将掉落。与所有其他方法一样，此方法将阻塞直到动画结束。仅当它可以在繁忙的运动场上创建人物时，它才会返回。AI.searchnullanimatetruetrue public boolean dropTetrimino(int type, boolean animate)
这4种方法必须由工作流调用，但TetrisFrame必须在事件调度线程本身中创建。要了解如何完成此操作，请参阅类Main。为了感兴趣，他Main使用了一个类Randomizer，该类模拟Nintendo Tetris的有偏伪随机数生成器。该软件包tetris.gui.images包含与显示相关的文件。tiles.png-这是包含所有图块图形的模式表。background.dat存储组成背景的图块的标识符；从中提取的数据$BF3F。它colors.dat包含字节，这些字节会生成从级别138开始出现的异常正方形颜色。它ImageLoader包含一个NES调色板表，并且ImagePane存储了所显示的级别值的完整集合。其他项目
潜在地，可以使用代码代替编写演示模式。实际上，可以充分利用AI清除整个比赛场地的速度，永久演示这种演示。为此，在伪随机数生成器中，您需要使用一些任意常量作为种子，这将为我们提供确定性的Tetrimino序列。将记录前两个Tetrimino序列。当AI达到全域清除时，接下来的两个Tetriminos将与序列的前两个进行比较。如果它们匹配（预计每49次完整场清洗将发生此事件），则可以将伪随机数生成器传递给与种子相同的常量，这将创建一个无限的演示循环。周期的持续时间可能很长，以掩盖它是一个周期的事实。也该演示可以在循环中的任意点开始，每次创建一个新的演示。使用AI的另一种可能性是创建“玩家与计算机”模式。在多玩家俄罗斯方块中，同时清除多条线时，垃圾线出现在对手场地的下部，从而增加了比赛场地。由于AI可以玩B型游戏，因此AI必须能够保护自己免受碎片侵害。但是，如前所述，AI玩法保守，通常会努力一次清除一条线。也就是说，他将能够防御攻击，但不能攻击。为了能够更改他的行为，我创建了一个名为的接口IChildFilter。 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); }
AI有一个替代的构造器得到一个实现IChildFilter。如果可用，IChildFilter.validate它可以作为对子状态许可的附加检查；如果返回false，则子状态不会排队。WellFilter是一个实施IChildFilter旨在捡起四排（俄罗斯方块）。像在世的球员一样，她逐渐在比赛场地的最右边建造一口井，从下到上逐行上升。由于它逐行工作，因此它拒绝在最右边的列上添加一个正方形的子状态。当整个行（井列除外）完全填满时，AI会前进到下一行。当这些线中有4条或更多准备就绪时，它可使“棒”掉入井中并获得俄罗斯方块。另外，跟踪堆高；如果太大，则WellFilter不再影响AI。要对其进行测试，请进行Main以下更改： AI ai = new AI(new WellFilter());
WellFilter可以，但是效果不是特别好。它包含一个简单的启发式设计，用于演示该概念。为了更频繁地使用俄罗斯方块，您需要使用一种更复杂的策略，也许可以使用PSO对其进行优化。此外，您可以使用子状态过滤来生成模式。以下是他的能力示例PatternFilter。PatternFilter从底部到顶部逐行构建图像，类似于它的工作方式WellFilter；但是，它只保留与PatternFilter特定模式相对应的子状态，而不保留最右边的列。构造函数PatternFilter获取包中图像之一的名称tetris.gui.patterns，它将其用作模板。每个20×10的图像包含对应于运动场中的单元的黑白像素。 AI ai = new AI(new PatternFilter("tetriminos"));
上面显示的代码行创建了7种Tetrimino的轮廓。另一个大的tritrimino T旋转了一个角度的例子。另一个例子。如果仔细观察，将会看到游戏的名称。就像WellFilter，PatternFilter无非是概念的证明。由于试图获得这些图案通常会在游戏结束时结束，因此他处理的图案仅限于比赛场地的底部。但是，这是一个有趣的想法，值得进一步研究。游戏手柄版本
Lua脚本和Java程序忽略了重力。对于他们来说，下降速度并不重要，因为根据配置的不同，它们要么将图形立即传送到所需位置，要么沿任何选定的路径拖动。在某种程度上，他们只是模仿俄罗斯方块，而不是玩它。但是，在带有源文件的zip文件中，还有另一个Lua脚本，该脚本通过生成游戏手柄按钮的信号来播放，该脚本允许游戏控制人物，重力和其他所有东西的运动。增加重力极大地扩大了搜索空间，迫使AI考虑到操纵形状的狡猾规则。这些规则的详细信息在文章的第一部分中进行了描述，可以通过直接研究代码来充分理解。这里是最重要的：
- : , .
- «» .
- «» «» .
- .
- .
- .
- .
- , .
- A B .
- «» «» 6 16 . «» «» , .
- «» 3 .
- 96 . , — .
为了适应所有这些规则，历史信息必须嵌入搜索状态中。他们需要在字段中存储每个按钮的保持帧数以及上一次自动释放后的帧数。每组唯一的值（包括坐标x）y和tetrimino旋转表示一个单独且唯一的状态。不幸的是，可能性的数量如此之多，以至于无法完全搜索该空间。游戏手柄的AI版本仅探索其中的一部分。AI使用State具有以下字段的对象： { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor }
按下并释放移位按钮，而不是在交替的帧中使用自动AI移位。因此，他只需要监视按钮是否被按下，而不需要监视多长时间。由于没有自动旋转，同样的想法适用于按钮A和B因此领域Left，Right，A和B可以解释为列举包含下列值中的一个： { RELEASED, PRESSED }
另一方面，对于软下降，必须首先按住“向下”按钮三帧，这需要存在4种状态： { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES }
Down从值递增地增加RELEASED前PRESSED_FOR_3_FRAMES，在其中有一个缓坡。之后，它可以接收一个值RELEASED或返回PRESSED_FOR_2_FRAMES，在初始延迟后每隔第二帧引起一个软下降。它不能RELEASED来自PRESSED_FOR_1_FRAME或来自PRESSED_FOR_2_FRAMES。实际上，Lua代码使用整数常量，但是原理是相同的。类似地，visited并且predecessor，fallTimer它被分配在辅助队列状态书写时所获得的值;它fallTimer比父状态的值大一。条件包含fallTimer等于下降速度，表示在该帧中发生自动下降，对于此状态的后续状态，值fallTimer将为0。每个Searcher预定义8-包含所有可能状态（20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B）的数组，并且BFS的执行类似于为 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end
如下面的伪代码所示，该函数addChild考虑了每个帧中发生的事件的顺序（例如，移位，旋转和下降）。 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end
与以前的版本一样，它AI.search返回对象链State。但是在这种情况下，每个State按钮都包含许多需要在每个框架中按下的按钮。场x，y并且rotation不用于操纵数字，但是可用来验证的数字移动的正确性。尽管由于上述限制，搜索空间已大大减少，但完成搜索需要1-3秒。如果运行它，则在创建每个tetrimino后都会发现暂停。此外，这些动作看起来非常不自然。通常在锁定之前转一圈。但是，即使在最大速度下，这种AI的运行方式也与忽略重力的版本几乎相同。要对其进行检查，请运行zip文件，该文件lua/NintendoTetrisAIGamepadVersion.lua位于带有source的zip文件中。解决重力的一种简单方法是仅通过转动，移动，然后下降到底部来限制图形的移动。这个想法是，如果您摆脱了滑动和滚动，那么图形的垂直速度将不会对AI产生任何影响。他要做的只是将图形传送到所需的列，其余的将由重力完成。此技术的另一个优点是搜索空间很小，可以实时播放，而不会延迟计算。但是，这种方法的缺点是，如果没有滑动和滚动，AI的效果会更差。但是，无法实时播放的Tetris AI几乎一文不值。加法
之前，我编写了一个插件，该插件在程序上模拟了俄罗斯方块中的播放器。但是，我的项目有一些缺点：- 该机器人关闭了重力，使您可以进行滑行和滚动，这在Nintendo Tetris的最低级别上已超越了播放器的功能。他从不降低身材，但降低身材的唯一方法是控制下降。也就是说，他在理论上理想的世界中工作。说穿了，他作弊。
- . — , . Double, Triple Tetris, — , . 90. , , 29 - .
- . . . , Tetris .
在本节中，我将讨论一种在不禁用重力的情况下玩Nintendo Tetris的高级机器人。他评估风险并进行管理，在达到高下降速度之前积极争取最大分数。
录影带
在下面显示的所有视频中，观看机器人从19级开始获得Nintendo Tetris积分的最大数量。
资料下载
TetrisAI_2018-01-28.zip该文件.zip包含：src -源代码树。TetrisAI.jar -编译的二进制文件。lgpl-2.1.txt -免费软件许可证。
发射
先决条件
- Nintaco是NES / Famicom模拟器。
Tetris (U) [!].nes -Nintendo Tetris ROM文件。
插件启动
- 启动Nintaco并打开
Tetris (U) [!].nes。 TetrisAI.jar从下载的文件中提取.zip。- 通过选择工具|打开运行程序窗口。运行程序...
- JAR Find JAR… .
- Load JAR, .
- Run.
- ,
GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), . A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .
值得考虑的是，该机器人仅适用于19级及更高级别。在较低级别，他将无法控制作品。速度参考
为了使游戏运行更快，请选择“机器” |“ 速度 最高
详细资料
高原
低于10级时，每个级别的下降速度都比前一级别略高。但是，在10及更高的级别上，有几个平稳阶段，在几个平台上，速度保持恒定。这是触发机制工作方式的结果。速度表示为每次下降的帧数，它是整数值。也就是说，对于更高的级别，剩下的选项不多：10–12、13–15、16–18、19–28和29+分别是5、4、3、2和1帧用于下降。该机器人的开发仅考虑了19-28的平稳期。在偶数帧中，他单击游戏手柄“左”，“右”，A，B或什么都没有。在奇数帧中，它无需按下任何按钮即可自动下降。似乎游戏没有感知到与旋转一致的水平运动。因此，每个按钮均按偶数帧独立按下。与高水平演奏的大师不同，该机器人没有利用延迟自动换档（DAS）（也称为自动重复）及相关技术。他的作品更让人联想到托尔·阿克伦德（Thor Akerlund）的振动拇指技术。但是，它将振动频率增加到游戏允许的理论最大值。单，双，三和俄罗斯方块奖励40、100、300和1200分。分数乘以等级数加1。换句话说，要获得最大分数，玩家必须争取最大数量的俄罗斯方块，并尽可能长时间地在高等级上玩。级别19是可以选择的最高级别，它可以使机器人直接跳到高原19-28。但是，由于我在上一部分中提到的关卡计算机制中的错误，游戏将在清除140行（而不是预期的200行）之后进入第20级。此后，游戏将每10行更改一次关卡。但是，到达230行后，机器人会从高原上升并迅速放弃。也就是说，他需要在清洁230行之前拨打尽可能多的俄罗斯方块。软下降
软下降也可以增加点数。为了获得积分，必须将人物形象轻轻降低以锁定比赛场地。放置图形时，沿途发生的任何短期软下降都不会影响得分。如果下降成功，则玩家在软下降过程中每越过一条线将获得1分。并且即使软下降导致清除行，结果值也不会乘以级别编号。柔和的下降对总分的影响很小。但是，如果可能，机器人将通过单击“向下”获得这些点来完成图形的放置。在极少数情况下，它可以平均非常高的分数与超过最大分数之间的差异。人工智能算法
在创建形状时，机器人会探索当前形状和下一个形状的所有可能位置。允许的放置位置是人物放置在占用的牢房或运动场地板上的位置。从创建人物的位置开始，可以通过一系列水平移动，转弯和下降来达到该位置。使用BSF可以找到有效的位置和路径序列。将一块放置在运动场上会产生以下结果：4个空单元被占用，并且所有已填充的行都被清除，从而使行下降。对于当前人物的每个允许放置以及与之相关的后果，机器人会检查下一个人物的每个允许放置，并评估后果的组合。提出了这样的搜索链SearchChain。每个合并的结果将传递到评估功能，该功能计算比赛场地的内容。得分最低的组合获胜，并且当前的棋子将相应放置。搜索链结果仅影响当前形状。创建下一个图形时，将与下一个图形结合对它进行评估，依此类推。评估功能
评估函数是以下参数的加权和：- 清除的总行数是通过添加两个tetriminos清除的行数。
- – , . — , , .
- - – .
- – , -.
- – , . . .
- – . , 1. , , .
- – , . — , — .
- – . , (20).
- – . , 0.
- – , ( ) .
- : — , ( ) . . . .
- – . , 1 , 1, — 0.
- – .
- – .
- – .
- – . .
- – .
机器学习
为了找到评估函数的权重，我们使用了脚注[1]中描述的粒子群优化（PSO）方法的一种变体。为了获得良好的收敛性能，应用了建议的惯性和加速度系数。粒子步长的最大大小取决于其速度值的限制。在每次迭代期间，并行评估粒子以充分利用可用的计算资源。此外，在检测到收敛后（经过一定数量的迭代后没有改善），PSO设置为使用随机选择的权重自动重新启动，这使我们能够进一步探索搜索空间。通过模拟在19-28级平稳状态下的100批批次的完成情况来评估每个粒子位置矢量。一整批工作涉及清洗230行，但许多工作以该字段溢出而告终。排序批次分数，并将粒子分数确定为100批次中33的平均值。这个想法是基于进取心进行选择。上三分之一的粒子仅用于所需的图形序列，这限制了对保守游戏的需求。结果，他们倾向于将常规游戏推到边缘，等待下一个“坚持”。在PSO之前生成了100个批次的图案序列，并且一次又一次使用相同的序列。这是固定搜索空间所必需的，以便可以将解决方案选项进行相互比较。序列是使用真实的PRNG Nintendo Tetris的逻辑创建的，旨在减少重复出现的机会。但是PRNG也有缺点（请参阅上一篇文章“选择Tetrimino”部分）：它没有均匀地选择数字。最初的尝试导致机器人行为过于激进。如果他们超过19-28的稳定水平，他们通常会达到最高分。但是，不幸的是，它们经常为时过早导致字段溢出。为此，我们采取了四个步骤来“调整”僵尸程序：- : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
- . , , 7 . .
- , , . , 7 .
- , , . , . , .
在将所有这些规则应用于“镇静”机器人之后，PSO方法具有以下权重：| 参量 | 机重 |
|---|
| 已清除的总行数 | 0.286127095297893900 |
| 总阻塞高度 | 1.701233676909959200 |
| 孔细胞总数 | 0.711304230768307700 |
| 深井总数 | 0.910665415998680400 |
| 列中的孔总数 | 1.879338064244357000 |
| 总加权柱孔 | 2.168463848297177000 |
| 列中孔深的总数 | −0.265587111961757270 |
| 最小柱孔深度 | 0.289886584949610500 |
| 最大柱孔深度 | 0.362361055261181730 |
| 列中的转换总数 | −0.028668795795469625 |
| 总跳线数 | 0.874179981113233100 |
| 总柱高 | −0.507409683144361900 |
| 堆高 | −2.148676202831281000 |
| 列高散点图 | −1.187558540281141700 |
| 占用单元总数 | −2.645656132241128000 |
| 占用单元格的总加权数量 | 0.242043416268706620 |
| 柱高分散 | 0.287838126164431440 |
由于该链追求的是将评估功能最小化的组合，因此具有正权重的参数可以被视为奖励，其余部分则被视为罚款。但是权重并不一定显示相应参数的重要性。它们未归一化，因此无法进行比较。AI力量
为了评估AI的实力，在19-28的稳定期收集了大约170万个模拟游戏的结果（以点为单位）。分数不反映29级或更高级别的比赛，也不考虑从软下降获得的分数。但是，它包括由于场地溢出而提前完成的游戏。 Nintendo Tetris PRNG逻辑用于生成Tetrimino序列。在这些结果中，最大分数为1,313,600，最小分数为0，平均分数为816,379，这似乎很小。但是，如下所述，数据是失真的，因此中值989,200分可以更好地理解典型值。如上所述，PSO基于最佳三分之一批次的平均值来优化重量。在这种情况下，最好的三分之一的平均分数是1 108860。实际上，最好的75％的平均分数是1,000,000。机器人有47％的可能性达到29级的积分极限。它有61％的可能性将900,000积分获得该等级29.下图显示了得分达到29级的可能性。似乎该概率线性下降至大约900,000点。然后，它变成一条倒S形曲线。下面是一个平滑的直方图，其中包含每个得分方的参与人数。它的形状由上面显示的图的导数确定。如果您忽略波动，那么最多可达到约900,000个单位，然后以大约1,050,000点为中心进行正态分布。波动的原因尚不清楚。似乎积分的数量喜欢以20,000积分的增量跳跃。也许这是由于堆构建周期和获取俄罗斯方块而引起的。RAM和ROM分配
为了操纵CPU内存，发送按钮点击并接收帧渲染事件，该插件使用Nintaco API。使用Nintaco调试工具发现了所有内存地址，并且信息已添加到Data Crystal ROMhacking.net Wiki中。在源代码中，它们看起来像interface中的常量Addresses。
参考文献
- van den Bergh, F.; Engelbrecht, AP (2006)
A study of particle swarm optimization particle trajectories
In: Information Sciences 176 (2006) (pp. 937–971)
Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf