Deeper Systems 团队方案分享

首先，我想祝贺每一位参赛者，特别感谢“Under a penny”团队在最后阶段带来的激烈竞争 :)

很多因素促成了我们最终的胜利。这是良好的流程、团队合作以及最后时刻的即兴发挥共同作用的结果。

流程

我们的方法本质上是在当时尝试尽可能多的方法，并将我们的算力集中在最有希望的方法上。

其中一个关键组件是我们建立的一个小型 Web 服务，我们的脚本可以请求尝试一个随机个体，然后报告成功或失败，以及算法名称和处理时间。然后我们有一个小型网页，列出各种算法及其每小时分数提升方面的性能。这有几个优点：

• 我们可以追踪每种算法的表现
• 我们可以轻松插入新算法，而无需在每次单独尝试时重新编写计时和性能统计代码
• 它让我们能够将最新的更改快速分发到我们拥有的任何可用核心上

这也帮助我现在撰写这篇文章，因为它有助于记住我们尝试过的所有内容 :)。在我现在查看的页面上有 155 行，在服务运行之前我们还尝试了一些其他东西。

方法

用技术术语来说，我们尝试了“一大堆东西”。我们发现某些方法在开始时效果很好，但随着它们解决了“较容易”版本的问题或达到方法的极限，收益会递减。因此，我们不断添加新方法，并根据其持续表现重新平衡我们的算力。这些大致按时间顺序列出。

模拟退火算法

这是标准的模拟退火算法，用 C++ 实现。它运行速度超快，并在开始时获得了巨大的改进。我们的做法是，每次“运行”在一个样本上尝试几千个 epoch，然后报告改进（如果有），并获取一个新样本进行尝试。

遗传算法

我们最终对遗传算法进行了三次单独的实现。第一个 C++ 版本没有获得太多改进。我们本打算放弃这个方法，但看到 Desareca 的成功 后受到鼓舞，用 Python 实现了另一个。这在早期获得了快速改进，但很快开始放缓。作为最后的优化，我们将代码直接从 Python 翻译成 C++，该方法获得了约 50 倍的提升。我们让这个程序运行了一段时间。

模板匹配

我们尝试生成所有可能的 3x3、4x4 和 5x5 配置，运行 1、2、3、4、5 步，缓存结果，然后将这些“粘贴”到精确的部分匹配中。这有点繁琐，效果也不是很好。我们希望能粘贴多个这样的模板并获得良好的部分分数，但事实证明问题演变得太混乱，无法像这样分割。我们放弃了它，转而采用其他方法。

Z3 求解器

然后我们了解了 SAT 求解器，这要感谢 James McGuigan 的 优秀笔记本。这对我们来说是一个新工具。在这里，我们通过实验试图找出什么能带来最大的改进：先尝试“最简单”的问题，还是尝试我们在其他方法中“误差最大”的问题。我们很快发现，停止棋盘上的像素越少，求解器就越容易解决，因此我们优先运行这些。

Picosat 求解器

在 Z3 求解器之后，感谢 Serhii Hrynko 的笔记本，我们发现了 Picosat。与其他报告中读到的相反，我们发现 Picosat 比 Z3 快得多。

我们尝试了两种方法：做一个一体化解决方案（即给定停止棋盘找到 3 步前的棋盘），或者尝试迭代方法，先回退一步，然后再回退一步，等等。我们发现迭代方法有效得多。关键在于添加额外的约束，以最小化求解器在棋盘上找到的像素数量。像素越少意味着更有可能找到一个拥有自己父代的父代，而且求解器解决起来也更快。我们实现了一个搜索算法，使用二分查找来找到要添加的死亡单元格约束的数量，然后它会获取这些约束的一个随机子集并产生解决方案。如果解决方案失败，它会放宽约束（要求更少的死亡像素），如果搜索在没有约束的情况下失败，我们会回退一级。

对求解器设置超时非常有效。起初我们给了它们 1 分钟的超时，并在一分钟内解决了所有能解决的问题。然后我们扩展到 10 分钟，然后是一小时，最后到结束时，我们在中止前给它们设置了 2 小时的超时。超时的作用本质上是重新开始搜索一个不同的第一步回退棋盘。从观察中我们发现，求解器会陷入一个绝望的分支，要么是一个最终没有解的分支，要么是一个可能有解但尝试每一步的计算量太大以至于永远运行下去的分支。

部分求解器

求解器运行得越多，我们发现的收益递减就越大。我们进行了大量实验，最终发现了一种有帮助的方法，即将停止棋盘的边缘归零，并让求解器部分解决这个问题。这会生成一个起始棋盘，其解决方案的中心部分完全正确，然后我们的