世界上有一款俄罗斯游戏的变体，叫做 [Hatetris](https://qntm.org/files/hatetris/hatetris.html) （“可恶的俄罗斯方块”，亲自去玩一下就知道这个版本的俄罗斯方块有多么令人抓狂，我最多消了三行。。），号称世界上最难的俄罗斯游戏，是由程序员和科幻作家Sam Hughes于 2010 年编写的俄罗斯方块版本。曾经的世界纪录也只能做到消去32行（32分），然后在去年被一个日本选手 knowjade 推到了66 分。 现在这个分数已经被(痴迷于一个问题并付诸实践且刚学了几天 Rust）的两个开发者给推到了 86 分高分。
该团队最初选择了三门语言来实现：Mathematica、python 和 Rust。
Mathematica 平均每场比赛耗时 4.3 秒，Rust 平均每场比赛耗时 0.035 秒。这是一个如此大的差异，所以该团队认为与 Rust 的借用检查器进行谈判的所有麻烦和斗争都是值得的。
他们尝试的实现：
- MCTS（蒙特卡洛树搜索）是游戏模拟中的一条行之有效的路径。核心理念是将游戏中的每一步都变成树状结构，然后探索树。然后他们从树搜索重构为 DAG 搜索，产生了可喜的结果。（MCTS 中的“Graph vs Tree”实际上是这个专业圈子里有争议的，并有相关论文）
- 他们尝试 rust + pytorch-c绑定制作了AlphaHATETRIS，但是失败了
- 实现了一个模拟器，然后受 knowjade 写的相关文章启发，使用了
heuristic beam search （启发式光束搜索，https://gist.github.com/knewjade/586c9d82bd53f13afa8bcb7a65f8bd5a），但是他们得到的分数是 53 分，而不是 knowjade 的66分。- 从图论中得到启发，结合
heuristic beam search ，经过优化参数， 奢侈地使用了 aws 上的一个实例，然后花了56 个小时得到了 86分。一共花费140美元。收获的教训：
- 学会了使用火焰图分析程序性能：字符串格式化代码占用总运行时间 17% ； 避免循环嵌套；使用
clone() 解决借用问题，但并没有花费什么时间成本，因为编译器将它们优化掉了。- 切换数据结构。他们需要一个读取速度和插入速度都比较平衡的数据结构，所以从 Vec（读O(1)， 写O(n)） 换成了 BTreeSet （读写都是O(log(n))）。
- 再多的优化代码都不会消除对机器学习硬件的荒谬需求。不管你的模拟器有多好，你玩游戏的速度有多快……大量的训练数据和所需的训练时间使得尝试解决消费硬件上的复杂问题变得非常具有挑战性。
这篇文章涉及很多算法细节，感兴趣的可以点击原文阅读
https://hallofdreams.org/posts/hatetris/