强化学习算法deepcube，机器自行解决复杂魔方问题 | 雷峰网-亚博电竞网
译者：ai研习社（）
双语原文链接：
前瞻
我花了近一年的时间写一书，距离该书出版已经过去半年了，在这段休整时间，我发现自己对强化学习的热情已经无法退却。无论是研究不同的rl方法，或是复现论文代码，对我而言是极大的乐趣。幸运的是，rl在各个领域均在迅速发展，很多有趣的主题值得探讨。
引言
多数人对深度强化学习的认识主要集中在应用drl进行游戏，这并不意外，因为在2015年首次应用drl进行atari系列游戏，并大获成功。
事实证明，系列套件与rl的结合简直是天作之合，即使是现在，许多研究论文仍使用该套件来验证自己的方法。随着rl的发展，经典的53种atari游戏的挑战性越来越小（在撰写本文时，rl在一半以上的游戏表现超过人类），所以，现在的一些研究转向更复杂的游戏，例如starcraft和dota2。
由于上述原因，会给人一种错觉，即“ rl是用来玩游戏的”，事实显然不是这样。在我2018年6月出版的书中，我不仅介绍了rl在atari游戏的应用，也介绍了其他领域的不同示例，包括股票交易（），聊天机器人和nlp（），自动驾驶（），持续控制（） ）和棋盘游戏（）。
实际上，基于mdp的rl可以用于各种不同的领域，计算机游戏只是关于复杂决策的一个简易且关注度高的领域。
在本文中，我将详细介绍将rl应用于的最新研究工作。本文对uci（加利福尼亚大学欧文分校）的研究人员发表的论文“”进行解读。除了论文解读之外，我还使用，通过训练模型和流程解读实验，并对论文方法进行改进。
下文我将结合代码对论文的方法进行介绍，以加深对相关概念的理解。如果你只对理论方法感兴趣，可以跳过代码部分。
ok，现在开始吧！
rubik魔方和组合优化问题
我估计每个人都知道魔方是什么，所以我就不做过多了，而是将这部分的重点放在它与数学和计算机科学的联系。如非特殊说明，本文中的“立方体”是指3x3经典魔方。除了3x3经典魔方，还有其他一些变体魔方，但3x3经典魔方至今仍是最受欢迎的。
虽然看起来rubik的3x3模型似乎非常简单，但考虑到各种可能的旋转转换，这其实非常棘手。据计算，3x3经典魔方旋转状态总共有4.33 × 10¹⁹种不同状态。如果考虑一些魔方拼接出错的情况，即模仿无法通过旋转复原，只有拆解重新进行合理的拼接，那么总状态增加约12倍（≈5.19×10²⁰）。
所有状态都可以通过各种旋转组合得到。例如，在某种状态下顺时针旋转魔方左侧，就会达到一种新的状态，从该状态逆时针旋转同一侧就会回到原始状态。另外，如果连续三次旋转魔方左侧，则回到原始状态的最短路径是再将魔方左侧顺时针旋转一次，而不是逆时针旋转三次（虽然这样也可以，但却不是最佳的） 。
由于3x3魔方有6个面，并每个面可以沿两个方向旋转，因此总共有12种旋转方式。当然，直接旋转半圈（在同一方向上连续两次旋转）也是可以的，但为简单起见，我们将其视为两次旋转。
数学中，有一些领域专门研究这样的对象，最典型的便是抽象代数。抽象代数是数学研究的一个重要方向，也是现代计算机理论基础之一，主要研究抽象对象集及其代数操作。根据抽象代数，rubik魔方是一个非常复杂的‘’，有许多有趣的属性。
但是魔方不只是简单的状态和变换，它还是不确定的，其主要目标是找到一个可以复原魔方的旋转序列。这样的问题可以通过进行研究，组合优化也是应用数学和理论计算机科学的一个典型子领域。该领域包含许多有价值的典型问题，例如：
：在图中找到最短的路径；
：寻找蛋白质的3d结构；
资源分配：通过在消费者之间分配固定的资源，以获得最佳目标。
还有其他一些类似的问题。这些问题的共同之处在于状态空间特别大，从而导致通过遍历所有可能组合以找到最佳亚博电竞网的解决方案是不可行的。rubik魔方也属于这类问题，该问题状态空间为4.33×10¹⁹，想要通过蛮力求解几乎不可能。
最优化与‘上帝之数’
使组合优化问题变得棘手的原因是，尽管我们非常清楚该怎样达到问题的目标状态，但实际上我们并没有很好的亚博电竞网的解决方案。魔方问题尤其如此：在发明魔方之后，就确定了通过12种旋转可以达到目标状态，但ernő rubik花了大约一个月的时间才找到一种复原方法。如今，有了许多不同的魔方复原方法，包括入门方法、jessica fridrich方法和许多其他方法。
所有这些方法差异巨大。例如，入门方法需要记住5-7种旋转序列旋转大约100次才能还原魔方。与之形成对比的是，当前三阶魔方还原的世界纪录是4.22秒，这需要更少的步骤，但也要求挑战者需要记忆和训练大量的旋转序列。jessica fridrich方法平均约需55个动作，但需要熟悉大约120个动作序列。
但是，最大的问题是：给定任意状态的三阶魔方，其还原最短动作序列是什么？十分遗憾，尽管三阶魔方已经有54年的历史了，这个问题依然没有答案。只有在2010年，google的研究小组证明，解决任何魔方状态所需的最小移动量为20，该数字也称为‘上帝之数’。当然，这只是一个平均数字，最佳亚博电竞网的解决方案可能要短一些，也就是说，复原很多魔方平均需要20步移动，但某个状态可能不需要任何移动（已复原状态）。
但是，上述研究仅证明了最少平均移动量，却没有找到实际的亚博电竞网的解决方案。如何找到任何给定状态的最优解仍然是一个悬而未决的问题。
魔方复原的方法
在之前，魔方复原问题主要有两个研究方向：
使用群论方法，显着减小要搜索的状态空间。这种方法种最典型的包括；
使用蛮力搜索以及人工定义的启发式搜索，使搜索指向最有可能的方向。典型的如，该算法使用a *搜索和大型模式数据库避免选择错误的方向。
本文介绍了第三种方法：通过在海量不同状态的魔方数据集上训练神经网络，获得求解状态方向的策略。该训练不需要提供任何先验知识，仅需要魔方数据集（不是物理魔方，而是计算机模型）。这是其与上述两种方法的最大不同：前两种方法需要大量的领域知识，并以计算机编码进行定义。
后续章节是新的论文方法的详细介绍。
数据表示
我们从数据表示开始介绍。在三阶魔方问题中，我们首先对动作和状态以某种方式进行编码。
动作
此处的动作是指魔方在任何状态下可能的旋转，前文已经说过，我们总共只有12个动作。对于3阶魔方，共有左，右，上，下，前和后六个侧面可以旋转。而对每一面，有两种不同的操作，即该侧的顺时针和逆时针旋转（90°或–90°）。一个很小但非常重要的细节是，当需要旋转的面朝向你时，你能方便的进行操作。例如，你可以哦容易的旋转正面，但对于背面而言，总是有些不太习惯。
根据上述说明，动作名称可以根部不同侧面的首字母做出以下定义。如右侧的顺时针旋转命名为r；至于逆时针的动作，可能会使用不同的符号，包括r'/r/r̃。第一种和最后一种表示法对于计算机代码而言不太友好，因此我使用了小写字母来表示动作的逆时针旋转。这样，右侧面的两个动作是r和r，左侧面的两个动作为l和l，依此类推。
在我的代码中，动作空间是通过实现的，其中每个动作映射为唯一的整数。
状态
状态是指三阶魔方当前的排列组合方式，正如前文介绍的，该状态空间极其庞大（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，仅对批量搜索进行了简单优化。
综上，我的代码由以下几部分组成：
魔方环境，用于定义观察/状态空间、可能的动作以及网络状态的表示，；
神经网络，包括要训练的模型、训练样本的生成和循环训练过程。见和；
魔方复原方法, 见和；
其他一些不同组件，例如超参数的配置文件和魔方数据生成文件等。
魔方环境
正如前文介绍的，组合优化可不是个小问题，而且种类繁多，即使单就魔方而言，也包含数十种变体，包括2x2x2、3x3x3和4x4x4rubick魔方，以及square-1，pyraminx等。本文介绍的方法不依赖于预定义的领域知识、动作集和状态空间大小，具有较强的适用性。具体而言，求解魔方问题基于以下假设：
环境状态必须是完全可观察的，根据观察结果可以区分不同状态。在魔方问题中，我们可以观察到魔方所有面的状态，因此该问题符合我们的假设。但对于类似扑克牌这样的问题，我们是看不到对手的牌的，本文方法就不再适用了。
动作的数量是离散且有限的。在魔方复原问题中，我们只需执行12中动作，这符合假设。但是对操作空间是“旋转角度α∈[-120°… 120°]”这样的非离散动作的问题，就需要不同的处理方法了。
环境的准确建模。换句话说，我们要能够回答以下问题：“对状态s采取行动a会产生什么结果？”。如果无法解决这样的问题，adi和mcts方法都会失效。这个要求对于实现模型是及其必要的。然而，对于大多数问题，并不存在这样的模型，或者模型的输出非常嘈杂，但在象棋或围棋之类的游戏中，游戏规则即是这样的符合要求的模型。
领域确定性。即对相同状态的相同动作会得到相同的最终状态。不过我觉得，即使采取随机行动也应该会起作用，但也不一定。
为了使我们的方法可以很方便的迁移到非3x3魔方的问题，我将所有具体的环境信息都移到了一个单独模块，并通过抽象接口cubeenv与其余代码进行联系（见）。通过这样的方式，每个环境都有一个名称，指定环境名称即可使用相应的的环境类型。目前，我们定义了两种不同的环境：经典三阶魔方cube3x3和二阶魔方cube2x2。
如果你要使用自己的魔方数据或其他不同的环境，只需要修改该模块，通过接口即可在其它代码中使用你自定义的环境。
训练
模型训练过程见和。为简化实验，同时增强实验的可重复性，在单独的ini文件中设置训练的所有参数，包括：
要使用的环境的名称，我们提供了cube2x2和cube3x3两个环境；
运行名称，在tensorboard的名称和目录中显示，并用于保存模型；
adi的目标值计算方法。本代码提供两种计算方式：一种是原论文的方法，另一种是我改进的方法。实验表明，我的改进方法收敛更加稳定；
训练参数，包括batch、是否使用cuda、学习率、lr衰减等。
可以在查看我的实验设置。训练过程中，tensorboard参数被写入runs文件夹，并将最优模型保存到saves文件。
搜索过程
训练的结果是一个带有网络权重的模型文件。根据模型可以使用mcts方法复原魔方，具体实现见和模块。
其中，求解器可用于不同模式：
复原一个杂乱魔方。该魔方由一系列由逗号分隔的动作索引打乱，该序列由-p选项传递。例如，-p 1,6,1是依次执行第二个动作、第七个动作、第二个动作来打乱魔方。动作执行是面向特定环境的，通过-e选项传递，在魔方环境模块可以找到带有索引的动作。例如，2x2魔方的动作1,6,1分别表示l，r'，l变换。
从文本文件（每行代表一个魔方数据）读取排列并进行复原。文件名通过-i选项传递。我在文件夹提供了几个示例，此外，你还可以使用生成自己的数据集。
生成更多步骤的打乱魔方并进行复原。
执行复杂的系列打乱测试，并对其复原，然后将结果写入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爱好者。欢迎与译站一起，学习新知，分享成长。
