臺灣博碩士論文加值系統

現今，電玩遊戲已經是年青人之間最受歡迎的休閒娛樂活動之一，而隨著電腦計算及3D繪圖能力的快速進展，人工智慧(Artificial Intelligence, AI)在電腦遊戲中所扮演的角色已經日漸重要，已經成為了遊戲中必備的要素。現在遊戲中所使用的AI其質量與複雜度已有漸漸增加的趨勢，對大多數的電玩遊戲而言Intelligent NPC (Non-Player Character)必須要具有可玩性。因此如何增強遊戲中角色的智慧已經變成一個重要的研究議題。
本研究提出一個NPC代理人的增強式學習的合作架構，在此架構下多個代理人之間透過一個共用狀態與整體獎勵的機制來學習。經由不斷的學習訓練將可以發展出一套互相合作的行動策略，並能在虛擬環境中移動到指定地點並達成任務。從我們的實驗結果中可以看出一些有用的成果。甚至在經過多種不同的虛擬場景訓練之後，代理人可以在不同的虛擬場景之中透過本研究提出的學習機制來選擇出合適的行動策略達成目標。

Today, video games are the most popular entertainment for young people. With rapidly developed computer technology, the quality and complexity of AI (Artificial In-telligence) used in computer games are gradually increasing. Today, AI has become a vital element of computer games. Intelligent NPC (Non-Player Character) which can act as playmates is becoming the essential element for most video games. How to enhance the intelligence of game characters has become an important research topic.
This study proposes a cooperative reinforcement learning structure of NPC agents that share the common global states and the overall reward mechanism. Agents trained through our reinforcement learning mechanism will be able to develop an action strat-egy to complete their missions in the virtual game environment. Our empirical result has shown some promising result. Even the NPC agents are tested in different game level environments, all agents that share with the same goal will learn to perform ap-propriate actions and achieve the common goal reasonably.

中文摘要　．．．．．．．．．．．．．．．．．．．．． iii
英文摘要　．．．．．．．．．．．．．．．．．．．．． iv
誌謝辭　　．．．．．．．．．．．．．．．．．．．．． v
內容目錄　．．．．．．．．．．．．．．．．．．．．． vi
表目錄　　．．．．．．．．．．．．．．．．．．．．． viii
圖目錄　　．．．．．．．．．．．．．．．．．．．．． ix
第一章　　緒論．．．．．．．．．．．．．．．．．．． 1
　　第一節　　研究背景．．．．．．．．．．．．．．． 1
　　第二節　　研究動機．．．．．．．．．．．．．．． 2
　　第三節　　研究目的與範圍．．．．．．．．．．．． 4
　　第四節　　論文架構．．．．．．．．．．．．．．． 5
第二章　　文獻探討與背景．．．．．．．．．．．．．． 7
　　第一節　　電腦遊戲．．．．．．．．．．．．．．． 7
　　第二節　　A* path-finding．．．．．．．．．． 15
　　第三節　　機器學習．．．．．．．．．．．．．．． 21
　　第四節　　增強式學習Reinforcement Learning．． 23
第三章　　研究方法與設計．．．．．．．．．．．．．． 32
　　第一節　　系統架構．．．．．．．．．．．．．．．． 33
　　第二節　　Agent的合作模式．．．．．．．．．．． 36
　　第三節　　報酬的評估方式．．．．．．．．．．．． 41
第四章　　系統實作與分析．．．．．．．．．．．．．． 44
　　第一節　　系統建置環境．．．．．．．．．．．．．． 44
　　第二節　　系統功能介紹．．．．．．．．．．．．．． 45
　　第三節　　訓練結果與分析討論．．．．．．．．．．． 54
　　第四節　　研究結果．．．．．．．．．．．．．．． 61
第五章　　結論與未來研究方向．．．．．．．．．．．．． 64
參考文獻　．．．．．．．．．．．．．．．．．．．．． 66

一、中文部分

阪本千尋(2002)，專業級遊戲程式設計－完整實例與經驗分享(柯志杰譯)，台北：博碩文化。

陳建成(2003)，以適應性Q-Learning 為基礎發展足球機器人合作策略，國立中正大學電機工程研究所未出版之碩士論文

陳律宇(2006)，以自我組織特徵映射圖為基礎之模糊系統實作連續性Q-learning，國立中央大學資訊工程研究所未出版之碩士論文

趙筱娟(2004)，在虛擬世界中建置智慧型行為模式代理人:以強化學習為基礎的自我學習機制，私立淡江大學資訊工程學系研究所未出版之碩士論文。

二、英文部分

Bellman, R. (1957). Dynamic Programming. Princeton University Press, Princeton, NJ.

Bertsekas, D. P. (1987). Dynamic Programming: Deterministic and Stochastic Models. Prentice-Hall, Englewood Cliffs, NJ.

Buckland, M. (2005). Programming Game AI by Example. Wordware Publishing.

David M. Bourg & Glenn Seemann. (2005)，遊戲人工智慧(陳建勳譯)，台北：美商歐萊禮，(原文於2004年出版)。

Enrique, Sebastian. (2002). An Investigation Into the use of Synthetic Vision for NPC’s/Agents in Computer Games. Unpublished li-cenciatura thesis, Universidad de Buenos Aires Argentina.

Howard, R. A. (1960). Dynamic Programming and Markov Processes. The MIT Press, Cambridge, MA.

Howland, G. Basics of Game AI [Online]. Available: http://www.lupinegames.com/articles/basicai.htm [No date]

Laird, J., & van Lent, M. (2000). Interactive computer games: hu-man-level AI's killer application. In Proceedings of AAAI Na-tional Conference on Artificial Intelligence (pp. 1171-1178).

Lester, Patrick. (2005). A* Pathfinding for Beginners [Online]. Avail-able: http://www.policyalmanac.org/games/aStarTutorial.htm [2005, July 18]

Moore, A. W., Kaelbling L. P., & Littman, M. L. (1996). Reinforce-ment learning: A survey. Journal of Artificial Intelligence Re-search, 4, 237–285.
Nilsson, N. J. (1996). Introduction to Machine Learning [Online]. Available: http://robotics.stanford.edu/people/nilsson/mlbook.html [1996, December 4]

Puterman, M. L. (1994). Markov Decision Processes-Discrete Sto-chastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY.

Robocool. (2006)，人工智慧Java坦克機器人系列:增強式學習[線上資料]，來源：http://www-128.ibm.com/developerworks/cn/java/j-lo-robocode2/index.html [2006, July 13]

Sutton, R. S., & Barto, A. G. (1998). Reinforcement Learning: An In-troduction. Cambridge, Mass. : MIT Press.

Teknomo, K. (2005). Q-Learning by Examples [Online]. Available: http://people.revoledu.com/kardi/tutorial/ReinforcementLearning/index.html [2005]

Watkins, C. J. C. H., & Dayan, P. (1992), Technical note: Q learning, Machine Learning, 8(3), 279-292.

Wikipedia [Online]. Available: http://en.wikipedia.org/wiki/Main_Page



Woodcock, Steven. The Game AI Page:Building Artificial Intelligence into Games [Online]. Available: http://www.gameai.com/ [No date]

Yannakakis, G. N. (2005). AI in Computer Games: Generating Inter-esting Interactive Opponents by the use of Evolutionary Com-putation. Unpublished doctoral dissertation, University of Ed-inburgh, Scotland.