美文网首页
讲人话系列——DQN初探之2048

讲人话系列——DQN初探之2048

作者: 张凡宇 | 来源:发表于2019-12-09 19:57 被阅读0次

    概述

    强化学习也火了好久,最近才有空来充充电。老实说,最开始强化学习的知识点还挺多的,看了好久也没太弄清楚几个算法的关系,所以本着实践出真知的想法,找个案例做下。2048小游戏感觉本身复杂度还可以,又是个model-base的模型,检查起来比较方便,并且可以简化到2x2,3x3,所以感觉是个很不错的demo案例。顺便学习下传统的DP那一套东西,所以也做了一些很简单的实验来巩固下知识。本文还是会参杂很多个人想法,很多想法来自一些实验测试结果。关于理论的东西网上讲的已经很多了。因为查阅资料的时候,看到很多人在尝试DQN on 2048的时候遇到了不少问题,所以和大家进行下分享。

    最终效果

    • 大概率能玩出2048
    • 最高可以玩3w多分
    • 均值1w多分
    • 仍有上升空间(可能有啥bug,跑久了容易挂,就没继续跑了)
    • 网上能查到的比较厉害的差不多到4096(AI),比例也比较小。

    实验过程

    随机测试:

    定义:

    • max_tile:4x4格子中最大方块数
    • max_score:n局下来最大总分数(n in 50-100)
    • avg_score:n局平均分数(n in 50-100)

    4x4的游戏中随机算法评测:

    • max_tile:256
    • avg_score:700+
    • max_score:2k+

    这里大概评估下随机水平,方便后面评估。

    DQN初探:

    按照自己的想法构建了一个最初版本的DQN

    • net:4*4直接reshape(-1,16) - dense_layer(128) - dense_layer_(4)
    • memory_sie:100w
    • lr:0.001(固定)
    • reward:每次运行后得分
    • gamma(延迟衰减):1
    • e-greedy:指数衰减,最小0.1

    结果:网络到max_score:3000之后,好像跑不动了。这里一脸蒙,不知道有啥可以改的。于是发现这个事情并不简单,就想简化问题到2x2看看能不能有啥收货,顺便补习下传统的一些RL算法,验证下最优原理。

    值迭代、策略迭代、蒙特卡洛、Q-learning

    值迭代:


    值迭代

    策略迭代:


    策略迭代
    • 值迭代、策略迭代、蒙特卡洛、Q-learning:2*2上可以快速收敛。
    • Q-learning感觉会稍微有点波动。

    DQN 在2x2

    当用值迭代、策略迭代得到了理论最优值之后,又用DQN测试了一把。发现DQN结果比最优值总是差点,这就说明网络和学习策略确实有点问题,但同时侧面又反映了,2x2的时候能很接近最优策略,4x4差的比较远,那么很大部分问题可能来自参数化和探索方面。(空间变大会设计到的点)

    总结几个提升慢原因:

    • 没有找到足够高分的点训练
      • e-greedy
      • 游戏本身随机性
    • 找到高分点后,没有训练到
      • 被训练数据淹没-memory_size
      • lr和高分没有匹配上,太小了
    • reward设计不合理

    DQN-2013 + 网络层迭代、bug修复

    从2x2的地方看出,参数化有问题,那么第一个想法就是优化下网络,dnn还是太粗暴了,还是得cnn,这里就有几个方案:

    • 原始值 + cnn
    • one-hot + cnn
    • emb + cnn
    • cur + next-step + cnn(github上看到别人的做法,借鉴的alphaGoZero)

    新版本改进:修复了探索的bug,reward做了log变化,网络换成了emb+cnn,新结果如下:

    • max_score:6000
    • max_tile:1024

    但是问题也暴露的很明显:

    • loss出现了非常夸张的发散问题,预测值过估计严重。如下图,大概意思就是loss变得巨大无比之后,效果就开始变差,loss也下来了。
      • loss图

    DDQN/DQN2015

    一般讲DQN的三个优化:DDQN/Prioritized Experience Replay/dueling-DQN

    • DDQN/DQN2015的两个方案在2048的案例中都没有啥效果,过估计仍然很严重。
    • 后面两个没有提到对过估计的问题,所以没有尝试。
    • dueling-dqn在别人的一篇文章中有测试,dueling-dqn比ddqn的上限要高,早期好像差别也不大。

    到这里,其实有点调不下去了,后来在网上翻到了一个代码。能跑出2048,天呐,发现宝了,做了很多测试,发现我和他的方案上差异还是蛮大的,然后就开始了一点点比较的阶段。

    复现Github方案

    先提出别人和我方案的差异点:

    • lr别人用了离散衰减,start-lr = 0.0005
    • reward:用了max_tile增量+合并单元数
    • memory_size:6000!!!
    • 更新方案:dqn2013,没用target
    • gamma:0.9
    • egreedy:0.9 ,10000步后快速收敛到0
    • net:一个比较定制化的one-hot + cnn


      image.png

    我在他的方案上做了一系列实验:

    实验1:把e-greedy改成最小0.1
    实验结果:

    • max_score到1w+后开始增长变得很慢,很久都没有提升。说明该任务本身具有比较强的前后相关性和随机性,最终还保持较高的探索难以发现最佳值。

    实验2:用数值网络代替one-hot+cnn
    实验结果:

    • 提升没有之前快了,这个实验没跑完就挂了,但是raw的效果不如cnn。说明网络结构影响比较大

    实验3:reward改成每步获取score

    • 监控几乎和之前差不多,说明两个reward设计都可行。

    实验4:在原基础上只用max_tile来作为回报,拿掉合并分数。

    • 无法达到2048,在1024前就好像不涨了。说明reward也不能设计的太随意,要保持和训练方案比较高的协调性,只用max的话,reward会比较稀疏。

    在做完上述一系列实验后,我大致有了个数,然后对自己的实验进行了优化。
    优化方案:

    • lr设计成离散衰减
    • gamma:1 (没变)
    • reward:score (没变)
    • 更新方案:dqn-2013(没变)
    • memory_size:6000
    • egreedy:0.9指数衰减,10000步后快速收敛到0
    • net:emb+普通2*2的cnn2层 (不变)
      结果:
    • max_score:3.4w
    • max_tile:2048
    • avg_score:10000
    • 截张图看下:
      • 2048

    之后测试了下ddqn,发现收敛比较。本身把memory_size设置小了之后,过估计就没有这么严重了。这里简单分下,过估计本身在Q-learning中就存在,回访池过大之后,训练越多,过估计越严重,在没有很好的高分数据前,就给搞过估计了,所以后面就不好迭代了。反而用小点的话,过估计不严重,在高分出现后也不会淹没在数据中,对于这个任务可能更好一点。很多结论可能都与这种需要长期规划的性质相关。

    蒙特卡洛树搜索探索

    出于对alphaGo的膜拜,我也想过,dqn很多时候不好训练,就是很难拿到高分训练数据,能不能和alphaGo一样,用个mcts,就简单做了下。结果如下:

    • 纯蒙特卡洛树搜索的方案:每步模拟100-200,可以轻松到达2048,均值2w+(这里测试数据不多,跑的很慢,所以想用mcts来训练dqn的方案也被pass了)。

    需要监控的点

    • loss:DQN过估计严重,需要密切关注loss情况
    • max-label:如果没有出现过大值,看看探索过程是不是有问题。后期探索不能太大。
    • e-greedy:关注探索程度
    • episode:关注大致进度和速度
    • lr:这个和loss配合着看
    • 评估指标:avg/max score
      RL的任务感觉需要监控的内容更多,不光是监督学习的部分,探索的部分也很重要。

    训练情况

    • 训练出2048,要2个小时左右。大概2w episode这个样子。

    小结

    到此,2048的探索可能就先告一段落,虽然很多事情并没有研究太明白。但是对于整个算法有了个基础的认识。并对算法中可能存在的优化点有了一些了解。后续可能会尝试下策略梯度那一趴的东西。

    资料

    相关文章

      网友评论

          本文标题:讲人话系列——DQN初探之2048

          本文链接:https://www.haomeiwen.com/subject/xldigctx.html