2020最佳AI新基建年度榜
您正在使用IE低版浏览器,为了您的雷锋网账号安全和更好的产品体验,强烈建议使用更快更安全的浏览器
此为临时链接,仅用于文章预览,将在时失效
人工智能开发者 正文
发私信给雷锋字幕组
发送

0

强化学习算法DeepCube,机器自行解决复杂魔方问题

本文作者:雷锋字幕组 2020-10-30 16:35
导语:RL在各个领域均在迅速发展,很多有趣的主题值得探讨。

译者:AI研习社(季一帆

双语原文链接:https://www.yanxishe.com/TextTranslation/2719


前瞻

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

引言

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

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

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

实际上,基于MDP的RL可以用于各种不同的领域,计算机游戏只是关于复杂决策的一个简易且关注度高的领域。

在本文中,我将详细介绍将RL应用于组合优化领域的最新研究工作。本文对UCI(加利福尼亚大学欧文分校)的研究人员发表的论文“Solving the Rubik’s Cube Without Human Knowledge”进行解读。除了论文解读之外,我还使用PyTorch复现了论文,通过训练模型和流程解读实验,并对论文方法进行改进。

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

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步移动,但某个状态可能不需要任何移动(已复原状态)。

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

魔方复原的方法

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

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

  2. 使用蛮力搜索以及人工定义的启发式搜索,使搜索指向最有可能的方向。典型的如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张量。接下来以下图为例,对这种表示方式进行说明。

强化学习算法DeepCube,机器自行解决复杂魔方问题

将魔方中需要关注的面标为白色

上图中,我们用白色标记了我们需要关注的魔方模块,其余部分(蓝色)是冗余的,不需过多关注。我们都知道,3x3魔方由三种类型的模块组成:8个三色的角块,12个两色的侧边块和6个单色的中心块。

虽然不太明显,但实际上根本不需要过多关注中心块,因为它们不能更改其相对位置,只能整体旋转。因此,对于中心块,我们只需就其位置达成一致就可以。例如,在我的实现中,白色面总是在顶部,前面是红色,左边是绿色,依此类推。这使得数据集状态的部分固定,意味着将魔方上所有可能的旋转被视为同一状态。

由于无需关注中心块,所以在上图中所有中心块都是蓝色。那其余蓝色是怎么回事呢?这是因为每种特殊的立方模块(角块或侧变块)的颜色组合都是固定的。例如,根据上述对魔方前后左右各方向的定义(顶部为白色,红色为正面等等),左上角块一定是绿色、白色和红色,其他立体块不会有这三种颜色的组合。 侧边块也是如此。

因此,要找到某个特定模块的位置,我们只需要知道其某个面的位置即可。一般来说,你可以在侧边块或角块选择一个面进行跟踪关注,但是一旦选定,就要坚持下去。如上图所示,我们选择在顶部跟踪八个立方块贴面,从底部跟踪八个贴面,以及四个侧边块贴面,两个在正面,两个在背面。这样,我们需要跟踪关注的总计有20个贴面。

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

  • 白色在顶部,绿色在左面,红色在前面;

  • 绿色在顶部,红色在左面,白色在前面;

  • 红色在顶部,白色在左面,绿色在前面;

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

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

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

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

好了,数学知识就介绍这么多,如果你想了解更多,推荐Alexander Frey和David Singmaster撰写的著作“Handbook of Cubic Math”。

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

更多细节参见该模块,紧凑状态见函数namedtuple,神经网络张量表示见函数encode_inplace

训练过程

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

神经网络结构

下图是神经网络结构(取自原论文):

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

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

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

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

训练

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

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

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

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

  • 根据vᵢ = maxₐ(v(sᵢ,a)+R(A(sᵢ,a)))计算状态的目标值,其中A(s, a)是对s执行动作a之后的新状态;如果s是目标状态,则R(s)为1,否则为0;

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

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

模型应用

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

  • 向模型提供要解决的三阶魔方的当前状态;

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

  • 对模型执行该动作;

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

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

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

MCTS在这两种极端之间进行折衷:我们想要执行搜索,并且存在一些值得关注的信息,但是,某些情况下信息可能是不可靠的噪声或错误,有时信息也可能提供正确的方向,从而加快搜索过程。

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

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

  • 当前节点是叶节点;

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

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

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

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

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

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

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

为使用MCTS树得到复原方案,论文作者提出两种方法:

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

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

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

论文结果

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

为验证本文方法的效率,论文使用640个随机打乱的魔方对不同方法分别进行测试,并设置最大求解步骤为1000步,最大求解时间为1小时,实现发现DeepCube和Kociemba方法均能在限制步骤和时间内复原魔方。 具体而言,Kociemba求解速度非常快,其中值仅为一秒钟,但是由于依赖人工定义规则,其求解并不总是最短的。DeepCube方法花费了更多的时间,中值约为10分钟,但在55%的情况,该方法会比Kociemba得到更好的复原方案,即更少的步骤。从我个人的角度来看,55%虽然不足以说NN明显更好,但至少证明该方法还不错。下图(摘自论文)显示了所有求解方法的复原步数分布。可以看到,由于复原时间较长,在1000步魔方复原测试中没有比较Korf求解方法,但为了将DeepCube与Korf求解方法的性能进行比较,论文进一步设计了更容易的15步魔方复原测试集。

强化学习算法DeepCube,机器自行解决复杂魔方问题

实现细节

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

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

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

  • 相比代码性能,我更关注代码的可读性与简洁性,当然,对于不引入过多复杂性与成本消耗就能提高模型性能的操作,我在代码中还是保留了它们。例如,仅通过分割魔方数据集和正向网络传递,就可以将训练过程加快5倍。但是,如果需要将大多数内容重构为多GPU和多线程模式,我为简单起见就没有这样做。典型的就是MCTS进程,通常采用多线程代码实现,加快模型速度,但这就需要处理进程之间的同步问题。我没考虑那么多,只是以串行方式进行MCTS,仅对批量搜索进行了简单优化。

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

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

  2. 神经网络,包括要训练的模型、训练样本的生成和循环训练过程。见the training toollibcube / model.py模块

  3. 魔方复原方法, 见the solver toollibcube/mcts.py

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

魔方环境

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

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

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

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

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

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

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

训练

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

  • 要使用的环境的名称,我们提供了cube2x2和cube3x3两个环境;

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

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

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

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

搜索过程

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

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

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

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

  3. 生成更多步骤的打乱魔方并进行复原。

  4. 执行复杂的系列打乱测试,并对其复原,然后将结果写入csv文件。通过-o选项可以启用此模式,这可用于评估模型的质量,但同时也需要花费更多的时间。一旦选择该选项,就会生成测试结果图。

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

实验结果

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

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

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

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

强化学习算法DeepCube,机器自行解决复杂魔方问题

强化学习算法DeepCube,机器自行解决复杂魔方问题

二阶魔方

原论文中,使用三个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。

实验表明,模型损失越小,成功率越高,可用于复原更多打乱步骤的魔方。两种模型的实验结果如图所示。

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

强化学习算法DeepCube,机器自行解决复杂魔方问题


三阶魔方

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

正是由于上述原因,我的实验结果不如论文所示结果,我得到的最佳模型仅解决12-15步的乱序魔方复原问题,对于更复杂的问题则无能为力。如果你想获得更好的效果,可能使用更多CPU内核+并行MCTS来提升模型性能。为了获得数据,我将搜索过程限制在10分钟内,并对每个乱序干扰生成五个随机干扰。

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

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

强化学习算法DeepCube,机器自行解决复杂魔方问题

进一步的改进和实验

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

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

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

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

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

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

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

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

感谢你的阅读,期待你的评论!本文的PDF文件可从此处下载。


AI研习社是AI学术青年和AI开发者技术交流的在线社区。我们与高校、学术机构和产业界合作,通过提供学习、实战和求职服务,为AI学术青年和开发者的交流互助和职业发展打造一站式平台,致力成为中国最大的科技创新人才聚集地。

如果,你也是位热爱分享的AI爱好者。欢迎与译站一起,学习新知,分享成长。

强化学习算法DeepCube,机器自行解决复杂魔方问题

雷锋网版权文章,未经授权禁止转载。详情见转载须知

强化学习算法DeepCube,机器自行解决复杂魔方问题

分享:
相关文章

文章点评:

表情
最新文章
请填写申请人资料
姓名
电话
邮箱
微信号
作品链接
个人简介
为了您的账户安全,请验证邮箱
您的邮箱还未验证,完成可获20积分哟!
请验证您的邮箱
立即验证
完善账号信息
您的账号已经绑定,现在您可以设置密码以方便用邮箱登录
立即设置 以后再说