锐客网

  1. 首页 > 睿知 > >

魔方还原步数最少 魔方还原步数图解

睿知经验知识

魔方还原步数图解，首先将魔方归位 。然后将底层还原按照下层十字、角块归位、中间棱归位的顺序来完成 。接着还原中层，最后还原顶层 。在还原中，需要注重角块和棱块的拼接，遇到不熟悉的情况可以参考相应的算法 。尽量减少步数，使还原更快更有效率 。
魔栗少女 发自 凹非寺
量子位 出品 | 公众号 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次，生成k*l个训练样本 。

推荐阅读


上一篇：荣耀50参数配置中关村 荣耀50参数配置处理器

下一篇：湖北健康码怎么申请静态码？湖北健康码怎么申请转码