量子位 出品 | "大众号 QbitAI

小时候，觉得大家都在玩魔方。

我也买了一个，费尽脑细胞才拼出一层。
然后，就没有然后了……

后来碰着会玩魔方的小伙伴，我总是忍不住仰慕一下他的操作。

但是没想到，有一天，我还能碰着一个会玩魔方的人工智能。

最近，加州大学欧文分校的一个研究小组，发布了基于强化学习的魔方复原AI。

这只AI 完备不须要依赖人类的知识来解魔方，有速率有准度。
听说没有它复原不了的魔方。
除了这一种——

△ 某机器人选手强力碎魔方

如何让AI自己学会破解魔方？

第一步是建立AI对魔方的基本认知。

魔方有26个小方格，可以按照它们身上的贴纸数量来分类——

中央，一张贴纸。

边边，两张贴纸。

角角，三张贴纸。

这样一来，54张贴纸，每张都有自己独一无二的身份，即身属哪类方格，同一方格上的其他颜色有哪些。

用独热编码 (one-hot encoding) 便可以轻松表示每张贴纸的位置。

不过，由于每一张贴纸的位置不是独立的，而是和其他贴纸干系。
这样，把表示办法降个维，每个方格可以只看一张贴纸。
系统视角便是图中右边的样子——

△ 右侧双色是降维后的视角

然后，按朝向来标注魔方的6个面，前(F)，后(B)，左(L)，右(R)，上(U)，下(D) 。

正对要操作的那一壁，顺时针转 (90度) 直接用这几个字母就行了，逆时针在字母后面加个撇。
比如，R和R’便是把右面顺时针转90度，以及逆时针转90度。

这样算的话，6个面，操作一共有12种。

每一个韶光步(t)，都有一个状态(st) ，都会实行一个动作 (ta ) 。
然后，就有了一个新状态(s t+1 ) ，得到一个褒奖数值(Rs t+1 ) ，成功是1，没成功是-1。

三阶魔方的状态有4.3e^19种，而个中只有一种状态能够收到褒奖旗子暗记，那便是复原成功的状态。

正因如此，同样是走在强化学习的大路上，魔方和围棋之类的游戏，存在明显的不同。

在这样险要的情形下，如果利用A3C算法，理论上有可能永久到不了终点。

面对罕有的褒奖，团队受到策略迭代 (policy iteration) 的启示，提出了一种名为“自学迭代 (Autodidatic) ”的深度强化学习算法，简称ADI。

在这里，策略评估和策略优化两个步骤会交替进行，终极找到最优策略。
而把策略迭代和代价迭代 (value iteration) 结合在一起，便可以把评估和优化合而为一。

这还不是全部，把ADI和蒙特卡洛树搜索 (MCTS) 搭配食用，便称为“DeepCube (深度魔方) ”。
到目前为止，复原魔方成功率高达100%。

自学迭代 (ADI)

ADI的演习，用的是一个迭代监督学习过程。

深度神经网络fθ，要先学习一个策略 (policy) ，理解在已知的状态下，该当采纳若何的旋转动作。

深度神经网络fθ(s)，参数θ，输入的是状态s，输出的是一个代价和策略的组合 (v,p) 。
这个输出可以为MCTS铺路。

天生演习样本，要从复原完成的状态 (ssolved) 开始。

从初始状态打乱魔方，迁徙改变k次，得到k个魔方的序列。
把上述打乱活动重复l次，天生kl个演习样本。

△ 后代天生中

给每一个演习样本，天生它的12个后代的状态，然后用当前的代价网络，来估计每个后代的代价。

然后，这些后代里面，代价评估的最大值，便是这个样本的代价演习目标。

而最大值对应的动作，便是这枚样本的策略演习目标。

复原大法

这里，蒙特卡洛树搜索 (MCTS) 才要出场。

团队用了一个异步MCTS，并用之前演习好的fθ网络帮它增强了一下——策略输出p可以降落它的广度，代价输出v可以降落它的深度。

要为每一个已知状态s0，种起一棵搜索树。

树苗是T={s0}，迭代就从这个单一的凑集开始。

在树苗身上实行仿照遍历 (simulated traversals) ，直至到达一个叶节点 (leaf node) 为止。

每一个状态(s’)，都有它的专属影象——

Ns(a)，是从s开始，实行某个动作a的次数。

Ws(a)，是动作a从s那里得到的最大代价。

Ls(a) ，是动作a在s处的virtual loss (虚拟丢失) 。

Ps(a) ，是动作a在s处的先验概率。

每一次仿照，都是从根节点开始，跟随着树的策略，不断跌带着选择各种各样的动作。

每一个韶光步，都会选择一个动作。

而Virtual loss可以避免搜索树多次关照同一个状态，也可以阻碍多个异步worker走上同样的道路。

到达一个叶节点之后，状态就会加上后代 (s’) 。
这样，树上有了新的元素，后代也会天生自己的影象。

生生不息。

枝繁叶茂之后，测试一下效果：DeepCube大战其余两个魔方高手算法。

一个是Kociemba在1992、1992年提出的两段式算法，依赖人类供应的领域知识，用群论来解魔方。
这种方法的特点是运行速率非常非常快，也的确能解开任何状态下的魔方。
但它所找到的解法，常日不是最优解，比其他方法要多花几步。

另一个是Korf在1997年提出的迭代式深入A(IDA\)算法。
这种方法借助模式库进行启示式树搜索，无论在什么样的初始状态下，都能找到最优解，但探求答案的过程要花费很永劫光。

这些方法展开了两场竞赛。

第一场，DeepCube和Kociemba的方法用640个随机打乱的魔方进行了比拼，这些魔方都被胡乱拧了1000次。

两种方法都在1小时之内解开了全部魔方，Kociemba方法的速率比较快，每个魔方用时不到1秒，而DeepCube均匀每个魔方用了10分钟。

Kociemba方法找到的解法都在31-33步的样子，DeepCube的解法分布轻微广一点，大概从28到35都有，不过作者们说，在55%的情形下都能匹敌Kociemba方法。

第一场，比速率。

DeepCube和Kociemba都成功复原了640个 (1000次打乱) 魔方。

DeepCube单个魔方用时的中位数是10分钟，Kociemba是不到1秒钟。
但，在55%的魔方大战中，DeepCube或与后者速率相称，或好于后者。

实在自学成才的DeepCube和人类聪慧结晶的Kociemba，基本上还算旗鼓相当。

至于Korf？这位选手玩一个魔方须要6天。

△ 人类速拧比赛现场

第二场，比最优解。

100个魔方，每个经由15次打乱。

这次Korf比较厉害，中位数是13步，只有一个魔方超过15步。

不过，DeepCube也不差，在74%的魔方上，都和Korf找到了一样的最优解。
当然DeepCube超过15步的次数，比Korf略多一点。

至于kociemba？成绩太差，惨不忍睹。

顺便，再和人类比拟一下，三阶魔方最少步数的天下比赛中，人族的最好成绩是22步。

如此看来，DeepCube堪称魔方全能小王子。

我们一贯强调说，这个魔方AI，不依赖任何人类履历。

但是，从末了的结果看，DeepCube也和人类选手类似，学到了一些“套路”，包括用繁芜的排列组合来解魔方，以及与人类速拧选手附近的策略。

比如，DeepCube大量利用一组特定的操作，即aba-1。
便是先实行某个迁徙改变a，再实行其余一个迁徙改变b，末了把a步骤转回去。

团队检讨了DeepCube处理640个完备打乱的魔方时，创造AI常常利用这样的操作，这样能在移动某些方格的过程中，让其他方格不要受到影响。
详细来说，便是查看每三次相邻的迁徙改变，涌现频次最高的14种，都是aba-1格式。
比其他格式的涌现频率明显要高。

至于现在嘛，团队可能以为，自家的AI复原三阶魔方已经百发百中了，于是就开始研究四阶魔方，以及各种奇奇怪怪的魔方。

团队可能以为，自家的AI复原三阶魔方已经百发百中了，于是就开始研究四阶魔方，以及各种奇奇怪怪的魔方。

其余，走出魔方的天下，他们以为这种方法也可以用来处理其他组合优化问题，比如预测蛋白质的三级构造。

许多组合优化问题，都可以想成序列决策问题，也就可以用强化学习来办理。

这篇论文已经提交到NIPS，题目是：Solving the Rubik’s Cube Without Human Knowledge

传送门在此：

https://arxiv.org/pdf/1805.07470v1.pdf

有奖 (吗) 竞猜，那个碎掉魔方的机器人选手，来自哪里？

在量子位"大众年夜众号（ID：QbitAI）对话界面，回答：“魔方”两个字，答案急速揭晓。

— 完 —

诚挚招聘

量子位正在招募编辑/，事情地点在北京中关村落。
期待有才华、有激情亲切的同学加入我们！
干系细节，请在量子位"大众年夜众号(QbitAI)对话界面，回答“招聘”两个字。

量子位 QbitAI · 号签约作者

վ'ᴗ' ի 追踪AI技能和产品新动态