臺灣博碩士論文加值系統

如何設計代理人的決策系統，並使其能夠自動學習或發展新的策略一直是人工智慧領域尚待解決的問題。本論文在即時戰略遊戲（Real-Time Strategy Game）的環境下，藉由分析玩家的策略風格以建立具學習能力的決策系統。除了建立具有特殊玩家風格的自動決策系統外，尚能做為假想敵以供對戰演練。即時戰略遊戲的策略考量包括了資源分配、資訊隱藏、善用環境以及策略佈局，這些在遊戲中的考量權衡與真實世界中的戰場、商場、以及球場上所考慮的主要因素是一致的。在即時戰略上設計有計畫與學習能力的決策系統常會遭遇到複雜性的問題，例如決策空間太過龐大，系統不太可能即時下定決策，部分研究者嘗試以人工設計幾種固定策略，再從中採用動態挑選、學習的機制，這種作法雖然成功的降低了策略空間的複雜度，卻又回到了最原始的問題－「電腦的策略（打法）在一定的程度上被預先限制住了」。
人類之所以能夠進步快速的原因就在於懂得善用前人的經驗，生病的時候我們知道要吃什麼藥，而不需要再嘗百草。 透過過去發生的記錄，人類可以預知什麼行為可能會帶來什麼結果，我們學會如何去擇優避劣而不需要親自體驗。 即時戰略所儲存的記錄檔是許多玩家競賽後留下的寶貴經驗，然而目前的即時戰略人工智慧卻缺乏吸收這些經驗的設計。 在這次研究當中我們會收集大量的記錄檔，然後根據我們想要了解的玩家作篩選，篩選的方式是透過玩家的個人習慣，並將篩選出來的資料作為輸入，探勘出玩家在面臨各種狀況下的決策，以瞭解並形成玩家的個人風格。 我們所採用的核心方法是案例推論(Case Based Reasoning)，已經有許多研究者很成功的將這套方法運用在各種領域，像是醫學、遊戲、以及機器人的移動上。 實驗的最後我們比較決策系統所做的決策，以及記錄檔中玩家的實際決策，來驗證我們的模型。 在驗證的過程中我們發現系統很容易達到五成以上的預測準度，從一場場比賽的預測準度變化來看，不同的玩家在遊戲中的策略方針也的確有各自的特色。

The author built a decision-making system with learning ability in real-time strategy(RTS) games. The focus falls on the strategy style of player which is used to build an intelligent opponent agent for practicing.
The factors of strategy considered in RTS games include resource management, information hiding, environment, and strategy priority-arrangements. Similar practical experience and application can be found in battlefield, business or ball game. Most of decision system in real-time strategy games with planning and learning ability cannot avoid uncertain and unpredictable complexity problem— “It cost too much time to make a decision in a complex, real-time environment." Some researchers try to dynamically choose and evolve sub-plans between fixed handmade plans. Although this kind of design was successful in reducing time complexity, it was limited in a sense.
In this thesis, case-based reasoning approach is applied to analyzing gaming experience from player’s playing log for building a decision-making system. The end of this thesis verifies the proposed model by comparing the strategy made by our system and real decision made by human players. We found that each player has formed significant personal strategy style which can be found in different game plays.

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
一、緒論 1
1.1 策略挑選問題與即時戰略遊戲 1
1.2 玩家策略模型 2
1.3 從觀戰中學習 2
1.4研究目標 3
1.5論文架構 3
二、研究背景 4
2.1 即時戰略 4
2.1.1即時戰略簡介 4
2.1.2 電子競技的發展與遊戲的高度競爭 5
2.1.3 即時戰略的特性 6
2.1.4 策略佈署: 科技樹 11
2.1.5遊戲歷程: 記錄檔 13
2.2即時戰略中的戰術與觀念 14
2.2.1極端戰術 14
2.2.2資源採集 15
2.2.3環境的考量 16
2.2.4補給 17
2.2.5微控 17
2.2.6兵力配置、科技走向 17
2.3人工智慧在即時戰略上的發展 18
2.3.1發展緩慢的人工智慧 18
2.3.2支持發展人工智慧的論調 18
2.3.3即時戰略遊戲中的新一代人工智慧發展目標 19
2.4即時戰略遊戲的AI研究平台 20
2.5 案例推論(Case-Based Reasoning) 21
三、研究設計與實驗步驟 23
3.1 原始資料的取得 23
3.2 資料的格式與限制 24
3.3實驗模型與架構 27
3.3.1玩家動作模型 27
3.3.2 玩家策略模型 29
四、實驗與結果 34
4.1 玩家辨識實驗 34
4.2 玩家策略的預測 34
4.2.1 建造策略的母空間 34
4.2.2 建造策略的觀察值 35
4.2.3玩家辨識模型VS.人工整理資料 37
4.2.4盤面判定法的效果檢測 38
4.2.5 玩家的策略集中程度 40
五、結論 44
參考文獻 46

1. Tyrrell, T., Computational Mechanisms for Action Selection. 1993, University of Edinburgh.
2. Tyrrell, T., The Use of Hierarchies for Action Selection. Adaptive Behavior, 1993. 1(4): p. 387.
3. Decugis, V. and J. Ferber, Action selection in an autonomous agent with a hierarchical distributed reactive planning architecture. Proceedings of the second international conference on Autonomous agents, 1998: p. 354-361.
4. Bryson, J., Hierarchy and sequence vs. full parallelism in action selection. Intelligent Virtual Agents, 1999. 2: p. 113–125.
5. Tzu, S., The Art of War. 2005: Digireads. com.
6. Laird, J.E., Using a computer game to develop advanced AI. Computer, 2001. 34(7): p. 70-75.
7. Buro, M., Call for AI research in RTS games. Proceedings of the AAAI-04 workshop on AI in games, San Jose 2004, 2004: p. 139–142.
8. Buro, M., ORTS: A hack-free RTS game environment. Proceedings of the Third International Conference on Computers and Games, 2002: p. 156–161.
9. Molineaux, M. and D.W. Aha, TIELT: A Testbed for Gaming Environments. Proceedings of the Twentieth National Conference on Artificial Intelligence (Intelligent Systems Demonstrations), 2005.
10. Aha, D.W. and M. Molineaux, Integrating learning in interactive gaming simulators. Challenges in Game AI: Papers of the AAAI, 2004. 4: p. 04-04.
11. Aha, D.W., M. Molineaux, and M. Ponsen, Learning to win: Case-based plan selection in a real-time strategy game. Proceedings of the Sixth International Conference on Case-Based Reasoning. Chicago, IL: Springer, 2005.
12. Taylor, T.L., Power Gamers Just Want To Have Fun?: Instrumental Play In A MMOG. Paper presented at the 1st Digra Conference: Level Up, 2003.
13. Chee, F., Understanding Korean experiences of online game hype, identity, and the menace of the “Wang-tta”. DIGRA 2005 Conference: Changing Views-Worlds in Play.
14. Wallace, B., Gamer is royalty in S. Korea, in LA-Times. 2007.
15. Maes, P., Situated agents can have goals. ROBOT. AUTONOMOUS SYST., 1990. 6(1): p. 49-70.
16. Lorenz, E.N., The Essence of Chaos. 1996: University of Washington Press.
17. Southey, F., W. Loh, and D. Wilkinson, Inferring Complex Agent Motions from Partial Trajectory Observations.
18. Aamodt, A. and E. Plaza, Case-Based Reasoning. Proc. MLnet Summer School on Machine Learning and Knowledge Acquisition, 1994: p. 1-58.
19. Leake, D.B., CBR in Context: The Present and Future. Case-Based Reasoning: Experiences, Lessons, and Future Directions, 1996: p. 3–30.
20. Schmidt, R., et al., Case-Based Reasoning for Medical Knowledge-based Systems. International Journal of Medical Informatics, 2001. 64(2-3): p. 355-367.
21. Likhachev, M. and R.C. Arkin, Spatio-temporal case-based reasoning for behavioral selection. Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on, 2001. 2.
22. Cheng, D.C. and R. Thawonmas, Case-based plan recognition for real-time strategy games. Proceedings of the Fifth Game-On International Conference, 2004: p. 36-40.
23. Molineaux, M., D.W. Aha, and M. Ponsen, Defeating Novel Opponents in a Real-Time Strategy Game.