您现在的位置是: 首页 > 人工智能 >

AI在1.2秒内解决了Rubik的立方体

  • 2019-08-01 09:04:42    来源:   作者:

根据周一发表在Nature Machine Intelligence上的研究,一个新的神经网络可以解决魔方的速度是最快的人类速度的两倍 - 尽管比最快的哑算法快三倍。

虽然人工智能方法并不是最快的传统计算方法,特别是麻省理工学院的世界一流的min2phase算法,但它超越了老式游乐场的难题:一方面,它可以更好地用于研究蛋白质。

自20世纪70年代末创建以来,人们对这种受欢迎的玩具着迷。世界多维数据集协会是一个专注于组合益智游戏的组织,如魔方,每年举办几场比赛,挑战粉丝尽快解决。参加这些比赛的人被称为speedcubers,而目前的世界纪录属于Yusheng Du,这是一个中国的速度赛,只用了3.47秒便打破了这个难题。

但杜可能不像DeepCubeA这样的机器学习软件。该系统由加州大学欧文分校(UCI)的一组研究人员开发,由一个深度神经网络组成,可以在1.2秒内平均解决一次魔方数,森林阿戈斯内利,该论文的第一作者和UCI的博士生告诉The Register。

这很快,但没有使用麻省理工学院研究人员去年开发的min2phase算法 的机器人系统那么快。

Min2phase没有神经网络,没有经过训练,也没有使用任何机器学习技术:它只是为了求解立方体而编程,而且它可以做到(而且它能够非常快速地完成),而DeepCubeA具有潜力做更多。一方面,显然为什么Min2phase应该更快,尽管另一方面,我们已经看到AI代码在基本数据结构上比传统的哑算法运行得更快。

上帝的数量

DeepCubeA使用强化学习进行训练。从拼图的随机组合开始,它必须找到一种策略,该策略将最小化其“成本转移功能”,其计算成本 - 或移动量 - 以达到完美的解决状态。目标是尽可能降低功能,以便尽快破解游戏。

你需要按顺序执行一系列特定的移动,考虑到有43252,003,274,489,856,000 - 大约43种可能的组合,让DeepCubeA随机启动是不可行的。因此,研究人员反过来训练它。它被置于序列中的一个特殊状态,这将导致它被解决并被要求从那里开始。

研究人员用超过两天的时间训练了DeepCubeA,使用了100亿种不同的魔方组合,并要求它在30次移动中解码所有这些组合。它在1000个谜题上进行了测试并设法解决了所有问题,并且在60%的时间内以最少的移动进行了测试。从数学上证明,从任何一个州开始,魔方可以在20次或更少的移动中被破裂,这个数字被称为神的数字。

DeepCubeA并不完美,并且不能完全达到God's Number。最短的路径是平均21次移动。由于这是具有挑战性的,因此软件需要大约24秒才能完成拼图。最高速度的球员也远离神号,并且在大约四秒内为顶级球员大约50次移动来解决立方体。

“人类常见的算法是将十字架放在顶部,然后是顶角,然后是第二层,然后是底层,”Agostinelli向The Register解释道。

“这是一个相对简单的程序,然而,它远非最短的路径。要以尽可能少的移动来解决它需要更多的思考。这个概念也适用于机器。找到更短的路径,一般来说,需要更多时间。“

有目的的玩具

虽然Rubik's Cube仅仅是玩具,但用于解决它的AI算法可以应用于许多其他问题。研究人员对预测蛋白质结构感兴趣,以帮助药剂师设计药物以针对特定的身体机能。

“蛋白质的结构,如Rubik's Cube和本文研究的其他谜题,有很多可能性,但只有少数,通常只有一种,这些可能性被认为是一种解决方案,”Agostinelli说。“我们想要修改DeepCubeA算法进行蛋白质结构预测。“

“更一般地说,魔方是一个寻路问题:我如何从A点到达B点?路径寻找是机器人领域的一个大问题,可能需要人们做出复杂的决策; 尤其是在有很多可能性的大型环境中 像DeepCubeA这样的算法能够学习在10 19到10 62的环境中解决这个寻路问题。可能的状态,可以推广到其他寻路任务,“他总结道。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。
Top