我们的第10名解决方案 [含代码]

恭喜大家，比赛终于结束了！比赛刚结束，我想稍微介绍一下我们团队“Puzzlemaster”获得第10名的解决方案。

我们的解决方案是由3个部分组成的集成方案，这3个部分分别解决了3组任务，且存在部分交集：

• 由 @felipefonte99 实现的 DSL 算法
• 由 @nikitaovsov 实现的 ML（机器学习）算法。我想他们会在这个帖子中发布关于他们解决方案的其他帖子或评论。
• 由我和 @artyomp 创建的遗传算法，该算法试图拟合一个 DSL 程序。它解决了10-12个任务。现在我将讲述这部分内容。

首先，我想感谢这些 Kernel（代码内核）的作者，他们从算法角度给了我很多启发：

• Cellular Automata as a language for reasoning
• DSL and Genetic Algorithm applied to ARC

当然还有我打开了1000次的那个 Kernel：

• Visualizing all task pairs with gridlines

解决方案

我们创建了一种领域特定语言（DSL），基于可以应用于网格的命令。我们的语言中有许多命令。每个命令都有几个在训练期间随机采样的参数。我们称之为“全局规则”（与下文描述的元胞自动机规则相对）。

命令示例：

• 从（某种颜色的）单元格开始画一条线（或某种颜色）（直到在某种颜色处停止）。
• 将（某种颜色）的所有单元格映射为（某种颜色）。
• 旋转网格。
• 对（某种颜色）的（图形/单元格）施加重力，方向朝向（（某边界）/某颜色）。
• 其他...

所有括号中写的都是随机采样的参数。

在比赛结束时，我们在 DSL 中添加了“多网格”元素。例如，它可以拆分网格（例如通过上面的图形），对某些网格应用一些命令，然后将它们合并回来。这大大提升了我们的 LB 分数。

还有在先前命令之后应用的“元胞自动机（Cellular automata）”命令。关于元胞自动机的更多细节可以在这个 Kernel 中找到：Cellular Automata as a language for reasoning

我们的 DSL 包含几个随机参数化的 CA 规则。例如，检查直接邻居，检查有色角等。

因此，最终的 DSL 程序是一系列“全局”规则，然后对其结果应用 CA 规则。

C++ 部分

我们解决方案中非常重要的一部分是 @artyomp 使用 C++ 实现的“全局”规则和“CA 规则”。他做得非常棒，将整个算法加速了100倍，使我们能够创建许多新规则，而不必太在意搜索空间的复杂性。如果没有 C++，我们可能只能解决我们所解决的一半测试任务。

搜索算法

实际上，它类似于 DSL and Genetic Algorithm applied to ARC 中的算法，但有许多启发式方法。我们的算法创建随机的程序序列，创建无性突变（尝试用新命令替换命令、插入新命令、删除命令）和“有性”突变（尝试连接2个程序的随机前缀和后缀，并在最后进行一些突变）。

质量度量

如何衡量程序是否优秀？显然，我们应该衡量准确率（有多少单元格是正确的）。如果所有训练对的准确率等于1，我们就找到了解决方案。但是由于我们使用带有1个规则突变的遗传算法来寻找解决方案，我们可能需要更多的指标来允许种群更大。我的观察是我们应该小心，因为如果我们添加更多指标，算法更有可能创建一个包含许多命令的垃圾程序，它虽然能解决训练样本但过拟合了。

所以结果是我们最终选择的指标：

• 所有训练输出的平均准确率
• 每个输出的准确率
• 以下二进制指标的平均值：对于从0到10的每种颜色，我们计算我们的颜色预测是否绝对正确（在精确率和召回率方面）。这有助于算法找到正确序列，从而逐个正确拟合颜色