Tetris (a3nm)
来自俄罗斯方块中文维基
|
本条目介绍的游戏不是官方游戏。 该游戏虽然在名称中使用了「Tetris」或「俄罗斯方块」，但实际上没有俄罗斯方块著作权拥有者的授权。 |
| Tetris game | |
|---|---|
 游戏画面 | |
| 游戏信息 | |
| 开发 | a3nm |
| 游戏平台 | JavaScript |
| 发行时间 | 2022年4月19日 |
| 游戏机制 | |
| 场地大小 | 10×15 |
| 预览数量 | 0 （由玩家决定） |
| 降落 | 有 |
| 暂存 | 无 |
| 旋转系统 | 电脑选择朝向硬降 |
Tetris 是一个四连方块网页游戏。
该游戏转换了方块游戏的交互角色，人决定方块，电脑控制方块。
该游戏用穷举法证明了「纯硬降落块 6 行之内必能消行」，向敌对方块课题增添了一项结论成果。
游戏概况
人和电脑用四连方块下棋，人要尽量阻止电脑消行，可以悔棋。
人决定每一手的方块，电脑决定方块的朝向和硬降落点。
能使电脑 5 行之内消不出行，就算人赢。
证明过程
- 建立博弈背景：使用 10×20 的标准方块场地和七种四连方块，人决定块序，电脑决定朝向和落点。从数学上说，这是一个完美信息零和序列博弈。
- 提出原始关键命题对：存在一个策略能保证无论块序如何都能成功消行；存在一个块序能保证无论落点顺序如何都不能成功消行。这两个命题必是一真一假，现要证明哪个是真、哪个是假。
- 降低问题的复杂度：方块游戏存在复杂的软降和特殊旋转，难以一一判断。但是，如果所有块序连纯硬降都不能阻止消行，那么加入了软降和旋转只会使局面变得更加不能阻止消行。问题转化为：试证明「所有块序纯硬降都不能阻止消行」。
- 选择证明方法：序列博弈可通过穷举所有序列完成证明，只要能把所需穷举的状况总数合理降低到一个来得及遍历的程度，穷举法就能完成证明。问题转化为：试穷举「消行前可能存在的一切场地状况」。
- 寻找优化策略（前）：先用极小化极大算法（Minimax）排除死格[注 1]和已知的必胜局面。首先，可从硬降的定义判断，如果一个空格上方已经有另一个砖格，这个空格就绝对无法被硬降填补，其对应的行也绝对无法立刻消除（「死行」），所以真正要考虑的场地状况由各列的高度和「死行」的集合组成；其次，相同的场地状况可通过博弈树中的许多不同路径到达，如果已经穷举过某个节点之后的所有情况且结论全部相同，这个节点就可被记忆化（Memoization）[注 2]，未来的状态探索只要发展到这个节点，就能立刻得出结论。
- 寻找优化策略（后）：总状况数可用 Alpha-beta 剪枝继续缩减，每次触发记忆化节点时，就只按探索深度考虑其他落块方案从而寻得更短的策略路径。至这一步结束时，电脑获胜的全部 900 万个场地状况已经穷举完毕（证明已经成功），但仍有继续精简的方案，其关键在于移除「不可到达的场地状况」，这一步将状况总数缩减至了 21000。最后，作者通过合并策略相同的场地状态将状况总数进一步缩减至 5250。这个数值已经足够小，所以作者决定不再通过排除诸如「镜像场地」或「等高异列」再做优化或是启用「迭代深化」（重视低位落块或尽量阻止死行）之类的其他策略做重复证明。
- 检查策略：做出策略算法和对应的游戏状态数据文件描述出一个有边标号（Edge labeling）的有向无环图（Directed acyclic graph），进而做出游戏程序[注 3]接受检验。
- 结论：（在 10×20 的标准方块场地内使用七种四连方块）纯硬降落块 6 行之内必能消行，原始命题「存在一个策略能保证无论块序如何都能成功消行」为真。
- 未解决问题展望：如果加入软降和旋转情况，电脑的最低获胜高度是第几行；换作是宽两列以上的偶数列场地，结论又如何；落块一方是否有实现消二的必胜策略；假设场地足够高，那么是否存在可以消出任意总行数的策略（保证不会死局，无论什么块序都无法阻止持续性的、通往永久的消行）。
注释
参考资料
- a3nm. Can you be sure to clear a line at Tetris? （英）. a3nm's blog. 2022年4月19日. [2022年6月13日].
外链
- 游戏的 官方网站
