浅树，茂密的落叶

Stockfish搜索更多职位（每秒1亿个职位），并使用计算便宜的启发式方法对其进行评估。树搜索方法是对alpha-beta修剪的改进。

DeepMind的AlphaZero的后代Leela Chess Zero通过使用深度卷积神经网络（经过数百万次自玩游戏训练）来评估位置，从而搜索的位置少得多（每秒4万个）。它具有不同的搜索方法，即蒙特卡罗树搜索。

Leela Chess Zero所采用的神经网络本身令人着迷，它使用的结构类似于SE-ResNet图像分类模型。残留的挤压和激励层塔分别进入“价值”和“政策”部门，以评估职位并决定下一步要做的事情。

但是，我想更多地讨论寻找更少职位并在每个职位上投入更多精力的一般策略。尤其要指出的是，Stockfish和Leela Chess Zero之间的主要区别体现在Conway的《生命游戏》和相关的细胞自动机中许多用于查找飞船的搜索程序中的两个：

程序ntzfind最初由匿名作者'zdr'编写，并由Matthias Merzenich，Aidan Pierce和Tom Rokicki进行了增强，它是深度优先的树搜索，它使用巨大的内存查找表来查找下一个的所有可能选择。排基于前几行。

新程序ikpx2是我为查找第一个基本骑士而编写的程序的改编版，它与Leela Chess Zero比较相似，因为它的搜索树小得多，但在每个节点上完成的工作量却大得多。

特别是，ikpx2使用SAT解算器进行深度前瞻，以确定当前的部分宇宙飞船是否可以完全扩展多几行，因此不接近“死胡同”。相比之下，ntzfind只能通过执行整个子树的深度优先遍历来排除部分视图。

使用的SAT解算器是Armin Biere的kissat和CaDiCaL。 Kissat比CaDiCaL更优化，但尚不支持增量求解。这样，ikpx2尝试学习（使用基本强化学习，特别是多臂土匪模型）哪种SAT求解器更适合于给定任务。从理论上讲，我们可以添加其他最新的SAT解算器（例如Mate Soos的cryptominisat），并使用功能更强大的强化学习模型（例如神经网络）来评估子问题并确定要使用哪个解算器。

拥有这棵“浅叶重树”意味着当前的搜索进度可以轻松地完全放入内存中。而且，并行性很容易：我们保留了一个优先级的任务队列（部分太空飞船），并且有许多CPU线程可以执行以下操作：

发送回主编排线程的结果是已扩展的部分内容（对于30行左右）。这些行的一小部分初始段作为节点添加到内存树中；其余的行则不然，否则我们将得到ntzfind使用的完全未修剪的搜索树，因此我们的优势被彻底消灭。

其余的行会怎样？不仅仅是丢弃它们，我们还可以提取整个扩展部分，并在细胞自动机中对其进行仿真！有时，这些碎片会演变成主要搜索无法找到的物体：例如，尾巴的周期可能比宇宙飞船的其余部分要长，或者留下一堆碎片。这个想法似乎最早是由Paul Tooke于2001年进行探索的，然后在20年后的ikpx2中被重新发现。

保罗·图克（Paul Tooke）的想法是早期的ikpx2新搜索结果之一，就是这种局部搜索结果，它演变成一个528周期的河豚引擎：

同样，这是约翰·温斯顿·加思（John Winston Garth）发现的新颖的21期太空飞船。他跑ikpx2寻找2c / 7太空飞船；在12个CPU线程上运行的三天内，它既重新发现了David Eppstein的周末旅行者，又发现了一个全新的21期附件，紧贴其尾巴：

然后，用户“ iNoMed”发现其中两个可以相互作用以产生废气，该废气可以被附近的周末度假者扰乱，每42代发射一次向前移动的滑翔机：

ikpx2的另一个功能是它能够找到具有不同对称性的不同组成部分的对象。例如，这里是一个头部对称，胸部不对称，腹部对称的宇宙飞船。尾部是高周期的，也是由模拟部分而不是直接SAT求解引起的：

令人失望的是，ikpx2未能在标准“生命”规则中找到任何新的宇宙飞船速度。我在与查找罗宾爵士的原始ikpx相同的输入上对其进行了测试； ikpx2能够以大约50倍的速度（以经过的核心时间为单位）找到相同的结果。

最近发生了一次未命中的事故，如果不是第7代中诞生的一个额外电池，那将是（2,1）c / 7宇宙飞船（左侧配置，带有或不带有所示绿色三元组，会导致带有令人沮丧的红色四重奏的正确配置）：

像这样的近失踪事件的存在使我充满希望，如果有更多的时间，它将最终找到（2,1）c / 7宇宙飞船。

与ikpx的原始版本不同，此版本能够搜索大量相关的细胞自动机。特别是，它从元胞自动机规则（被视为9输入1输出布尔函数）中提取素数蕴涵集，并使用它来将规则的机制编码为SAT问题。

特别是，两次ikpx2调用足以在Day＆amp; Night规则中找到以下不断增长的骑士团：一次调用以找到延伸一条粗斜线的快速（2,1）c / 5前端，另一次调用以找到一条斜线。较慢的（2,1）c / 6尾部消耗了它：

这是柠檬41625发现的非标准规则中的11c / 22宇宙飞船，这是对称切换的更好示例。该发现包括具有高周期排气的奇对称，不对称和偶对称组件：

ikpx2的源代码是开源的（根据MIT许可证发行），因此您可以自己进行试验。 目前，它是x86_64专用的，因为它具有apgsearch作为依赖项（以便快速模拟部分并检查它们是否演变成任何有趣的东西）。