文章作者：張小凡
編輯整理：Hoh Xil
内容來源：作者授權釋出
出品平台：DataFunTalk
注：歡迎轉載，轉載請留言。
導讀：強化學習也火了好久，最近才有空來充充電。老實說，最開始強化學習的知識點還挺多的，看了好久也沒太弄清楚幾個算法的關系，是以本着實踐出真知的想法，找個案例做下。2048小遊戲感覺本身複雜度還可以，又是個 model-base 的模型，檢查起來比較友善，并且可以簡化到2x2，3x3，是以感覺是個很不錯的 demo 案例。順便學習下傳統的 DP 那一套東西，是以也做了一些很簡單的實驗來鞏固下知識。本文還是會參雜很多個人想法，很多想法來自一些實驗測試結果。關于理論的東西網上講的已經很多了。因為查閱資料的時候，看到很多人在嘗試 DQN on 2048 的時候遇到了不少問題，是以和大家進行下分享。
▌最終效果
- 大機率能玩出2048
- 最高可以玩 3w 多分
- 均值 1w 多分
- 仍有上升空間 ( 可能有啥 bug，跑久了容易挂，就沒繼續跑了 )
- 網上能查到的比較厲害的差不多到4096 (AI)，比例也比較小。
▌實驗過程
1. 随機測試：
定義：
- 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+
這裡大概評估下随機水準，友善後面評估。
2. 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
1. 值疊代：
值疊代
2. 政策疊代：
政策疊代
- 值疊代、政策疊代、蒙特卡洛、Q-learning：2*2上可以快速收斂。
- Q-learning 感覺會稍微有點波動。
3. DQN 在2x2
當用值疊代、政策疊代得到了理論最優值之後，又用 DQN 測試了一把。發現 DQN 結果比最優值總是差點，這就說明網絡和學習政策确實有點問題，但同時側面又反映了，2x2的時候能很接近最優政策，4x4差的比較遠，那麼很大部分問題可能來自參數化和探索方面。（空間變大會涉及到的點）
總結幾個提升慢原因：
- 沒有找到足夠高分的點訓練
- e-greedy
- 遊戲本身随機性
- 找到高分點後，沒有訓練到
- 被訓練資料淹沒-memory_size
- lr 和高分沒有比對上，太小了
- reward 設計不合理
4. 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 圖
5. DDQN/DQN2015
一般講 DQN 的三個優化：DDQN/Prioritized Experience Replay/dueling-DQN
- DDQN/DQN2015 的兩個方案在2048的案例中都沒有啥效果，過估計仍然很嚴重。
- 後面兩個沒有提到對過估計的問題，是以沒有嘗試。
- dueling-dqn 在别人的一篇文章中有測試，dueling-dqn 比 ddqn 的上限要高，早期好像差别也不大。
到這裡，其實有點調不下去了，後來在網上翻到了一個代碼。能跑出2048，天呐，發現寶了，做了很多測試，發現我和他的方案上差異還是蠻大的，然後就開始了一點點比較的階段。
6. 複現 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
我在他的方案上做了一系列實驗：
實驗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 了 )。
1. 需要監控的點
- loss:DQN 過估計嚴重，需要密切關注 loss 情況
- max-label:如果沒有出現過大值，看看探索過程是不是有問題。後期探索不能太大。
- e-greedy:關注探索程度
- episode:關注大緻進度和速度
- lr:這個和loss配合着看
-
評估名額:avg/max score
RL的任務感覺需要監控的内容更多，不光是監督學習的部分，探索的部分也很重要。
2. 訓練情況
訓練出2048，要2個小時左右。大概 2w episode 這個樣子。
▌小結
到此，2048的探索可能就先告一段落，雖然很多事情并沒有研究太明白。但是對于整個算法有了個基礎的認識。并對算法中可能存在的優化點有了一些了解。後續可能會嘗試下政策梯度那一趴的東西。
▌相關資料
1. mit 一篇 dqn on 2048 的文章：https://cs.uwaterloo.ca/~mli/zalevine-dqn-2048.pdf2. 可參考的 github：https://github.com/navjindervirdee/2048-deep-reinforcement-learning3. 我的github：https://github.com/Continue7777/ReinforcementLearning_2048
對本文感興趣的同學，歡迎點選文末閱讀原文與作者交流。
DataFun：