复原混乱的魔方需要几步？诺丁汉大学团队用深

回想在校期间，很多同学会在课间休息时从书桌里掏出魔方或娴熟或略显笨拙地转动起来，甚至上课时有些同学也会悄悄地在桌下转动手中的魔方。现在，“人工智能” 也对这款益智玩具产生了兴趣，期待用更加智能的方式实现魔方的复原。

近日，诺丁汉大学（University of Nottingham）副教授 Colin G. Johnson 带领的研究小组开发出一种深度学习技术，可以从一套样本解决方案中学习 “适应度函数” 并用它来解决魔方复原问题。该研究相关论文于 2 月 24 日发表在Expert Systems上，题目为《用逐级深度学习方法解决魔方问题》（Solving the Rubik's cube ith stepise deep learning）。

图｜相关论文（来源Expert Systems）

将打乱的魔方复原是一个相对复杂的问题，但研究人员决定将这一复杂的问题转换为多个简单的问题来解决，他们认为 “解决任何难题最多需要 20 步”。，他们将逐级学习和深度作为本次设计方案的两种主要方法。对应到魔方复原中，该技术会一步步地去尝试解决，而不是一次性学习复原魔方的整体方案。

换句话说，就是这种技术会通过尝试转动一个部件使魔方呈现更简单的形态，也就是把一个复杂的问题拆解成若干个相对简单的小问题，先学习解决一个小问题的方案，然后经过对这一步骤的数次重复，最终达到魔方复原的效果。其实，该种方案也意味着，整体解决方案的每一步都要比上一步更加容易。

该技术会 “反其道而行之”，从魔方一步步打乱的过程中学习怎样将混乱的魔方复原。具体操作起来就是，将拼好的魔方标记为 “0”，进行一次旋转后的魔方标记为 “1”，再旋转一次后标记为 “2”…… 以此类推。每个状态都与一个数字配对，该数字代表该状态下距离目标的步数。，学习的过程也是建立模型的过程，最终实现从数据库中抽取任意一个状态，预测将需要多少步才能到达目标状态，该步骤就与其被标记的数字相对应。

图｜计算机学习魔方复原的数据（来源Expert Systems）

然后，用特定的深度学习网络构建魔方复原培训集，并在其中搜索出当下的混乱状态和已经解决后的状态。

接下来，通过模拟数千次转动来估算魔方的混乱程度。完成了魔方的混乱程度估计之后，Johnson 开发的技术将通过深度的方式识别魔方复原前的一步，接下来是复原前的第二步、第三步…… 把这些数据积累起来再去解决魔方的复原问题将会非常容易，最终可以通过这些准备工作找出把混乱魔方复原的路径。

Johnson 解释道"与其尝试学习如何解决将整个魔方复原，不如学习怎样把复原魔方这一较为复杂的问题转换为更容易的问题，然后使用更简单的方法来解决它。"

图｜深度学习框架解决魔方问题的步骤（来源Expert Systems）

目前，Johnson 仅将该方案用于魔方的复原，但他也表示，这只是一个示例，其实该技术也可用于解决一些更加复杂的问题。“比如消除留声机、早期唱片中旧录音的噪音。” 具体而言是，如果他设计的技术能学到一个 “原始的声音”、一个比 “原始的声音” 多一点噪音的声音以及一个比 “原始的声音” 多一点再多一点的声音…… 那么最终将通过这种循序渐进的方式还原最 “纯净的声音”。

Johnson 表示，相比其他方式，他设计的这种逐级学习更加有效，也更能凸显分步处理的优势。不过，他也表示，该种训练框架将需要比传统方案更多的对特定领域的知识。以本文为例，训练解决魔方的框架就需要复原魔方的能力。

未来该技术将可能用于解决科学工程的很多其他问题，如用来学习和更好地理解蛋白质在细胞内折叠的方式，从蛋白质呈现的三维结构点序列可以倒推其是怎样折叠成最终形态的。

-End-

参考

https://onlinelipary.iley./doi/10.1111/exsy.12665

https://techxplore./nes/2021-02-deep-technique-rubik-cube-problems.html