Tetris AI (Yiyuan Lee)

本条目介绍的内容不是官方算法。 该算法名称中的「Tetris」或「俄罗斯方块」仅表说明其用于俄罗斯方块游戏，不代表其来自俄罗斯方块著作权拥有者、或属于任何官方游戏。

Tetris AI 是一个 JavaScript 方块 AI。
这个 AI 呈专家指导风格，能在现代方块环境下稳定地无限消行，在 GitHub 上获得了较多的星数。
这个 AI 最终使用的专家参数结论来自遗传算法。
作者：Yiyuan Lee、Philip Blyth、Kyle Zhou、cmacmillan。

求值过程

1. 预设专家评分标准：总楼高 A、当前方块的消行数 B、洞数 C、总落差 D。
   记所求的四个参数的向量为 p，四个专家评分标准数据的向量为 x，则得分函数 f(x) = p · x = aA + bB + cC + dD。
   评分计算深度设为 2（只取一个预览块）。
2. 比较评分：对于当前方块，如果两个朝向落点评分之间存在 f(x₁) - f(x₂) > 0 的关系，就认为前者是更好的落块点。
3. 生成 p 的初始解：起始 p 数 = 1000，p 中的 abcd 的绝对值都取在 0~1 之间，符号分别为负正负负。
4. 适应度函数（Fitness function）：按各 p 值为落块做决策，一局最多玩 500 块，记 fitness(p) = 消行数。
5. 竞优：每次随机取 100 个 p 考察适应度并取前两名，不断重复，增加「优秀样本」。
6. 加权平均杂交：p' = p₁ · fitness(p₁) + p₂ · fitness(p₂)。
   两个父向量之间的适应度差异越大，后代向量的加权平均结果就越会偏向「更优秀的」那个父向量。
7. 变异算子：赋予所有后代 5% 的变异率，参数变动幅度为 ±0.2，结果做归一化处理。
8. 末位淘汰：每当后代向量总数到达 300，就把表现最差的 300 个 p 删除，留下 1000 个更优秀的 p。
   至这一步结束，遗传算法即可进入循环，可发展任意多次直到产出令人满意的结果。
9. 确定结论参数：a = -0.510066，b = 0.760666，c = -0.356630，d = -0.184483。
10. 总结另有价值的信息：专家标准也有优劣之分，比如「楼高峰值」不如「总楼高」；
    这套参数是 Tetris AI 在标准的现代方块环境下得到的，只要改变随机器等规则，结论就会不一样；
    在比较两个不同的 AI 的性能时，一定要注意所应用的方块环境配置是否不同。

方块环境配置

超级旋转系统 + 10×22 场地 + 标准入场位置 + 包随机器 + 1 预览。

参考资料

• Yiyuan Lee. Tetris AI – The (Near) Perfect Bot （英）. Code My Road. 2013年4月14日. [2022年6月19日].

外链

• Tetris AI 官方网站（在线演示，可游玩，可调整参数）
• GitHub 页面：Tetris AI