406. Conways Reverse Game of Life 2020 | conways-reverse-game-of-life-2020
首先，我要感谢我的队友 @knstqq、@maximim、@robertjohncannell（按字母顺序排列）提供的想法和付出的努力。能和你们一起工作真是太棒了！
在这次比赛中，我尝试了很多不同的方法。以下是效果最好的几种：
我查阅了 Kaggle 上现有的使用遗传算法的 Notebook，但发现没有一个使用了 GPU 加速（如果我错了，漏掉了哪一个，我很抱歉）。所以我实现了一个。
从头开始使用 PyTorch 实现这个遗传算法很难，但我在这个过程中学到了很多关于遗传算法的知识（初衷），也学到了 PyTorch 以及如何使用 NVIDIA Nsight 进行优化。
这个解决方案在比赛中表现非常好，仅靠下面的 Notebook 就进入了排行榜前十名。这种新方法帮助我们团队 "Under a Penny" 改进了最终解决方案。
GPU 上的遗传算法 Notebook：Top 10 with First Genetic Algorithm on GPU! 🔥（版本 1 运行 9 小时，得分 0.0450）
Kaggle 的康威生命游戏逆向挑战 2020 可以看作是一个布尔可满足性问题。我使用了 Kissat SAT 求解器，它在 SAT 竞赛 2020 的主赛道和不可满足实例中均获得了第一名。
棘手的部分可能是将问题转换为高效的 CNF 形式，但实际上使用 SymPy 做起来相当容易。
下面的 Notebook 在 25 分钟内解决了 9532 个谜题（delta=1）：Perfect Solve of Puzzles using a SAT solver
这种方法的缺点是，解决某些谜题可能需要很——长时间，而且 delta 越大，难度越高。
也可以将问题表述为约束问题。您可以在下文的“Notebooks 奖项尝试”部分找到使用 OR-tool 的迭代方法。
迭代方法包括用 delta = 1 解决谜题，然后再用 delta = 1 解决这个解，直到我们进行了 delta 次为止。这比端到端解决问题要快得多，但并不总能找到解。
本次比赛设有“Notebooks 奖项”：
得分最高的 Kaggle Notebook（由排行榜提交分数决定）。要获得此奖项资格，Notebook 必须在其内部完成全部计算。
我对此的解决方案是在 1 个 GPU + 1 个 CPU 上运行遗传算法（即使所有工作都在 GPU 上，PyTorch 也会 100% 使用一个 CPU），并在 1 个 CPU 上使用 OR-tool 运行迭代解决方案。
这种方法的缺点是：GPU Notebook 只有 2 小时和 2 个 CPU，而 CPU Notebook 有 9 小时和 4 个 CPU。
2 小时得分：0.05353 GA on GPU + OR-tools on CPU2
9 小时得分：0.0433（由于代码限制无法提交）
解决方案的集成非常简单。我们计算为谜题找到的每个解决方案的分数，然后取分数最低的解决方案。
与 @knstqq、@maximim、@robertjohncannell 组队是一次很棒的经历，大家都保持了团队的积极性，而且他们对这个问题的解决方案真的很棒。最后，合并在一起确实是获得这个名次的秘诀。
队名来源于团队只有 @maximim 和我的时候。我们的目标是分数低于 .01，我们称之为 "a penny"（一分钱）。