[心得] Learning to play Tetris

[panruru1224 (booooooored)]

[關鍵字]:

Tetris, Reinforcement Learning, Monte Carlo Tree Search,
Temporal Difference Learning

[重點摘要]:

利用MCTS和TD實作自我學習的俄羅斯方塊機器人


1.影片 & GitHub

https://www.youtube.com/watch?v=EALo2GfZuYU

https://github.com/hrpan/tetris_mcts



2.簡介

故事起源於第一次看到 DeepMind 的 Atari 影片

https://www.youtube.com/watch?v=V1eYniJ0Rnk

當時深深覺得這東西實在太神奇了竟然可以自我學習而且達到超人類水準

覺得如果可以用到俄羅斯方塊應該蠻有趣的 就開始在閒暇時間讀相關的文章

起初以為用 DQN 或是 policy gradient 就可以輕鬆解決的問題

沒想到不管訓練多久都消不了幾條就放著生灰塵了

直到後來看到 AlphaGo 以後才又燃起了一線希望

也成功讓我的機器人成功消了超過1000條



3.關於俄羅斯方塊

相信大家應該都玩過了 對遊戲規則就不多做說明

一般人大概都不會覺得俄羅斯方塊是一款很難的遊戲

起初我也這樣想 後來仔細想想俄羅斯方塊其實需要很長遠的計畫能力

對一個完全沒有先備知識的電腦來說 每個動作都是等價的

假設電腦要消掉一條 (先假設沒有 hard drop)

他必須要往前計畫約50步才有辦法做到 (假設是 20 X 10 的版面)

這對傳統的 Q-Learning 來說難度是相當高的

因為 Q-Learning 本身對於 credit assignment 是指數遞減

也就是說你如果在第50步得到一分的話 第一步所獲得的分數只有 r^49 (0 < r < 1)

幾乎跟雜訊沒甚麼兩樣



之所以檯面上的俄羅斯方塊機器人可以有近人類水準的操作是因為他們大多用了

一些 hard-code 的額外獎勵 例: 列的高度 台面有幾個洞 平滑程度等等

這些額外獎勵可以大量縮短獎勵分配的長度 (從每消一條變成每放一塊獎勵一次)

讓這些訊號變得更顯著 不過這些獎勵只能用在特定遊戲中

一旦規則改變就必須在重新寫過 而且在一些困難的遊戲(例如圍棋)中

並不是所有人都有能力去寫出這種獎勵 所以讓機器人可以自我學習是非常重要的

詳細要如何用MCTS來解決這個問題就請看GitHub吧



4.心得

從開始解決這個問題開始到現在也過了快兩年

剛開始沒辦法消超過10條到現在可以消超過1000條看起來真的是蠻過癮的

(而且看起來還沒收斂應該可以再更高 不過因為一輪要跑太久(>10hrs)所以放棄了)

過程中也學到了不少python的技巧 可以算是蠻有收穫的吧

希望這篇文章可以啟發更多對 reinforcement learning 有興趣的人

(雖然我知道這文章沒啥組織性又打的很雜)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.67.208
※ 文章網址: https://www.ptt.cc/bbs/DataScience/M.1545662371.A.E27.html
推 larsonloreal: 先推再看
推 TreeMan: really cool!
推 y956403: 大推實作
推 st1009: 推推
推 tritonight: 推
→ panruru1224: 文章也發在reddit上 有些蠻有趣的討論可以看看
→ panruru1224: https://tinyurl.com/y8ne25fu
推 cutekid: 大推，好厲害(Y)
推 woogee: 超強....
推 illegalplan: 剛好期末在做這個 偷偷跟原po講 DQN跟PG都起不來
→ illegalplan: 但是actor-critic可以喔
→ panruru1224: 蠻好奇AC可以到多少 有數據嗎?
→ illegalplan: AC平均只到60行左右 而且action是可能的落地組合
→ panruru1224: 蠻有趣的 不過我猜action的設計應該影響很大
→ panruru1224: 用落地組合應該可以讓planning簡化很多
→ sizzle0121: 加上prioritized experience replay試試?
推 a78998042a: 好強 XDD
推 gaexp233008: 推推
推 alen84204: 從人類的角度來看感覺每次好不容易有空格出來 結果機
→ alen84204: 器又直接把他補上XDD 另外是不是當前方塊如過在最低平
→ alen84204: 面上無法填補時 機器會自動判對放在最高的位置上阿
推 uukoQAQ: 推推