前瞻
我花了近一年的时间写《动手深度强化学习》一书，距离该书出版已经过去半年了，在这段休整时间，我发现自己对强化学习的热情已经无法退却。无论是研究不同的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魔方是一个非常复杂的‘群’，有许多有趣的属性。
但是魔方不只是简单的状态和变换，它还是不确定的，其主要目标是找到一个可以复原魔方的旋转序列。这样的问题可以通过组合优化进行研究，组合优化也是应用数学和理论计算机科学的一个典型子领域。该领域包含许多有价值的典型问题，例如：
旅行商问题：在图中找到最短的路径；
蛋白质折叠模拟：寻找蛋白质的3D结构；
资源分配：通过在消费者之间分配固定的资源，以获得最佳目标。
还有其他一些类似的问题。这些问题的共同之处在于状态空间特别大，从而导致通过遍历所有可能组合以找到最佳解决方案是不可行的。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张量编码的，下面我会介绍本文使用的神经网络结构及其训练方法。
