imported>風洛霊flore2024年8月28日 (三) 13:33的版本
(差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)
|
|
本条目介绍的是随机器故意给玩家发送不利方块的游戏。如果您寻找的是以帽子为主题的一种下落消除游戏，请参阅 Hatris。
|
|
本条目介绍的内容不是官方的俄罗斯方块游戏。
这个游戏模拟了俄罗斯方块的玩法，在名称中使用了「Tetris」或「俄罗斯方块」，但没有经过俄罗斯方块公司官方授权。
|
| Hatetris |
|---|
| 开发 |
qntm |
|---|
| 游戏平台 |
JavaScript |
|---|
| 发行时间 |
2010年 |
|---|
| 最新版本 |
#153（2022年9月2日） |
|---|
| 预览块数 |
0 |
|---|
| 场地大小 |
10 × 20 -4 |
|---|
| 暂存块 |
无 |
|---|
| 硬降 |
无 |
|---|
| 旋转系统 |
专用 |
|---|
|
|
|
|
|
|
|
|
Hatetris 是一个四连方块网页游戏。
该游戏会根据场地情况计算并发出对玩家最不利的下一块，总体上很难消行。
该游戏有三个主要的创作目的：使方块玩家们受苦，证明（或证伪）“俄罗斯方块一定能在输掉之前至少消一行”的命题[1]，改进 Stacked Odds 和 Bastet 在“逆境方块”主题上的不足之处[2]。
玩家需要和魔鬼出块规则斗智，摆出即便用最差的方块也能多多消行的形状。
玩法
尽量多消行。
Hatetris 自带四种[注 1]出块算法：Hatetris（总是给出最差的方块）、Lovetris（全是 I）、Brzustowski 1992（SZ 连涝）[注 2]、Burgiel 1997（SZ 交替）[注 3]
重力是零，方块只能手动降落；
锁定延迟无限大，方块接地时只能手动锁定。
死亡判定：顶出死亡——场地最上方 4 行有实格。
触发死亡后，录像代码出现。
操作
键盘：左右键横移，上键顺时针旋转，下键软降。
这四个操作都可以独立长按，可跨块，新操作打断旧长按。
鼠标：点击相应的动作标志（但只能单点，即使用了鼠标键也没有长按）。
悔棋：Ctrl + Z / Y。
方块环境配置
正在操作的方块是红色，已经锁定的方块是青色[注 4]。
各方块在代码层面统一使用 4×4 范围框，入场位置如上图所示。
其中，X 格坐标为 (6,19)。
下图是各方块的入场朝向，每次旋转将范围框内容顺时针旋转 90 度：
Hatetris 没有踢墙。
Hatetris 的出块原理
- 原序（从差到好）为 SZOILJT，只要 7 种方块都不能构成消行，就一定出 S
- 如果有 1–6 种方块能构成消行，就在不能消行的方块当中取最能拔高单列堆叠高度的那种方块，若打平，按原序取最差的块
- 如果 7 种方块全能构成消行，就在不能消出原先井形的方块当中按原序取最差的块
高分思路
|
|
这一章的内容整理自 David & Felipe 的相关文章（更新日期 2022 年 9 月 5 日，共享协议 CC-BY 4.0）和 knewjade 的 66 行报告（见第二节，更新日期 2022 年 5 月 30 日）。
|
伪循环
图一：由 Atypical 公布的伪循环（pseudoloop）是 Hatetris 最初的高分思路。
(5 + 4 + 3 + 2 + 1) 个 S 竖排成阶梯，引出全 Z 横消，回归平地状态，循环。
图二三：伪循环加强版——左下角 6S 阶梯，右下角横 1S，接 I + S 反向滚动消一。
图四：伪循环最终版——在回归期间楼顶横 2S，最后滚动的 2S 软降消除，引出另一侧所需的 I。
在突破 30 行之前，Hatetris 的世界纪录都或多或少地使用了伪循环的思路。
2010 年 5 月 4 日，Deasuke 将加强版伪循环极限地执行了三遍，消出 30 行，纪录保持了 7 年。
至此，在不使用计算机辅助的前提下，人类玩家已经开始把思路转向“制造屋檐，扩大方块总落点数”。
AI + 通解形
2021 年，knewjade 大幅突破 Hatetris 的世界纪录，于 8 月 23 日达到 66 行。
相关说明见此处（日文），重点有四处：
一、以提高机械探索的基本性能为目标，重视计算速度，扩大可探索的局数。
二、安排三个落块评价值（洞[注 5]、完全封闭洞、消行数），展开集束搜索[注 6]。
三、专家指导 AI 寻找和前往如上左图所示的通解形。[注 7]
四、进一步专家指导：完全封闭大洞能用 S/Z 解封并填入的，不计封闭属性（顺应 Hatetris 的第三条出块原理）。
Knewjade 的这份 AI 思路说明正是 David & Felipe 后来获得成功的关键。
David & Felipe 的寻解思路
首先，要认识到 knewjade 的 66 行纪录的“思考过程”已经超出常人所能及的程度，再要突破，就必须也使用计算机辅助寻解。
选择软件/语言：不选内置大量机器学习功能的 Mathematica 和内置许多机器学习 API 的 Python，选对局速度明显更快[注 8]的 Rust。
模拟方法：机器学习赋能的蒙特卡洛树（MCT）搜索[注 9]——非专家指导模拟寻解（类似于 AlphaZero）。[注 10]
测试发现，用 MCT 寻 Hatetris 的解存在诸多不利因素[注 11]，越是迭代，模型越差，于是 David & Felipe 决定向启发法回归。
启发法的基本寻位思路是“穷举方块理论上可能到达的每一个位置，再排除掉会跟实格和墙壁重叠的那些位置”。
直接穷举效率太低，要合理精简位置数，更要有加速分析对局的方法，为此，David & Felipe 提出了以下四个方案：
一、缩小分析空域：方块锁定时不可能触及高出当前方块堆 4 行以上的位置，只需穷举偏下的位置。
二、明确摆法算式：设矢量 v 为方块起始位置，矩阵 M 为所有落点位置的集，则 n 步摆法集 = v * Mn。
三、GPU 矩阵计算：用 4 个矢量（代表上下左右）和 0/1 逻辑开关（方块被挡是 0，不被挡是 1）在 GPU 上快速计算。
四、二进制位浪：四连方块范围框对齐 10 × 4 时总位置数都是 34，可用 34 位二进制数表示。[注 12]
把这些 34 位的二进制数缓存起来，寻位计算就变成了“见数得集”的极速对照（平均每步 48 微秒）。
为了在 GPU 上实现这一点，相关代码用 CUDA C 写成。至此，快速分析对局的基础条件建立完毕。
有了速度，下一步就是追求质量——试改进 knewjade 的落块评价体系。
五个评价参数：x = 完全封闭洞数，y = 洞数，z = 完全封闭洞的行数[注 13]，w = 可消行方块种数[注 14]，v = 最低非死区高度。[注 15]
这个评价体系在好几处细节上顺应了 Hatetris 的游戏规则，已经很科学，再要改进，就要从它的盲区去思考：
一、可消除性：所谓消行，就是把行内的 10 个格子逐渐填满的过程。有些过程更容易继续发展出消行，有些过程则会停滞不前。
用福特-富尔克森方法[注 16]考察那些成功消除掉的行通常都经过了怎样的“填满过程”，就能推导出更易消行的摆法流。
二、可渗入性：只差一步就填满的行在关键余位被其他实格阻挡了外界通路，导致方块不能渗入目标位置，就不可消除。
“可消除性”仅仅是理论，要融合当前方块堆每一行的可渗入比率[注 17]，才能得到符合落块事实的计算结果。
Knewjade 的旧启发式考察宏观的地形特征，能形成大局观，不能细判出看似性质相同的两个洞通往消行的优劣情况；
David & Felipe 的新启发式考察消行的填满过程，不断地微观评价出相邻两行的消除力，和旧启发式形成了互补。[注 18]
改进完体系，剩下的就是参数优化（有一组好参数，就可能直接回报一个世界纪录）和执行 AI。
David & Felipe 使用的 Rust 库是 Simple(x)[注 19]，好处是参数之间的轻重关系可自然得出，坏处是需要集束搜索上百次。
| 参数
|
洞
|
完全封闭洞
|
完全封闭洞的行数
|
最低非死区高度
|
可消除性
|
图表启发式
|
执行消行
|
| 值
|
11.2106
|
83.7646
|
83.7646
|
-83.7646
|
每种方块 -83.7646
|
-2.1413
|
-332.2211
|
| 注：这组参数仅仅是 David & Felipe 在有限的硬件条件和计算预算下得到的最佳参数，绝非 Hatetris AI 的终点
|
David & Felipe 用这组参数得出了 86 行的世界纪录（发布时间 2022 年 5 月 29 日）。
注释和参考
- ↑ 也可使用自己编写的出块算法
- ↑ 使用 John Brzustowski 1992 年的论文“Can You Win At Tetris?”的算法二。
先连出 S，每当系统检测到特定的循环，就换成另一种方块。
- ↑ 算法来自 Heidi Burgiel 1997 年的论文“How To Lose At Tetris”。
这篇论文最著名的一点就是证明了 SZ 交替的俄罗斯方块游戏一定会在 7 万块之内玩输掉。
- ↑ 老版本则是蓝色
- ↑ 上方有实格的空格
- ↑ 集束搜索（Beam search）是一种启发式图搜索算法，它是在深度扩展最为复杂的前几步实行广度优先策略并只保留少数高评价值节点，从而降低问题的复杂度。
- ↑ 上左图是 7 种方块均可消行的基础形。Knewjade 专家指导下的 AI 常常会集束搜索出上右图所示的两侧通解形，恰好顺应 Hatetris 的第三条出块原理，得到大量的横 S/Z 消一。
- ↑ 实测结果：Rust 的对局速度是 Mathematica 的 123 倍
- ↑ 又称随机抽样或统计试验方法，是一种以概率和统计理论方法为基础的计算方法。
- ↑ 把每一块的摆法随机递归到底，得到许多的叶节点（leaf node），都用 Hatetris 这个游戏真实地模拟出来；在 MCT 中后向传播（Backpropogate）模拟结果实现权重调整，并用有向无环图（Directed Acyclic Graph）融合完全一致的场况为 MCT 剪枝。
- ↑ 样本只有不到十万局，模型训练周期长至数星期，长递归难以实现超参数（Hyperparameter）变异。
- ↑ O 是例外（只有 10 个位），可被 34 向下兼容
- ↑ 这种洞在 Hatetris 中很难挖掘，闭一洞两洞几乎一样差，将“有完全封闭洞的行数”作为参数已经足够合适了。
- ↑ 由 Hatetris 的第二条出块原理可知，如果有好几种不能消行的方块，它们的出块优先度一定会不同。反过来说，能消行的那几种方块是被 Hatetris 统一排除掉的，优先度就相同了，“可消行的方块种数”也就可以直接用作参数了，不需要再特别排序。
- ↑ Hatetris 的落块考察重点在于方块“所能及”的地表空域，更低的“死区”通常不可再利用，故不计入评价值。Knewjade 在此处考虑到了一种特殊情况：由于 Hatetris 的原序优先取 S/Z，完全封闭洞域能用 S/Z 解封并填入的，不算死区。
- ↑ 福特-富尔克森方法（Ford–Fulkerson method）是美国数学家 L. R. Ford Jr. 和 D. R. Fulkerson 于 1956 年发表的一种类似贪心算法的寻解方法。这种方法寻找增广路径的方式不完全确定，关键在于计算网络流的最大流，可用来考察俄罗斯方块的消行的填满过程。
- ↑ 例：2w 通路七种方块都能渗入，1w 通路只有 I 一种方块能渗入，完全封闭洞没有方块能渗入
- ↑ 这是一个图表理论系微观改进方法。当集束搜索宽度高达 2,500 万时，新启发式几乎起不到任何改良作用。
- ↑ 这是一个简化版（降低了计算复杂性的维度）的贝叶斯优化，能实现参数优化。
外链
