领域|强化学习算法DeepCube，机器自行解决复杂魔方问题( 二 ) 自行解决|rl|强化|机器|算法

由于3x3魔方有6个面，并每个面可以沿两个方向旋转，因此总共有12种旋转方式。当然，直接旋转半圈（在同一方向上连续两次旋转）也是可以的，但为简单起见，我们将其视为两次旋转。
数学中，有一些领域专门研究这样的对象，最典型的便是抽象代数。抽象代数是数学研究的一个重要方向，也是现代计算机理论基础之一，主要研究抽象对象集及其代数操作。根据抽象代数，Rubik魔方是一个非常复杂的‘群’，有许多有趣的属性。
但是魔方不只是简单的状态和变换，它还是不确定的，其主要目标是找到一个可以复原魔方的旋转序列。这样的问题可以通过组合优化进行研究，组合优化也是应用数学和理论计算机科学的一个典型子领域。该领域包含许多有价值的典型问题，例如：
旅行商问题：在图中找到最短的路径；
蛋白质折叠模拟：寻找蛋白质的3D结构；
资源分配：通过在消费者之间分配固定的资源，以获得最佳目标。
还有其他一些类似的问题。这些问题的共同之处在于状态空间特别大，从而导致通过遍历所有可能组合以找到最佳解决方案是不可行的。Rubik魔方也属于这类问题，该问题状态空间为4.33×101?，想要通过蛮力求解几乎不可能。
最优化与‘上帝之数’
使组合优化问题变得棘手的原因是，尽管我们非常清楚该怎样达到问题的目标状态，但实际上我们并没有很好的解决方案。魔方问题尤其如此：在发明魔方之后，就确定了通过12种旋转可以达到目标状态，但Ern? Rubik花了大约一个月的时间才找到一种复原方法。如今，有了许多不同的魔方复原方法，包括入门方法、Jessica Fridrich方法和许多其他方法。
所有这些方法差异巨大。例如，入门方法需要记住5-7种旋转序列旋转大约100次才能还原魔方。与之形成对比的是，当前三阶魔方还原的世界纪录是4.22秒，这需要更少的步骤，但也要求挑战者需要记忆和训练大量的旋转序列。Jessica Fridrich方法平均约需55个动作，但需要熟悉大约120个动作序列。
但是，最大的问题是：给定任意状态的三阶魔方，其还原最短动作序列是什么？十分遗憾，尽管三阶魔方已经有54年的历史了，这个问题依然没有答案。只有在2010年，Google的研究小组证明，解决任何魔方状态所需的最小移动量为20，该数字也称为‘上帝之数’。当然，这只是一个平均数字，最佳解决方案可能要短一些，也就是说，复原很多魔方平均需要20步移动，但某个状态可能不需要任何移动（已复原状态）。
但是，上述研究仅证明了最少平均移动量，却没有找到实际的解决方案。如何找到任何给定状态的最优解仍然是一个悬而未决的问题。
魔方复原的方法