臺灣博碩士論文加值系統

近年來，多人線上遊戲成為了網路上非常普遍的休閒活動，但隨著多人線上遊戲的蓬勃發展，玩家欺詐的行為也變得越來越常見，其中最嚴重的，要算是使用俗稱 bot 的自動化機器人程式了，原因是 bot 使用者不需付出對應的努力，即可獲得不合情理的獎勵，一般而言，遊戲社群間是不認同 bot 的存在的。然而想要辨識 bot 使用者，然後加以反制是困難的，原因是 bot 本來就是被設計來在遵循遊戲規則下模仿玩家行為，其行為模式與真正玩家相仿。以往遊戲經營者嘗試以肉眼偵測遊戲機器人程式的方式，經常產生誤判案例糾紛可見一般，因此目前遊戲產業期望藉助一些軟體技術，嘗試來偵測 bot 的存在，以增加判定的準確率。這些偵測技術大致上有幾種類型，第一種是在遊戲進行中，中斷玩家進行方式進而分析玩家類型，缺點是干擾玩家進行遊戲的順暢。第二種反制方式是在遊戲進行中，監測系統是否有 bot 程式存在，這種方式前提是假設機器人程式是必須依附於客戶端遊戲程式，且多半只針對特定功能者。例如 FPS 遊戲中，專司瞄準的機器人程式，其缺點是失去一般性。因此在本論文中，我們對兩種線上遊戲類型分別提出對應的 bot 偵測方式。

第一種為俗稱 FPS 的第一人稱射擊遊戲，提出基於遊戲中人物移動軌跡的方法偵測 FPS 遊戲中的機器人程式，它可以被應用於所有具有移動軌跡類型遊戲的一般性技術。透過真實玩家數據分析，我們得知，真實玩家移動的軌跡特性與那些機器人程式是非常不同的，雖然遊戲機器人程式竭力模仿真實玩家的行為，但是因為玩家行為是非常難以仿造，這點是我們的主要理論基礎。我們採用了 Quake 2 作為實際研究案例，根據評估真實玩家的紀錄顯示，這種偵測方法在以 200 秒為一觀測單位下，可以達到 95% 以上的準確性。

第二種針對節奏類型遊戲，提出一種基於壓力與錯誤率的方法來偵測跳舞機類型遊戲的機器人程式。它也是一個可以被應用於此類跳舞機類型遊戲的一般性技術，理論基礎是，因為玩家會隨著節拍快慢與按鍵組合形成的壓力大小，與按鍵時間與按鍵值與出錯的機率成正比，也因資料簡單，因此此類 bot 非常容易透過學習真實玩家的方式，發展反制 bot 偵測的技術。然而，除非 bot 得知我們的數學式實際參數值，否則反制我們的偵測，也是十分困難的。我們採用了唯舞獨尊此款多人線上遊戲作為我們的實際研究案例，由於至目前為止尚未找到對此類型遊戲 bot 偵測的論文，因此我們是第一個可以用來偵測節奏類型 bot 的論文。

In recent years, online game has become one of the most popular Internet activities, but cheating activity, such as game bots, has increased as a consequence. Generally, the gamer community disagrees with the use of game bots, as bot users obtain unreasonable rewards without corresponding efforts. However, bots are hard to detect because they are designed to simulate human game playing behavior and they follow game rules exactly. Existing detection approaches either interrupt the players'' gaming experiences, or assume game bots are run as standalone clients or assigned a specific goal, such as aim bots in FPS games. Therefore, we separately propose game bot detection approaches according to two different types of online games.

1) A trajectory-based approach to detect FPS game bots. It is a general technique that can be applied to any game in which the avatar''s movement is controlled directly by the players. Through real-life data traces, the result shows that the trajectories of human players and those of game bots are very different. In addition, although game bots may endeavor to simulate players'' decisions, certain human behavior patterns are difficult to mimic because they are AI-hard. Taking Quake 2 as a case study, we evaluate our scheme''s performance based on real-life traces. The result shows that the scheme can achieve a detection accuracy to 95% or higher, given a trace of 200 seconds or longer.

2) A pressure-error-based approach to detect rhythm game bots. It is also a general technique that can be applied to any rhythm game in which the errors increase the dependance on pressure from the game speed and key combinations. Theoretically, the bot can fight back by learning the real player''s behaviors, but without our arguments of formula, the bot is hard to do that. The study case is Dancing Online. Up to now, we have not found any paper about rhythm game bots detection, so we believe that this paper is the first one for rhythm game bots detection.

誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
英文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction 1
2 Related Work 4
3 FPS Game Bot Detection 6
3.1 FPS Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Quake 2 and Its Game Bots . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.1 Human Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.2 Bot Traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3.3 Trace Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4 Discriminative Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.4.1 Aggregated Navigation Pattern . . . . . . . . . . . . . . . . . 10
3.4.2 Individual Trajectories . . . . . . . . . . . . . . . . . . . . . . 12
3.5 Bot Detection Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5.1 Feature Extraction . . . . . . . . . . . . . . . . . . . . . . . . 13
3.5.2 Classi‾cation . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Rhythm Game Bot Detection 21
4.1 Rhythm Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Dancing Online . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2.1 Normal Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2.2 Rhythm Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.3 Beat Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3 Dance Online Game Bots . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.4 Data Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.5 The Recording Program . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5.1 Data Declaration . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.5.2 Recording Program Design . . . . . . . . . . . . . . . . . . . . 28
4.5.3 Data Collection . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.6 Discriminative Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.7 Bot Detection Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.7.1 Time Spent Based . . . . . . . . . . . . . . . . . . . . . . . . 35
4.7.2 Pressure-Error Based . . . . . . . . . . . . . . . . . . . . . . . 37
4.8 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.8.1 Time Spent Based . . . . . . . . . . . . . . . . . . . . . . . . 37
4.8.2 Pressure-Error Based . . . . . . . . . . . . . . . . . . . . . . . 38
5 Conclusion 42
Bibliography 44

[1] Kuan-Ta Chen, Polly Huang, and Chin-Laung Lei. Game traffic analysis: An MMORPG perspective. Computer Networks, 50(16):3002-3023, 2006.
[2] Kuan-Ta Chen, Jhih-Wei Jiang, Polly Huang, Hao-Hua Chu, Chin-Laung Lei, and Wen-Chin Chen. Identifying MMORPG bots: A traffic analysis approach. In Proceedings of ACM SIGCHI ACE''06, Los Angeles, USA, Jun 2006.
[3] Kuan-Ta Chen, Andrew Liao, Hsing-Kuo Kenneth Pao, and Hao-Hua Chu. Game bot detection based on avatar trajetory. In Proceedings of IFIP ICEC 2008, 2008.
[4] Kuan-Ta Chen, Hsing-Kuo Kenneth Pao, and Hong-Chung Chang. Game bot identification based on manifold learning. In Proceedings of ACM NetGames 2008, 2008.
[5] DCO. http://www.play55.net/.
[6] Ryan Ridah Feltrin. Eraser Bot 1.01, May 2000. http://downloads.gamezone.com/demos/d9862.htm.
[7] Philippe Golle and Nicolas Ducheneaut. Preventing bots from playing online games. Computers in Entertainment, 3(3):3-3, 2005.
[8] Id Software: id History. http://www.idsoftware.com/business/history/.
[9] id Software, Inc. http://www.idsoftware.com/.
[10] Said Ila, Dick Mizerski, and Desmond Lam. Comparing the effect of habit in the online game play of australian and indonesian gamers. In Proceedings of the Australia and New Zealand Marketing Association Conference, 2003.
[11] International Games System CO.,LTD. http://www.igs.com.tw/.
[12] jibe. ICE Bot 1.0, 1998. http://ice.planetquake.gamespy.com/.
[13] Mike Malakhov. CR Bot 1.15, May 2000. http://arton.cunst.net/quake/crbot/.
[14] Thomas P. Novak, Donna L. Hoffman, and Adam Duhachek. The influence of goal-directed and experiential activities on online flow experiences. Journal of Consumer Psychology, 13(1):3-16, 2003.
[15] Spasim (1974) The First First-Person-Shooter 3D Multiplayer Networked Game. http://www.geocities.com/jim bowery/spasim.html.
[16] The website of Detours. http://research.microsoft.com/en-us/projects/detours/.
[17] The website of Gamer. http://www.gamer.com.tw/.
[18] The website of Konami. http://www.konami.co.jp/en/.
[19] Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John Langford. CAPTCHA: Using hard AI problems for security. In Proceedings of Eurocrypt, pages 294-311, 2003.
[20] S. Yeung, J.C.S. Lui, J. Liu, and J. Yan. Detecting cheaters for multiplayer games: theory, design and implementation. Proc IEEE CCNC, 6:1178-1182.