[關鍵字]: 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://webptt.com/m.aspx?n=bbs/DataScience/M.1545662371.A.E27.html