突然资讯网
首页 >> 科技 >> 正文

甚至称得上是强化学习方法的基石,魔方问题尤其如此

日期:2020-10-30 18:50:07 来源:互联网 编辑:小狐 阅读人数:493

译者:AI研习社(季一帆)

前瞻

我花了近一年的时间写《动手深度强化学习》一书,距离该书出版已经过去半年了,在这段休整时间,我发现自己对强化学习的热情已经无法退却。无论是研究不同的RL方法,或是复现论文代码,对我而言是极大的乐趣。幸运的是,RL在各个领域均在迅速发展,很多有趣的主题值得探讨。

引言

多数人对深度强化学习的认识主要集中在应用DRL进行游戏,这并不意外,因为在2015年首次应用DRL进行Atari系列游戏,并大获成功。

事实证明,系列套件与RL的结合简直是天作之合,即使是现在,许多研究论文仍使用该套件来验证自己的方法。随着RL的发展,经典的53种Atari游戏的性越来越小(在撰写本文时,RL在一半以上的游戏表现超过人类)所以,现在的一些研究转向更复杂的游戏,例如StarCraft和Dota2。

由于上述原因,会给人一种错觉,即“ RL是用来玩游戏的”事实显然不是这样。在我2018年6月出版的书中,我不仅介绍了RL在Atari游戏的应用,也介绍了其他领域的不同示例,包括股票交易,聊天机器人和NLP,自动驾驶,持续控制 和棋盘游戏。

在本文中,我将详细介绍将RL应用于的最新研究工作。本文对UCI(加利福尼亚大学欧文分校)的研究人员发表的论文进行解读。除了论文解读之外,我还使用,通过训练模型和流程解读实验,并对论文方法进行改进。

下文我将结合代码对论文的方法进行介绍,以加深对相关概念的理解。如果你只对理论方法感兴趣,可以跳过代码部分。

OK,现在开始吧!

Rubik魔方和组合优化问题

我估计每个人都知道魔方是什么,所以我就不做过多魔方介绍了,而是将这部分的重点放在它与数学和计算机科学的。如非特殊说明,本文中的“立方体”是指3x3经典魔方。除了3x3经典魔方,还有其他一些变体魔方,但3x3经典魔方至今仍是最受欢迎的。

虽然看起来Rubik的3x3模型似乎非常简单,但考虑到各种可能的旋转转换,这其实非常棘手。据计算,3x3经典魔方旋转状态总共有4.33 × 10¹⁹种不同状态。如果考虑一些魔方拼接出错的情况,即模仿无法通过旋转复原,只有拆解重新进行合理的拼接,那么总状态增加约12倍(≈5.19×10²⁰)

所有状态都可以通过各种旋转组合得到。例如,在某种状态下顺时针旋转魔方左侧,就会达到一种新的状态,从该状态逆时针旋转同一侧就会回到原始状态。另外,如果连续三次旋转魔方左侧,则回到原始状态的最短路径是再将魔方左侧顺时针旋转一次,而不是逆时针旋转三次(虽然这样也可以,但却不是最佳的) 。

由于3x3魔方有6个面,并每个面可以沿两个方向旋转,因此总共有12种旋转方式。当然,直接旋转半圈(在同一方向上连续两次旋转)也是可以的,但为简单起见,我们将其视为两次旋转。

数学中,有一些领域专门研究这样的对象,最典型的便是抽象代数。抽象代数是数学研究的一个重要方向,也是现代计算机理论基础之一,主要研究抽象对象集及其代数操作。根据抽象代数,Rubik魔方是一个非常复杂的有许多有趣的属性。

但是魔方不只是简单的状态和变换,它还是不确定的,其主要目标是找到一个可以复原魔方的旋转序列。这样的问题可以通过进行研究,组合优化也是应用数学和理论计算机科学的一个典型子领域。该领域包含许多有价值的典型问题,例如:

蛋白质折叠模拟:寻找蛋白质的3D结构。

资源分配:通过在消费者之间分配固定的资源,以获得最佳目标。

还有其他一些类似的问题。这些问题的共同之处在于状态空间特别大,从而导致通过遍历所有可能组合以找到最佳解决方案是不可行的。Rubik魔方也属于这类问题,该问题状态空间为4.33×10¹⁹,想要通过蛮力求解几乎不可能。

最优化与‘上帝之数’

使组合优化问题变得棘手的原因是,尽管我们非常清楚该怎样达到问题的目标状态,但实际上我们并没有很好的解决方案。魔方问题尤其如此:在发明魔方之后,就确定了通过12种旋转可以达到目标状态,但Ernő Rubik花了大约一个月的时间才找到一种复原方法。如今,有了许多不同的魔方复原方法,包括入门方法、Jessica Fridrich方法和许多其他方法。

所有这些方法差异巨大。例如,入门方法需要记住5-7种旋转序列旋转大约100次才能还原魔方。与之形成对是,当前三阶魔方还原的世界纪录是4.22秒,这需要更少的步骤,但也要求者需要记忆和训练大量的旋转序列。Jessica Fridrich方法平均约需55个动作,但需要熟悉大约120个动作序列。

但是,最大的问题是:给定任意状态的三阶魔方,其还原最短动作序列是什么?十分遗憾,尽管三阶魔方已经有54年的历史了,这个问题依然没有答案。只有在2010年,Google的研究小组证明,解决任何魔方状态所需的最小移动量为20,该数字也称为‘上帝之数’当然,这只是一个平均数字,最佳解决方案可能要短一些,也就是说,复原很多魔方平均需要20步移动,但某个状态可能不需要任何移动(已复原状态)

但是,上述研究仅证明了最少平均移动量,却没有找到实际的解决方案。如何找到任何给定状态的最优解仍然是一个悬而未决的问题。

魔方复原的方法

在之前,魔方复原问题主要有两个研究方向:

使用群论方法,显着减小要搜索的状态空间。这种方法种最典型的包括Kociemba算法。

使用蛮力搜索以及人工定义的启发式搜索,使搜索指向最有可能的方向。典型的如Korth算法,该算法使用A *搜索和大型模式数据库避免选择错误的方向。

本文介绍了第三种方法:通过在海量不同状态的魔方数据集上训练神经网络,获得求解状态方向的策略。该训练不需要任何先验知识,仅需要魔方数据集(不是物理魔方,而是计算机模型)这是其与上述两种方法的最大不同:前两种方法需要大量的领域知识,并以计算机编码进行定义。

后续章节是新的论文方法的详细介绍。

数据表示

我们从数据表示开始介绍。在三阶魔方问题中,我们首先对动作和状态以某种方式进行编码。

动作

此处的动作是指魔方在任何状态下可能的旋转,前文已经说过,我们总共只有12个动作。对于3阶魔方,共有左,右,上,下,前和后六个侧面可以旋转。而对每一面,有两种不同的操作,即该侧的顺时针和逆时针旋转(90°或–90°)一个很小但非常重要的细节是,当需要旋转的面朝向你时,你能方便的进行操作。例如,你可以哦容易的旋转正面,但对于背面而言,总是有些不太习惯。

根据上述说明,动作名称可以根部不同侧面的首字母做出以下定义。如右侧的顺时针旋转命名为R;至于逆时针的动作,可能会使用不同的符号,包括R/r/r̃。第一种和最后一种表示法对于计算机代码而言不太友好,因此我使用了小写字母来表示动作的逆时针旋转。这样,右侧面的两个动作是R和r,左侧面的两个动作为L和l,依此类推。

在我的代码中,动作空间是通过python枚举实现的,其中每个动作映射为唯一的整数。

状态

状态是指三阶魔方当前的排列组合方式,正如前文介绍的,该状态空间极其庞大(4.33×10¹⁹个不同状态)但除了要面对海量的状态,我们在选择特定的状态表示形式时,还要考虑到以下这些要求:

避免冗余:在极端情况下,我们可以通过记录每侧每个贴纸的颜色来表示魔方的状态。但是,如果你计算一下这些组合的数量,会发现它等于6⁶*⁸=6⁴⁸≈2.25×10³⁷,远远大于三阶魔方的状态空间大小,这意味着这种表示形式是高度冗余的,例如,魔方两侧中心对称的情况。至于为什么得到6⁶*⁸,很简单:三阶魔方有6个面,每个面除了中心块外有8个小立方体,所以总共有48个贴面,每个贴面可用6种颜色之一上色。

内存效率:在后续的训练和模型应用过程中,我们需要将大量魔方集的不同状态保存在内存中,这可能会影响流程效率。因此,我们希望表示形式尽可能紧凑。

转换性能:另一方面,我们需要对某一状态进行所有可能的旋转操作,并且要求这些操作快速完成。如果在内存中的状态表示非常紧凑(例如使用位编码)这会导致魔方侧面的每一次旋转需要进行冗长的解压缩过程,严重影响训练速度。

适宜的神经网络:就像其他机器学习、深度学习实例中那样,并非每个数据表示都符合神经网络的输入格式。在NLP中通常使用字符或单词嵌入,在CV中将图像从jpeg解码为原始像素,Random Forests则需要对数据进行大量特征设计等。

在本文中,使用独热编码将三阶魔方的每个状态表示为20×24张量。接下来以下图为例,对这种表示方式进行说明。

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图1)

那么,张量维度中的“ 24”是从哪里来的?我们总共要跟踪20种不同的贴面,但是由于魔方旋转,它们可能出现在不同的位置,至于具体位置,这取决于要跟踪的立体块的类型。以角块开始说明,我们总共有8个角块,旋转魔方可以按任何顺序对它们进行重新排列。因此,任何一个角块都可能出现在8个角中的任何一个位置。此外,每个角块也可以旋转,例如,这会使“绿色、白色、红色”对应的角块有以下三种可能的方向:

白色在顶部,绿色在左面,红色在前面。

绿色在顶部,红色在左面,白色在前面。

红色在顶部,白色在左面,绿色在前面。

因此,为精确表示角块的位置和方向,我们得到8×3=24种不同的组合。

至于12个侧面块,由于它们只有两个贴面,因此只能有两个方向。也得到24种组合,只不过是通过12×2=24计算得到的。最后,我们要跟踪20个立方块,8个角块和12个侧边块,每个立方块有24个可能的位置。

独热编码是指当前对象的位置为1且其他位置为0,该编码可以输入神经网络进行处理。因此,本文中状态的最终表示形式为20×24的张量。

考虑到冗余情况,这种表示方式非常接近总状态空间,其可能的组合数量为24²⁰≈4.02×10²⁷。虽然它仍远大于魔方的状态空间,但是这种方式要比比对每个贴面的所有颜色进行编码要好得多。冗余得原因是魔方旋身得属性,如不可能只旋转一个角块或是一个侧边块,每次旋转总是会转一个面。

细心的读者可能会注意到,这样的魔方状态的张量表示有一个重大缺点:内存效率低下。实际上,如果将状态表示为20×24的浮点张量,我们浪费了4×20×24=1920字节的内存,考虑到在训练过程中需要表示数千种状态,这会导致数百万字节内存的损耗。为了克服这个问题,在本文的实现中,我使用两种表示形式:一种是张量,用做神经网络输入;另一种是更紧凑的表示形式,以便更长久地存储不同的状态。我们将这种紧凑状态保存为一系列列表,根据角块和侧边面的排列及其方向进行编码。这种表示方式不仅具有更高的内存效率(160字节)而且使魔方的转换也更加方便。

训练过程

现在我们已经知道了三阶魔方的状态是如何以20×24张量编码的,下面我会介绍本文使用的神经网络结构及其训练方法。

神经网络结构

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图2)

该神经网络将魔方状态的20×24张量表示作为输入,并产生两个输出:

策略。由12个数字组成,表示行动的概率分布。

值。使用一个标量表示对状态的评估,具体含义见下文。

在输入和输出之间,神经网络由若干ELU激活函数的全连接层。在我的代码实现中,网络结构与此处并无差异,详见此处。

训练

可以看到,网络非常简单:策略告诉我们对当前状态进行何种转换,值用于评价状态的好坏程度。那么,最大的问题就是:如何训练网络?

论文提出的训练方法是“ Auto-Didactic Iterations”简称“ ADI”,该方法也简洁明了。从目标状态(复原的魔方)开始,执行一些预定义的长度为N的随机变换序列(文中给出了N个状态的序列)对序列中的每个状态,一次执行以下过程:

将所有可能的变换(总共12个)应用于状态s。

将这12个状态传递给当前的神经网络,以输出值。这样就得到s的12个子状态的值。

根据vᵢ = maxₐvsᵢ,a+RAsᵢ,a计算状态的目标值,其中As, a是对s执行动作a之后的新状态;如果s是目标状态,则Rs为1,否则为0。

状态s的目标策略使用相同的公式进行计算,不同的是我们选择最大值,即pᵢ = argmaxₐ vsᵢ,a+RAsᵢ,a这仅意味着目标策略只有在最大值的子状态时取值为1,否则为0。

具体过程见下图。生成序列为x₀,x₁…以魔方xᵢ为例进行详细说明,对状态xᵢ,通过上述公式确定策略和值目标。

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图3)

通过该过程,我们可以生成任意数量的训练数据。

模型应用

假设我们已经通过上述过程训练得到模型,那么如何使用模型来复原魔方呢?根据网络结构,我们很容易想到这样的方法(但不幸的是该方法并不可行)

向模型要解决的三阶魔方的当前状态。

根据策略选择最大可能的动作(或从结果分布中采样)

对模型执行该动作。

重复上述过程,知道魔方复原。

看上去这样是可以奏效的,但是在实践中,这样的方法却行不通。主要原因是模型质量不过关。由于状态空间巨大,加上神经网络特性,对于所有输入状态,不可能经过训练使得NN返回准确的最佳动作。也就是说,模型并没有告诉我们明确的求解思路,只是向我们提出值得探索的方向,但这些方向可能使我们更接近解决方案,也有可能会引起误导。因为在训练过程中,不可能处理所有可能状态。要知道,即使使用GPU以每秒处理数十万状态的速度进行训练,对于4.33×10¹⁹的状态空间,也需要经过一个月的训练时间。因此,在训练中我们只取状态空间的一小部分,大约为0.0000005%这就要求我们使用更复杂的方法。

有一种非常适用的方法,即“蒙特卡洛树搜索”简称MCTS。该方法有很多变体,但总体思路很简单,可以与众所周知的蛮力搜索方法如“广度优先搜索BFS”或“深度优先搜索DFS”对比来进行说明。在BFS和DFS中,我们尝试所有可能的动作,并探索通过这些动作获得的所有状态对状态空间进行详尽搜索。可以发现,这种方式是上述过程的另一个极端。

正如上文提到的,MCTS是一类方法,不同方法在具体细节和特征方面有所不同,本文使用的是UCT方法(Upper Confidence bound1 applied to Trees)该方法在树上操作,其中节点是状态,边是动作,将所有状态起来。在多数情况下,整个树是非常巨大的,因此我们不会试图构建整个树,只是构建其中的一小部分。首先,让我们从一棵由单个节点组成的树开始,也就是我们的当前状态。

每执行一步MCTS,都要沿着树探索某些路径,一般可以面对以下两种选择:

当前节点是叶节点。

当前节点在树的中间,并具有子节点。

对于叶节点,通过对状态执行所有可能的动作对其进行“扩展”并检查所有结果状态是否为目标状态(如果找到了魔方复原的目标状态,则搜索完成),将叶节点状态传递给模型,输出值和策略,将其存储备用。

如果当前节点不是叶节点,那么我们能够知道该节点的子节点(可到达状态)并从网络获得值和策略输出。因此,我们需要决定选择哪条路径(换句话说,探索哪种行动最优)这一决定极其重要,甚至称得上是强化学习方法的基石,即“探索-利用问题”一方面,神经网络的策略告诉我们该怎么做,另一方面,对于策略出错的情况,可以通过探索周围的状态来解决。但由于状态空间巨大,不能一直探索,这就要求我们在这两者之间保持平衡,这直接影响着搜索性能和结果。

为解决这个问题,对于每个状态,我们为每个可能的动作(共12个)设置计数器,每次在搜索过程中选择某一动作,相应计数器就会增加。在决定采取特定动作时,可以通过计数器进行判定,即某一动作的执行次数越多,将来选择的可能性就越小。

此外,模型返回的值也用于辅助决策,即从当前状态的值及其子节点状态的值中选择最大值进行跟踪。根据这样的模型,可以从父节点的状态找到最可能的路径。

总而言之,对于非叶节点状态,通过以下公式选择要执行的动作:

其中,N(s,a)是状态s选择动作a的次数,P(s,a)是模型为状态s返回的策略,W(s,a)是模型根据状态s的分支a下所有子节点状态返回的最大值。

重复此过程,直到找到解决方案或时间耗尽。为加快此过程,MCTS通常以并行方式进行,利用多个线程同时执行多个搜索。在这种情况下,可以从A(t)中减去一些额外损失,以防止多个线程探索相同路径。

naïve:得到目标状态后,使用从根状态开始的路径作为复原方案。

BFS方法:得到目标状态后,对MCTS树执行BFS,以找到从根到此状态的最短路径。

论文提到,第二种方法找到的复原方案比第一种方案更短,这并不奇怪,因为MCTS过程的随机性,在第一种复原方案路径中可能引入了无用的循环。

论文结果

论文的结果令人印象深刻。在使用三个GPU并行训练了44小时之后,网络学会了类似甚至超过人工复原魔方的方案。最终,将本文模型DeepCube已与先前介绍的两种求解方法进行了比较,分别是Kociemba two-staged solver 和Korf IDA*。

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图4)

实现细节

好的,现在我们开始介绍代码实现。在本部分中,我将简要介绍代码方案及一些关键设计,但在此之前,我还是要先强调一些事情:

我不是该项目的研究人员,因此这段代码只是想要复现论文的方法。但不幸的是,由于论文没有确切的超参数信息,因此我进行了大量猜测和试验,但实现结果与论文的结果依然存在较大差异。

同时,我试图以通用方式实施所有操作来简化实验。例如,有关魔方状态和转换的详细信息不做详细展示,仅仅通过添加一个新模块来抽象化3x3魔方问题。在我的代码中,分别对2x2魔方和3x3魔方进行实验,但类似这样有固定可预测动作集的、环境完全可见的问题都可以通过这样的方式进行解决。下一节会做详细说明。

综上,我的代码由以下几部分组成:

魔方环境,用于定义观察/状态空间、可能的动作以及网络状态的表示,见libcube / cubes模块。

神经网络,包括要训练的模型、训练样本的生成和循环训练过程。见和。

魔方复原方法, 见和。

其他一些不同组件,例如超参数的配置文件和魔方数据生成文件等。魔方环境

正如前文介绍的,组合优化可不是个小问题,而且种类繁多,即使单就魔方而言,也包含数十种变体,包括2x2x2、3x3x3和4x4x4Rubick魔方,以及Square-1,Pyraminx等。本文介绍的方法不依赖于预定义的领域知识、动作集和状态空间大小,具有较强的适用性。具体而言,求解魔方问题基于以下假设:

环境状态必须是完全可观察的,根据观察结果可以区分不同状态。在魔方问题中,我们可以观察到魔方所有面的状态,因此该问题符合我们的假设。但对于类似牌这样的问题,我们是看不到对手的牌的,本文方法就不再适用了。

动作的数量是离散且有限的。在魔方复原问题中,我们只需执行12中动作,这符合假设。但是对操作空间是“旋转角度α∈【-120°…+ 120°】”这样的非离散动作的问题,就需要不同的处理方法了。

环境的准确建模。换句话说,我们要能够回答以下问题:“对状态s采取行动a会产生什么结果?”如果无法解决这样的问题,ADI和MCTS方法都会失效。这个要求对于实现模型是及其必要的。然而,对于大多数问题,并不存在这样的模型,或者模型的输出非常嘈杂,但在象棋或围棋之类的游戏中,游戏规则即是这样的符合要求的模型。

领域确定性。即对相同状态的相同动作会得到相同的最终状态。不过我觉得,即使采取随机行动也应该会起作用,但也不一定。

为了使我们的方法可以很方便的迁移到非3x3魔方的问题,我将所有具体的环境信息都移到了一个单独模块,并通过抽象接口CubeEnv与其余代码进行(见此处)通过这样的方式,每个环境都有一个名称,指定环境名称即可使用相应的的环境类型。目前,我们定义了两种不同的环境:经典三阶魔方cube3x3和二阶魔方cube2x2。

如果你要使用自己的魔方数据或其他不同的环境,只需要修改该模块,通过接口即可在其它代码中使用你自定义的环境。

训练

模型训练过程见和。为简化实验,同时增强实验的可重复性,在单独的ini文件中设置训练的所有参数,包括:

要使用的环境的名称,我们了cube2x2和cube3x3两个环境。

运行名称,在TensorBoard的名称和目录中显示,并用于保存模型。

ADI的目标值计算方法。本代码两种计算方式:一种是原论文的方法,另一种是我改进的方法。实验表明,我的改进方法收敛更加稳定。

训练参数,包括batch、是否使用CUDA、学习率、LR衰减等。

可以在查看我的实验设置。训练过程中,TensorBoard参数被写入runs文件夹,并将最优模型保存到saves文件。

搜索过程

训练的结果是一个带有网络权重的模型文件。根据模型可以使用MCTS方法复原魔方,具体实现见和模块。

其中,求解器可用于不同模式:

复原一个杂乱魔方。该魔方由一系列由逗号分隔的动作索引打乱,该序列由-p选项传递。例如,-p 1,6,1是依次执行第二个动作、第七个动作、第二个动作来打乱魔方。动作执行是面向特定环境的,通过-e选项传递,在魔方环境模块可以找到带有索引的动作。例如,2x2魔方的动作1,6,1分别表示L,RL变换。

从文本文件(每行代表一个魔方数据)读取排列并进行复原。文件名通过-i选项传递。我在文件夹了几个示例,此外,你还可以使用生成自己的数据集。

在所有情况下,都需要使用-e选项来传递环境名称,并使用-m选项传递模型文件。此外,还有其他参数可以调整MCTS、时间或搜索步长等,在此不做过多赘述。

实验结果

一开始我已经说过,我不是论文的研究人员,因此本工作仅仅是复现论文并进行简单实验。但是,原论文没有相关方法的详细信息,例如超参数,在训练过程中对魔方打乱的步数,收敛性等等。为获取这些信息,我已向论文发送了一封电子,但至今未收到他们的回复。

因此,我进行大量的实验,但实验结果与论文结果仍存在较大差异。首先,原始方法的收敛非常不稳定,即使降低学习率和增atch,训练依然不稳定,值损失呈指数增长,如下图所示。

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图5)

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图6)

经过多次实验,我认为导致这种现象的原因是原始方法中值目标是错误的。

确实如此,在公式vᵢ = maxₐvs, a + RAs, a中,网络返回的值vs,a总是与实际奖励Rs相加,即使对目标状态也是这样。这样,网络返回的实际值可以是-100、10⁶或3.1415。这样大的差异对神经网络极不友好,尤其是MSE值目标。

为此,我做了以下修改,将目标状态值设为0:

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图7)

具体而言,指定参数value_targets_method = zero_goal_value而不是默认的value_targets_method = paper,你可以在ini文件中选择该新的目标函数。

通过这种简单修改,训练过程模型可以更快地收敛稳定状态,见下图。

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图8)

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图9)

甚至称得上是强化学习方法的基石,魔方问题尤其如此(图10)

二阶魔方

原论文中,使用三个Titan XP GPU并行训练了44小时,在这个过程中,模型总计看过约80亿魔方状态。根据这样的叙述,可以得到训练速度约等于每秒查看50000魔方状态。我的实现在单个GTX 1080Ti上进行,其训练速度为15000/秒,与论文差别不大。因此,使用论文的数据,在单个GPU上训练一次大概需要6天时间,这使得实验和超参数调整及其困难。

为解决这个问题,我设置了简单的2x2魔方环境,只需一个小时的训练时间。如果你也想继续复现,可参见repo中的两个ini文件:

cube2x2-paper-d200.ini:使用原论文中的值目标方法。

cube2x2-zero-goal-d200.ini:改进的0值目标计算方法。

在这两种配置中,状态批次均为10k,魔方打乱步骤为200,其他训练参数也相同。

分别进行训练后,生成了两个模型(模型文件)

原论文方法的损失为0.18184。

改进0值方法的损失为0.014547。

接下来对魔方复原过程中的MCTS步骤进行对比。如下图所示,改进的0目标模型通常以更少的步骤复原魔方,也就是说,该模型学到更优的复原策略。

最后,比较不同魔方复原方法的长度。下图绘制了naïve和BFS方案的长度。从图中可以看出,naïve方法的长度要比BFS长约10倍,这表明调整MCTS参数可以改善模型性能。同时还可以发现,“零目标”模型的解决方案比原论文模型更长,其原因可能是前一种方法不存在更长的复原路径。

三阶魔方

3x3魔方的模型训练过程要复杂的多,所以在这里仅进行简单介绍。但即使只是简单的实验,也表明0值目标函数可以极大地提高训练稳定性和模型质量。另外,三阶魔方训练一次大约需要20个小时,想要进行大量实验需要花费很多时间和耐心。

下图是论文方法与改进的零目标值方法的比较。

下图所示为找到的最佳解决方案的长度。图示表明两点:第一,在10-15干扰深度范围内,“零目标”方法求解长度大于论文的,这意味着模型虽然没有找到生成数据的干扰序列,但发现了更长其他解决方法;第二,对于12-18深度范围,原论文方法找到比干扰序列更短的解决方案,可能的原因是生成了简并序列。

进一步的改进和实验

针对上述研究,有许多其他方法可提升模型性能,改进实验结果。比如:

更详细的输入和更复杂的神经网络。由于魔方问题非常复杂,仅仅通过简单的前馈神经网络并不能获得最佳模型,考虑卷积网络可能会提升模型的学习能力。

训练期间的振荡和不稳定性在RL问题中十分常见,这可能是步间相关性导致的。通常的解决方法是,在使用策略网络学习引导值时引入目标网络。

引入临时缓冲区可提高训练速度。

实验表明,样本加权(与扰乱深度成反比)有助于获得更好的策略,该策略知道如何解决扰乱魔方问题,但这也可能使对更深状态的学习过程变慢。为此,可以使用自适应权重,以减少其在后续训练阶段的影响。

在训练过程中使用熵损失来正则化学习策略。

2x2魔方的训练模型没有考虑到魔方问题中存在的不动中间块,因此整个二阶魔方都可以旋转。由于二阶魔方的状态空间很小,所以无需考虑冗余的相同状态,但对于4x4魔方来说,去冗余至关重要。

多次实验寻找更好的训练参数和MCTS参数。

本文相关词条概念解析:

魔方

魔方(英语:Rubik'sCube,原名MagicCube),在台湾称为魔术方块,在香港称为扭计骰,是匈牙利建筑学教授和雕塑家厄尔诺·鲁比克(ErnőRubik),于1974年发明的机械益智玩具。其中包含6个处于面最中心无法移动的块,12个位于棱上的块和8个角块。六个面每个有一种颜色,一般来说,标准的魔方的颜色应该是蓝、白、红、绿、黄和橙色,其中蓝绿相对、白黄相对、红橙相对。自发明来,魔方在全世界已经售出了约1亿多只。魔方与中国的华容道、法国的独立钻石棋同被称谓智力游戏界的三大不可思议。

网友评论