適用於小精靈的深度強化式學習之研究

A Study of Deep Reinforcement Learning for Ms. Pac-Man

高黃江

深度強化式學習之 ； 小精靈 ； 深度類神經網路 ； Deep Reinforcement Learning ； Ms. Pac-Man ； Deep Neural Network

交通大學電機資訊國際學位學程學位論文

2017年

碩士

吳毅成

英文

深度類神經網路（Deep Neural Network）是２００６年開始發展的一種機器學習技術。近年來，深度類神經網路被廣泛利用在資訊工程領域的各種應用上，並獲得出色的成績。 本論文將深度類神經網路應用在遊玩Ms. Pac-Man的遊戲上。深度加強學習（Deep Reinforcement Learning）是一種結合深度類神經網路與Q學習方法（Q-learning）的技術，也是加強學習的一個變體。此研究將Ms. Pac-Man遊戲中抽象化後的資訊當成類神經網路的輸入，使用其網路的人工智慧程式，可以在超過90%的嘗試中通過前兩個關卡。在最短通關時間與最佳通關分數兩項數據上，深度加強學習方法與之前的蒙地卡羅搜尋樹（Monte-Carlo Tree Search）方法相比，有顯著的進步。

Deep Neural Network (DNN), a branch of machine learning was introduced in 2006, have had remarkable success in of computer science. DNN can be applied to solving a wide range of problems. Deep Reinforcement Learning (DRL) is a combination of DNN and Q-learning, a form of Reinforcement Learning technique. This thesis applies DRL to create a program playing Ms. Pac-Man game. This study uses the abstracted information of Ms. Pac-Man game as the input of the network. Our program can pass the first level at a rate of 99.10%, the second at 91.20%, and the third at 82.60%. The performance of DRL method is significantly better than Monte Carlo Tree Search (MCTS) in terms of both time and score.

1. [1] Piers R. Williams, Diego Perez-Liebana, and Simon M. Lucas, “Ms. Pac-Man Versus Ghost Team CIG 2016 Competition”, IEEE Transactions on Computational Intelligence and AI in Games, pages: 420-427, Sept. 2016.
   連結：
2. [2] T. Pepels, M. H. M. Winands, and M. Lanctot, "Real-time Monte Carlo Tree search in Ms Pac-Man", IEEE Transactions on Computational Intelligence and AI in Games, vol. 6, no. 3, pp. 245–257, Sep. 2014.
   連結：
3. [3] V. Mnih, K. Kavukcuoglu, and D. Silver, "Human-level control through deep reinforcement learning", Nature, vol. 518, no. 7540, pp. 529–533, Feb. 2015.
   連結：
4. [4] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, “Playing Atari with Deep Reinforcement Learning”, arXiv:1312.5602v1 [cs.LG], Dec. 2013.
   連結：
5. [7] Simon M. Lucas, "Ms Pac-Man versus ghost-team competition", Computational Intelligence and Games, Pages: 1 - 1 ,Sept. 2009.
   連結：
6. [9] L. Bom, R. Henken, M. Wiering, "Reinforcement Learning to train Ms. Pac-Man using higher-order action-relative inputs”, Adaptive Dynamic Programming And Reinforcement Learning (ADPRL), pages: 156 – 163, Apr. 2013.
   連結：
7. [5] Google, "TensorFlow," TensorFlow, 2016. [Online]. Available: https://www.tensorflow.org. Accessed: 2016.
8. [6] A. Karpathy, "Deep reinforcement learning: Pong from Pixels," 2016. [Online]. Available: http://karpathy.github.io/2016/05/31/rl/. Accessed: 2016.
9. [8] P. Rohlfshagen, Simon M. Lucas, "Ms Pac-Man versus ghost team CEC 2011 competition", In Evolutionary Computation (CEC), 2011 IEEE Congress on, pages 70–77. IEEE, Jun. 2011.