译者：AI研习社（季一帆）
双语原文链接：https://www.yanxishe.com/TextTranslation/2719
前瞻
我花了近一年的时间写《动手深度强化学习》一书，距离该书出版已经过去半年了，在这段休整时间，我发现自己对强化学习的热情已经无法退却。无论是研究不同的RL方法，或是复现论文代码，对我而言是极大的乐趣。幸运的是，RL在各个领域均在迅速发展，很多有趣的主题值得探讨。
引言
多数人对深度强化学习的认识主要集中在应用DRL进行游戏，这并不意外，因为Deep Mind在2015年首次应用DRL进行Atari系列游戏，并大获成功。
事实证明，Atari系列套件与RL的结合简直是天作之合，即使是现在，许多研究论文仍使用该套件来验证自己的方法。随着RL的发展，经典的53种Atari游戏的挑战性越来越小（在撰写本文时，RL在一半以上的游戏表现超过人类），所以，现在的一些研究转向更复杂的游戏，例如StarCraft和Dota2。
由于上述原因，会给人一种错觉，即“ RL是用来玩游戏的”，事实显然不是这样。在我2018年6月出版的书中，我不仅介绍了RL在Atari游戏的应用，也介绍了其他领域的不同示例，包括股票交易（第8章），聊天机器人和NLP（第12章），自动驾驶（第13章），持续控制（第14-16章） ）和棋盘游戏（第18章）。
实际上，基于MDP的RL可以用于各种不同的领域，计算机游戏只是关于复杂决策的一个简易且关注度高的领域。
在本文中，我将详细介绍将RL应用于组合优化领域的最新研究工作。本文对UCI（加利福尼亚大学欧文分校）的研究人员发表的论文“Solving the Rubik’s Cube Without Human Knowledge”进行解读。除了论文解读之外，我还使用PyTorch复现了论文，通过训练模型和流程解读实验，并对论文方法进行改进。
下文我将结合代码对论文的方法进行介绍，以加深对相关概念的理解。如果你只对理论方法感兴趣，可以跳过代码部分。
OK，现在开始吧！
Rubik魔方和组合优化问题
我估计每个人都知道魔方是什么，所以我就不做过多魔方介绍了，而是将这部分的重点放在它与数学和计算机科学的联系。如非特殊说明，本文中的“立方体”是指3x3经典魔方。除了3x3经典魔方，还有其他一些变体魔方，但3x3经典魔方至今仍是最受欢迎的。
虽然看起来Rubik的3x3模型似乎非常简单，但考虑到各种可能的旋转转换，这其实非常棘手。据计算，3x3经典魔方旋转状态总共有4.33 × 10¹⁹种不同状态。如果考虑一些魔方拼接出错的情况，即模仿无法通过旋转复原，只有拆解重新进行合理的拼接，那么总状态增加约12倍（≈5.19×10²⁰）。
所有状态都可以通过各种旋转组合得到。例如，在某种状态下顺时针旋转魔方左侧，就会达到一种新的状态，从该状态逆时针旋转同一侧就会回到原始状态。另外，如果连续三次旋转魔方左侧，则回到原始状态的最短路径是再将魔方左侧顺时针旋转一次，而不是逆时针旋转三次（虽然这样也可以，但却不是最佳的） 。
由于3x3魔方有6个面，并每个面可以沿两个方向旋转，因此总共有12种旋转方式。当然，直接旋转半圈（在同一方向上连续两次旋转）也是可以的，但为简单起见，我们将其视为两次旋转。
数学中，有一些领域专门研究这样的对象，最典型的便是抽象代数。抽象代数是数学研究的一个重要方向，也是现代计算机理论基础之一，主要研究抽象对象集及其代数操作。根据抽象代数，Rubik魔方是一个非常复杂的‘群’，有许多有趣的属性。
但是魔方不只是简单的状态和变换，它还是不确定的，其主要目标是找到一个可以复原魔方的旋转序列。这样的问题可以通过组合优化进行研究，组合优化也是应用数学和理论计算机科学的一个典型子领域。该领域包含许多有价值的典型问题，例如：
还有其他一些类似的问题。这些问题的共同之处在于状态空间特别大，从而导致通过遍历所有可能组合以找到最佳解决方案是不可行的。Rubik魔方也属于这类问题，该问题状态空间为4.33×10¹⁹，想要通过蛮力求解几乎不可能。
最优化与‘上帝之数’
使组合优化问题变得棘手的原因是，尽管我们非常清楚该怎样达到问题的目标状态，但实际上我们并没有很好的解决方案。魔方问题尤其如此：在发明魔方之后，就确定了通过12种旋转可以达到目标状态，但Ernő Rubik花了大约一个月的时间才找到一种复原方法。如今，有了许多不同的魔方复原方法，包括入门方法、Jessica Fridrich方法和许多其他方法。
所有这些方法差异巨大。例如，入门方法需要记住5-7种旋转序列旋转大约100次才能还原魔方。与之形成对比的是，当前三阶魔方还原的世界纪录是4.22秒，这需要更少的步骤，但也要求挑战者需要记忆和训练大量的旋转序列。Jessica Fridrich方法平均约需55个动作，但需要熟悉大约120个动作序列。
但是，最大的问题是：给定任意状态的三阶魔方，其还原最短动作序列是什么？十分遗憾，尽管三阶魔方已经有54年的历史了，这个问题依然没有答案。只有在2010年，Google的研究小组证明，解决任何魔方状态所需的最小移动量为20，该数字也称为‘上帝之数’。当然，这只是一个平均数字，最佳解决方案可能要短一些，也就是说，复原很多魔方平均需要20步移动，但某个状态可能不需要任何移动（已复原状态）。
但是，上述研究仅证明了最少平均移动量，却没有找到实际的解决方案。如何找到任何给定状态的最优解仍然是一个悬而未决的问题。
魔方复原的方法
在该论文之前，魔方复原问题主要有两个研究方向：
使用群论方法，显着减小要搜索的状态空间。这种方法种最典型的包括Kociemba算法；
使用蛮力搜索以及人工定义的启发式搜索，使搜索指向最有可能的方向。典型的如Korth算法，该算法使用A *搜索和大型模式数据库避免选择错误的方向。
本文介绍了第三种方法：通过在海量不同状态的魔方数据集上训练神经网络，获得求解状态方向的策略。该训练不需要提供任何先验知识，仅需要魔方数据集（不是物理魔方，而是计算机模型）。这是其与上述两种方法的最大不同：前两种方法需要大量的领域知识，并以计算机编码进行定义。
后续章节是新的论文方法的详细介绍。
数据表示
我们从数据表示开始介绍。在三阶魔方问题中，我们首先对动作和状态以某种方式进行编码。
动作
此处的动作是指魔方在任何状态下可能的旋转，前文已经说过，我们总共只有12个动作。对于3阶魔方，共有左，右，上，下，前和后六个侧面可以旋转。而对每一面，有两种不同的操作，即该侧的顺时针和逆时针旋转（90°或–90°）。一个很小但非常重要的细节是，当需要旋转的面朝向你时，你能方便的进行操作。例如，你可以哦容易的旋转正面，但对于背面而言，总是有些不太习惯。
根据上述说明，动作名称可以根部不同侧面的首字母做出以下定义。如右侧的顺时针旋转命名为R；至于逆时针的动作，可能会使用不同的符号，包括R'/r/r̃。第一种和最后一种表示法对于计算机代码而言不太友好，因此我使用了小写字母来表示动作的逆时针旋转。这样，右侧面的两个动作是R和r，左侧面的两个动作为L和l，依此类推。
在我的代码中，动作空间是通过python枚举实现的，其中每个动作映射为唯一的整数。
状态
状态是指三阶魔方当前的排列组合方式，正如前文介绍的，该状态空间极其庞大（4.33×10¹⁹个不同状态）。但除了要面对海量的状态，我们在选择特定的状态表示形式时，还要考虑到以下这些要求：
避免冗余：在极端情况下，我们可以通过记录每侧每个贴纸的颜色来表示魔方的状态。但是，如果你计算一下这些组合的数量，会发现它等于6⁶*⁸=6⁴⁸≈2.25×10³⁷，远远大于三阶魔方的状态空间大小，这意味着这种表示形式是高度冗余的，例如，魔方两侧中心对称的情况。至于为什么得到6⁶*⁸，很简单：三阶魔方有6个面，每个面除了中心块外有8个小立方体，所以总共有48个贴面，每个贴面可用6种颜色之一上色。
内存效率：在后续的训练和模型应用过程中，我们需要将大量魔方集的不同状态保存在内存中，这可能会影响流程效率。因此，我们希望表示形式尽可能紧凑。
转换性能：另一方面，我们需要对某一状态进行所有可能的旋转操作，并且要求这些操作快速完成。如果在内存中的状态表示非常紧凑（例如使用位编码），这会导致魔方侧面的每一次旋转需要进行冗长的解压缩过程，严重影响训练速度。
适宜的神经网络：就像其他机器学习、深度学习实例中那样，并非每个数据表示都符合神经网络的输入格式。在NLP中通常使用字符或单词嵌入，在CV中将图像从jpeg解码为原始像素，Random Forests则需要对数据进行大量特征设计等。
在本文中，使用独热编码将三阶魔方的每个状态表示为20×24张量。接下来以下图为例，对这种表示方式进行说明。
将魔方中需要关注的面标为白色
上图中，我们用白色标记了我们需要关注的魔方模块，其余部分（蓝色）是冗余的，不需过多关注。我们都知道，3x3魔方由三种类型的模块组成：8个三色的角块，12个两色的侧边块和6个单色的中心块。
虽然不太明显，但实际上根本不需要过多关注中心块，因为它们不能更改其相对位置，只能整体旋转。因此，对于中心块，我们只需就其位置达成一致就可以。例如，在我的实现中，白色面总是在顶部，前面是红色，左边是绿色，依此类推。这使得数据集状态的部分固定，意味着将魔方上所有可能的旋转被视为同一状态。
由于无需关注中心块，所以在上图中所有中心块都是蓝色。那其余蓝色是怎么回事呢？这是因为每种特殊的立方模块（角块或侧变块）的颜色组合都是固定的。例如，根据上述对魔方前后左右各方向的定义（顶部为白色，红色为正面等等），左上角块一定是绿色、白色和红色，其他立体块不会有这三种颜色的组合。 侧边块也是如此。
因此，要找到某个特定模块的位置，我们只需要知道其某个面的位置即可。一般来说，你可以在侧边块或角块选择一个面进行跟踪关注，但是一旦选定，就要坚持下去。如上图所示，我们选择在顶部跟踪八个立方块贴面，从底部跟踪八个贴面，以及四个侧边块贴面，两个在正面，两个在背面。这样，我们需要跟踪关注的总计有20个贴面。
那么，张量维度中的“ 24”是从哪里来的？我们总共要跟踪20种不同的贴面，但是由于魔方旋转，它们可能出现在不同的位置，至于具体位置，这取决于要跟踪的立体块的类型。以角块开始说明，我们总共有8个角块，旋转魔方可以按任何顺序对它们进行重新排列。因此，任何一个角块都可能出现在8个角中的任何一个位置。此外，每个角块也可以旋转，例如，这会使“绿色、白色、红色”对应的角块有以下三种可能的方向：
白色在顶部，绿色在左面，红色在前面；
绿色在顶部，红色在左面，白色在前面；
红色在顶部，白色在左面，绿色在前面；
因此，为精确表示角块的位置和方向，我们得到8×3=24种不同的组合。
至于12个侧面块，由于它们只有两个贴面，因此只能有两个方向。也得到24种组合，只不过是通过12×2=24计算得到的。最后，我们要跟踪20个立方块，8个角块和12个侧边块，每个立方块有24个可能的位置。
独热编码是指当前对象的位置为1且其他位置为0，该编码可以输入神经网络进行处理。因此，本文中状态的最终表示形式为20×24的张量。
考虑到冗余情况，这种表示方式非常接近总状态空间，其可能的组合数量为24²⁰≈4.02×10²⁷。虽然它仍远大于魔方的状态空间，但是这种方式要比比对每个贴面的所有颜色进行编码要好得多。冗余得原因是魔方旋转自身得属性，如不可能只旋转一个角块或是一个侧边块，每次旋转总是会转一个面。
好了，数学知识就介绍这么多，如果你想了解更多，推荐Alexander Frey和David Singmaster撰写的著作“Handbook of Cubic Math”。
细心的读者可能会注意到，这样的魔方状态的张量表示有一个重大缺点：内存效率低下。实际上，如果将状态表示为20×24的浮点张量，我们浪费了4×20×24=1920字节的内存，考虑到在训练过程中需要表示数千种状态，这会导致数百万字节内存的损耗。为了克服这个问题，在本文的实现中，我使用两种表示形式：一种是张量，用做神经网络输入；另一种是更紧凑的表示形式，以便更长久地存储不同的状态。我们将这种紧凑状态保存为一系列列表，根据角块和侧边面的排列及其方向进行编码。这种表示方式不仅具有更高的内存效率（160字节），而且使魔方的转换也更加方便。
更多细节参见该模块，紧凑状态见函数namedtuple，神经网络张量表示见函数encode_inplace。
训练过程
现在我们已经知道了三阶魔方的状态是如何以20×24张量编码的，下面我会介绍本文使用的神经网络结构及其训练方法。
神经网络结构
下图是神经网络结构（取自原论文）：
该神经网络将魔方状态的20×24张量表示作为输入，并产生两个输出：
策略。由12个数字组成，表示行动的概率分布；
值。使用一个标量表示对状态的评估，具体含义见下文。
在输入和输出之间，神经网络由若干ELU激活函数的全连接层。在我的代码实现中，网络结构与此处并无差异，详见此处。
训练
可以看到，网络非常简单：策略告诉我们对当前状态进行何种转换，值用于评价状态的好坏程度。那么，最大的问题就是：如何训练网络？
论文提出的训练方法是“ Auto-Didactic Iterations”（简称“ ADI”），该方法也简洁明了。从目标状态（复原的魔方）开始，执行一些预定义的长度为N的随机变换序列（文中给出了N个状态的序列）。对序列中的每个状态，一次执行以下过程：
将所有可能的变换（总共12个）应用于状态s；
将这12个状态传递给当前的神经网络，以输出值。这样就得到s的12个子状态的值；
根据vᵢ = maxₐ(v(sᵢ,a)+R(A(sᵢ,a)))计算状态的目标值，其中A(s, a)是对s执行动作a之后的新状态；如果s是目标状态，则R(s)为1，否则为0；
状态s的目标策略使用相同的公式进行计算，不同的是我们选择最大值，即pᵢ = argmaxₐ (v(sᵢ,a)+R(A(sᵢ,a)))。这仅意味着目标策略只有在最大值的子状态时取值为1，否则为0。
具体过程见下图。生成序列为x₀，x₁…，以魔方xᵢ为例进行详细说明，对状态xᵢ，通过上述公式确定策略和值目标。
通过该过程，我们可以生成任意数量的训练数据。
模型应用
假设我们已经通过上述过程训练得到模型，那么如何使用模型来复原魔方呢？根据网络结构，我们很容易想到这样的方法（但不幸的是该方法并不可行）：
向模型提供要解决的三阶魔方的当前状态；
根据策略选择最大可能的动作（或从结果分布中采样）；
对模型执行该动作；
重复上述过程，知道魔方复原。
看上去这样是可以奏效的，但是在实践中，这样的方法却行不通。主要原因是模型质量不过关。由于状态空间巨大，加上神经网络特性，对于所有输入状态，不可能经过训练使得NN返回准确的最佳动作。也就是说，模型并没有告诉我们明确的求解思路，只是向我们提出值得探索的方向，但这些方向可能使我们更接近解决方案，也有可能会引起误导。因为在训练过程中，不可能处理所有可能状态。要知道，即使使用GPU以每秒处理数十万状态的速度进行训练，对于4.33×10¹⁹的状态空间，也需要经过一个月的训练时间。因此，在训练中我们只取状态空间的一小部分，大约为0.0000005％，这就要求我们使用更复杂的方法。
有一种非常适用的方法，即“蒙特卡洛树搜索”，简称MCTS。该方法有很多变体，但总体思路很简单，可以与众所周知的蛮力搜索方法（如“广度优先搜索BFS”或“深度优先搜索DFS”）对比来进行说明。在BFS和DFS中，我们尝试所有可能的动作，并探索通过这些动作获得的所有状态对状态空间进行详尽搜索。可以发现，这种方式是上述过程的另一个极端。
MCTS在这两种极端之间进行折衷：我们想要执行搜索，并且存在一些值得关注的信息，但是，某些情况下信息可能是不可靠的噪声或错误，有时信息也可能提供正确的方向，从而加快搜索过程。
正如上文提到的，MCTS是一类方法，不同方法在具体细节和特征方面有所不同，本文使用的是UCT方法（Upper Confidence bound1 applied to Trees）。该方法在树上操作，其中节点是状态，边是动作，将所有状态联系起来。在多数情况下，整个树是非常巨大的，因此我们不会试图构建整个树，只是构建其中的一小部分。首先，让我们从一棵由单个节点组成的树开始，也就是我们的当前状态。
每执行一步MCTS，都要沿着树探索某些路径，一般可以面对以下两种选择：
当前节点是叶节点；
当前节点在树的中间，并具有子节点。
对于叶节点，通过对状态执行所有可能的动作对其进行“扩展”，并检查所有结果状态是否为目标状态（如果找到了魔方复原的目标状态，则搜索完成）。然后，将叶节点状态传递给模型，输出值和策略，将其存储备用。
如果当前节点不是叶节点，那么我们能够知道该节点的子节点（可到达状态），并从网络获得值和策略输出。因此，我们需要决定选择哪条路径（换句话说，探索哪种行动最优）。这一决定极其重要，甚至称得上是强化学习方法的基石，即“探索-利用问题”。一方面，神经网络的策略告诉我们该怎么做，另一方面，对于策略出错的情况，可以通过探索周围的状态来解决。但由于状态空间巨大，不能一直探索，这就要求我们在这两者之间保持平衡，这直接影响着搜索性能和结果。
为解决这个问题，对于每个状态，我们为每个可能的动作（共12个）设置计数器，每次在搜索过程中选择某一动作，相应计数器就会增加。在决定采取特定动作时，可以通过计数器进行判定，即某一动作的执行次数越多，将来选择的可能性就越小。
此外，模型返回的值也用于辅助决策，即从当前状态的值及其子节点状态的值中选择最大值进行跟踪。根据这样的模型，可以从父节点的状态找到最可能的路径。
总而言之，对于非叶节点状态，通过以下公式选择要执行的动作：
其中，N(s,a)是状态s选择动作a的次数，P(s,a)是模型为状态s返回的策略，W(s,a)是模型根据状态s的分支a下所有子节点状态返回的最大值。
重复此过程，直到找到解决方案或时间耗尽。为加快此过程，MCTS通常以并行方式进行，利用多个线程同时执行多个搜索。在这种情况下，可以从A(t)中减去一些额外损失，以防止多个线程探索相同路径。
为使用MCTS树得到复原方案，论文作者提出两种方法：
naïve：得到目标状态后，使用从根状态开始的路径作为复原方案；
BFS方法：得到目标状态后，对MCTS树执行BFS，以找到从根到此状态的最短路径。
论文提到，第二种方法找到的复原方案比第一种方案更短，这并不奇怪，因为MCTS过程的随机性，在第一种复原方案路径中可能引入了无用的循环。
论文结果
论文的结果令人印象深刻。在使用三个GPU并行训练了44小时之后，网络学会了类似甚至超过人工复原魔方的方案。最终，将本文模型DeepCube已与先前介绍的两种求解方法进行了比较，分别是Kociemba two-staged solver 和Korf IDA*。
为验证本文方法的效率，论文使用640个随机打乱的魔方对不同方法分别进行测试，并设置最大求解步骤为1000步，最大求解时间为1小时，实现发现DeepCube和Kociemba方法均能在限制步骤和时间内复原魔方。 具体而言，Kociemba求解速度非常快，其中值仅为一秒钟，但是由于依赖人工定义规则，其求解并不总是最短的。DeepCube方法花费了更多的时间，中值约为10分钟，但在55％的情况，该方法会比Kociemba得到更好的复原方案，即更少的步骤。从我个人的角度来看，55％虽然不足以说NN明显更好，但至少证明该方法还不错。下图（摘自论文）显示了所有求解方法的复原步数分布。可以看到，由于复原时间较长，在1000步魔方复原测试中没有比较Korf求解方法，但为了将DeepCube与Korf求解方法的性能进行比较，论文进一步设计了更容易的15步魔方复原测试集。
实现细节
好的，现在我们开始介绍代码实现。在本部分中，我将简要介绍代码方案及一些关键设计，但在此之前，我还是要先强调一些事情：
我不是该项目的研究人员，因此这段代码只是想要复现论文的方法。但不幸的是，由于论文没有提供确切的超参数信息，因此我进行了大量猜测和试验，但实现结果与论文的结果依然存在较大差异。
同时，我试图以通用方式实施所有操作来简化实验。例如，有关魔方状态和转换的详细信息不做详细展示，仅仅通过添加一个新模块来抽象化3x3魔方问题。在我的代码中，分别对2x2魔方和3x3魔方进行实验，但类似这样有固定可预测动作集的、环境完全可见的问题都可以通过这样的方式进行解决。下一节会做详细说明。
相比代码性能，我更关注代码的可读性与简洁性，当然，对于不引入过多复杂性与成本消耗就能提高模型性能的操作，我在代码中还是保留了它们。例如，仅通过分割魔方数据集和正向网络传递，就可以将训练过程加快5倍。但是，如果需要将大多数内容重构为多GPU和多线程模式，我为简单起见就没有这样做。典型的就是MCTS进程，通常采用多线程代码实现，加快模型速度，但这就需要处理进程之间的同步问题。我没考虑那么多，只是以串行方式进行MCTS，仅对批量搜索进行了简单优化。
综上，我的代码由以下几部分组成：
魔方环境，用于定义观察/状态空间、可能的动作以及网络状态的表示，见libcube / cubes模块；
神经网络，包括要训练的模型、训练样本的生成和循环训练过程。见the training tool和libcube / model.py模块；
魔方复原方法, 见the solver tool和libcube/mcts.py；
其他一些不同组件，例如超参数的配置文件和魔方数据生成文件等。
魔方环境
正如前文介绍的，组合优化可不是个小问题，而且种类繁多，即使单就魔方而言，也包含数十种变体，包括2x2x2、3x3x3和4x4x4Rubick魔方，以及Square-1，Pyraminx等。本文介绍的方法不依赖于预定义的领域知识、动作集和状态空间大小，具有较强的适用性。具体而言，求解魔方问题基于以下假设：
环境状态必须是完全可观察的，根据观察结果可以区分不同状态。在魔方问题中，我们可以观察到魔方所有面的状态，因此该问题符合我们的假设。但对于类似扑克牌这样的问题，我们是看不到对手的牌的，本文方法就不再适用了。
动作的数量是离散且有限的。在魔方复原问题中，我们只需执行12中动作，这符合假设。但是对操作空间是“旋转角度α∈[-120°…+ 120°]”这样的非离散动作的问题，就需要不同的处理方法了。
环境的准确建模。换句话说，我们要能够回答以下问题：“对状态s采取行动a会产生什么结果？”。如果无法解决这样的问题，ADI和MCTS方法都会失效。这个要求对于实现模型是及其必要的。然而，对于大多数问题，并不存在这样的模型，或者模型的输出非常嘈杂，但在象棋或围棋之类的游戏中，游戏规则即是这样的符合要求的模型。
领域确定性。即对相同状态的相同动作会得到相同的最终状态。不过我觉得，即使采取随机行动也应该会起作用，但也不一定。
为了使我们的方法可以很方便的迁移到非3x3魔方的问题，我将所有具体的环境信息都移到了一个单独模块，并通过抽象接口CubeEnv与其余代码进行联系（见此处）。通过这样的方式，每个环境都有一个名称，指定环境名称即可使用相应的的环境类型。目前，我们定义了两种不同的环境：经典三阶魔方cube3x3和二阶魔方cube2x2。
如果你要使用自己的魔方数据或其他不同的环境，只需要修改该模块，通过接口即可在其它代码中使用你自定义的环境。
训练
模型训练过程见train.py和libcube/model.py。为简化实验，同时增强实验的可重复性，在单独的ini文件中设置训练的所有参数，包括：
要使用的环境的名称，我们提供了cube2x2和cube3x3两个环境；
运行名称，在TensorBoard的名称和目录中显示，并用于保存模型；
ADI的目标值计算方法。本代码提供两种计算方式：一种是原论文的方法，另一种是我改进的方法。实验表明，我的改进方法收敛更加稳定；
训练参数，包括batch、是否使用CUDA、学习率、LR衰减等。
可以在ini文件夹查看我的实验设置。训练过程中，TensorBoard参数被写入runs文件夹，并将最优模型保存到saves文件。
搜索过程
训练的结果是一个带有网络权重的模型文件。根据模型可以使用MCTS方法复原魔方，具体实现见solver.py和libcube/mcts.py模块。
其中，求解器可用于不同模式：
复原一个杂乱魔方。该魔方由一系列由逗号分隔的动作索引打乱，该序列由-p选项传递。例如，-p 1,6,1是依次执行第二个动作、第七个动作、第二个动作来打乱魔方。动作执行是面向特定环境的，通过-e选项传递，在魔方环境模块可以找到带有索引的动作。例如，2x2魔方的动作1,6,1分别表示L，R'，L变换。
从文本文件（每行代表一个魔方数据）读取排列并进行复原。文件名通过-i选项传递。我在cubes_tests文件夹提供了几个示例，此外，你还可以使用gen_cubes.py生成自己的数据集。
生成更多步骤的打乱魔方并进行复原。
执行复杂的系列打乱测试，并对其复原，然后将结果写入csv文件。通过-o选项可以启用此模式，这可用于评估模型的质量，但同时也需要花费更多的时间。一旦选择该选项，就会生成测试结果图。
在所有情况下，都需要使用-e选项来传递环境名称，并使用-m选项传递模型文件。此外，还有其他参数可以调整MCTS、时间或搜索步长等，在此不做过多赘述。
实验结果
一开始我已经说过，我不是论文的研究人员，因此本工作仅仅是复现论文并进行简单实验。但是，原论文没有提供相关方法的详细信息，例如超参数，在训练过程中对魔方打乱的步数，收敛性等等。为获取这些信息，我已向论文作者发送了一封电子邮件，但至今未收到他们的回复。
因此，我进行大量的实验，但实验结果与论文结果仍存在较大差异。首先，原始方法的收敛非常不稳定，即使降低学习率和增大batch，训练依然不稳定，值损失呈指数增长，如下图所示。
经过多次实验，我认为导致这种现象的原因是原始方法中值目标是错误的。
确实如此，在公式vᵢ = maxₐ(v(s, a) + R(A(s, a)))中，网络返回的值v(s,a)总是与实际奖励R(s)相加，即使对目标状态也是这样。这样，网络返回的实际值可以是-100、10⁶或3.1415。这样大的差异对神经网络极不友好，尤其是MSE值目标。
为此，我做了以下修改，将目标状态值设为0：
具体而言，指定参数value_targets_method = zero_goal_value而不是默认的value_targets_method = paper，你可以在ini文件中选择该新的目标函数。
通过这种简单修改，训练过程模型可以更快地收敛稳定状态，见下图。
二阶魔方
原论文中，使用三个Titan XP GPU并行训练了44小时，在这个过程中，模型总计看过约80亿魔方状态。根据这样的叙述，可以得到训练速度约等于每秒查看50000魔方状态。我的实现在单个GTX 1080Ti上进行，其训练速度为15000/秒，与论文差别不大。因此，使用论文的数据，在单个GPU上训练一次大概需要6天时间，这使得实验和超参数调整及其困难。
为解决这个问题，我设置了简单的2x2魔方环境，只需一个小时的训练时间。如果你也想继续复现，可参见repo中的两个ini文件：
cube2x2-paper-d200.ini：使用原论文中的值目标方法；
cube2x2-zero-goal-d200.ini：改进的0值目标计算方法。
在这两种配置中，状态批次均为10k，魔方打乱步骤为200，其他训练参数也相同。
分别进行训练后，生成了两个模型（模型文件）：
原论文方法的损失为0.18184；
改进0值方法的损失为0.014547。
实验表明，模型损失越小，成功率越高，可用于复原更多打乱步骤的魔方。两种模型的实验结果如图所示。
接下来对魔方复原过程中的MCTS步骤进行对比。如下图所示，改进的0目标模型通常以更少的步骤复原魔方，也就是说，该模型学到更优的复原策略。
最后，比较不同魔方复原方法的长度。下图绘制了naïve和BFS方案的长度。从图中可以看出，naïve方法的长度要比BFS长约10倍，这表明调整MCTS参数可以改善模型性能。同时还可以发现，“零目标”模型的解决方案比原论文模型更长，其原因可能是前一种方法不存在更长的复原路径。
三阶魔方
3x3魔方的模型训练过程要复杂的多，所以在这里仅进行简单介绍。但即使只是简单的实验，也表明0值目标函数可以极大地提高训练稳定性和模型质量。另外，三阶魔方训练一次大约需要20个小时，想要进行大量实验需要花费很多时间和耐心。
正是由于上述原因，我的实验结果不如论文所示结果，我得到的最佳模型仅解决12-15步的乱序魔方复原问题，对于更复杂的问题则无能为力。如果你想获得更好的效果，可能使用更多CPU内核+并行MCTS来提升模型性能。为了获得数据，我将搜索过程限制在10分钟内，并对每个乱序干扰生成五个随机干扰。
下图是论文方法与改进的零目标值方法的比较。
下图所示为找到的最佳解决方案的长度。图示表明两点：第一，在10-15干扰深度范围内，“零目标”方法求解长度大于论文的，这意味着模型虽然没有找到生成测试数据的干扰序列，但发现了更长其他解决方法；第二，对于12-18深度范围，原论文方法找到比干扰序列更短的解决方案，可能的原因是生成了简并测试序列。
进一步的改进和实验
针对上述研究，有许多其他方法可提升模型性能，改进实验结果。比如：
更详细的输入和更复杂的神经网络。由于魔方问题非常复杂，仅仅通过简单的前馈神经网络并不能获得最佳模型，考虑卷积网络可能会提升模型的学习能力；
训练期间的振荡和不稳定性在RL问题中十分常见，这可能是步间相关性导致的。通常的解决方法是，在使用策略网络学习引导值时引入目标网络；
引入临时缓冲区可提高训练速度；
实验表明，样本加权（与扰乱深度成反比）有助于获得更好的策略，该策略知道如何解决扰乱魔方问题，但这也可能使对更深状态的学习过程变慢。为此，可以使用自适应权重，以减少其在后续训练阶段的影响；
在训练过程中使用熵损失来正则化学习策略；
2x2魔方的训练模型没有考虑到魔方问题中存在的不动中间块，因此整个二阶魔方都可以旋转。由于二阶魔方的状态空间很小，所以无需考虑冗余的相同状态，但对于4x4魔方来说，去冗余至关重要；
多次实验寻找更好的训练参数和MCTS参数。
感谢你的阅读，期待你的评论！本文的PDF文件可从此处下载。
AI研习社是AI学术青年和AI开发者技术交流的在线社区。我们与高校、学术机构和产业界合作，通过提供学习、实战和求职服务，为AI学术青年和开发者的交流互助和职业发展打造一站式平台，致力成为中国最大的科技创新人才聚集地。
如果，你也是位热爱分享的AI爱好者。欢迎与译站一起，学习新知，分享成长。
雷锋网版权文章，未经授权禁止转载。详情见转载须知。
