TetrisBattleAI: Make Tetris Great Again!
還記得幾年前在Facebook風靡一時的Tetris Battle嗎?
Tetris Battle是一個多人對打俄羅斯方塊的遊戲，透過連續的消行(combo)來擊敗對手，相當吃技術和反應，想當年練留1、留2、留4…應該是不少人的童年回憶(?)，我也是沉迷了好一陣子XD
這次就透過AI課程的 final project，就來做可以玩Tetris Battle的AI！！
Tetris Battle AI
當初選擇這個題目，其實是因為覺得它好像很好做，稍微搜尋一下就知道之前已經有很多人做過單人版的AI了，甚至有電機系的學長用rule-based的方法做Tetris Battle AI的，直接接到Facebook屌虐一波(可惜沒release code)，感覺我們應該可以用DQN輕鬆完成。
原本的目標是放在learning-based的方法，希望能train一個model打敗現在所有的AI，只不過後來發現：
- 沒有Python Tetris Battle的環境(只有找到C的和1-player的)，最後只好自己刻…
- Baseline在combo的表現其實不好
- Tetris以Renforcement Learning (RL)來說reward非常sparse，不可能用隨機的方式消到任何一行，要combo就更sparse，極度難train
- RL是個大坑….
所以最後我們只有做到打敗baseline，combo的表現沒有特別好，learning-based的方法應該還有發展空間。
Methods
我們試了很多方法：
- Fixed-policy (baseline)
- Genetic Algorithms (GA)
- DQN
- Policy Gradient
- Actor-critic (AC)
其中baseline跟GA都是我們訂好評估action好壞的標準(落下方塊之後的總高度/空洞數/消行數…)，agent每一步都執行分數最高的action，然後玩很多局，學這些標準之間的權重
DQN/Policy Gradient/Actor-critic則都是RL的方法，只給獎勵，讓agent自己去學規則，細節可以參考https://zhuanlan.zhihu.com/p/25239682、https://flyyufelix.github.io/2017/10/12/dqn-vs-pg.html
RL的方法在Tetris其實非常難train，我們把每個action直接簡化成落下到最後的位置，train出來的表現還是不如預期，DQN/policy gradient更是直接失敗。最後多加上hold的選擇，才train出1-player不會死的model~
Results
這是我們的GA對baseline，可以看出雖然動作很快，但其實效率都不是很好(line sent/cleared大概只有50%)，還有很多改進的地方
AC對baseline則會把block持續維持在很低的位置，combo的效率更差，但是比較不容易被KO
上面這兩個model大概都只是稍微會玩的程度而已，跟專業玩家還差很多，未來還有很大的發展空間
結語
看電腦自己玩Tetris滿好玩的，但是要實做rule-based或train RL方法都有相當的難度。另外，很想看看加上bomb lines會變成什麼樣子，希望哪天有人能繼續做下去XD
大家也可以自己載來玩玩看～ Let’s make Tetris great again!
