Automatically Extracting and Communicating Decision Rules for Increased Success in Real-time Strategy Games.

摘要

In real-time strategy games, strategy refers to how the player chooses to use military and economic resources. Another common name for this is macromanagement. Tactics (also known as micromanagement) refer to the movement of individual units and how to use them to win individual battles. Winning the game requires players to make a successful connection between strategy and tactics. In order to build this connection, however, players must involve a great deal of time and effort in order to obtain the base knowledge required.;There has been previous work done that examines both strategy and tactics in real-time strategy games. For strategy, previous work researches things such build orders or resource distributions. For tactics, they focused on battle management. To our knowledge, however, this is the first work that addresses the connection between strategy and tactics.;For example, let's consider the "Tower Rush" strategy. The "Tower Rush" is a strategy in which one player destroys all of an opponent's buildings very quickly by building cheap, but powerful, towers. Traditionally, "Tower Rush" needs expert knowledge to guide how many resources the player needs, what the correct build order is, when to launch an attack, the proper placement of towers, etc. My approach would quantify the "Tower Rush" strategy using conditional rules and then visualize the rules in game. To achieve the "Tower Rush," the player only needs to know basic operations like how to operate a resource miner, how to construct buildings, how to attack units, etc.;In my dissertation, I bridge the knowledge gap between strategy and tactics by leveraging signal processing and machine learning to obtain decision rules consistent with successful outcomes that are easily interpreted by novice players or implemented by bots.;Filling this gap in traditional way through experiences can be time-consuming and ineffective. This phenomenon is also known as the "knowledge acquisition bottleneck." To automatically fill the gap, I create a middle level, called decision rules, between strategy and tactics. I first analyze expert game logs and model the game logs as time-evolving models (e.g., time series and sequences of graphs) to keep the temporal information and changes of states in game environments. I then extract features from the time-evolving models by combining and applying feature extraction methods, signal processing, and machine learning. Next I obtain decision-tree rules by building decision tree models and use the extracted features as input. Finally, I translate the decision-tree rules to decision rules because the decision-tree rules are not easily interpretable.;My evaluation proceeds in four phases in a popular real-time strategy game, Starcraft and a popular action real-time strategy game, DotA. In phase one, ML-based validation is used to evaluate that the rules are predictive of a game win. First, I collected game logs played by professional players and split them into a training set and a test set. Second, I use training set to extract the knowledge and test the prediction accuracy on the test set. In phase two, I validate the rules by game experts. In phase three, I implement the rules in a game bot and compete it with other game bots. The competition of game bots shows the extracted knowledge is effective in real game environments. In phase four, I create a visualization system. I measure the decision-making performance metrics of players guided by the visualization system in order to show that communication between players and the decision rules is effective.;In an appendix, I also present how my approach can be extended to another real-time strategy game and even other complex environments. I first validate my approach in Warcraft III (another popular real-time strategy game). I then show my approach can be used in hurricane environments and in currency exchange environments.