Real-Time Strategy (RTS) games are popular testbeds for AI researchers. In this paper we compare di erent machine learning algorithms to predict the outcome of small battles of marines in StarCraft, a popular RTS game. The predictions are made from the perspective of an external observer of the game and they are based only on the actions that the di erent units perform in the battle eld. Our empirical results show that case-based approaches based on k-Nearest Neighbor classi cation outperform other standard classi cation algorithms like Linear and Quadratic Discriminant Analysis or Support Vector Machines.
Real-Time Strategy (RTS) games are popular testbeds for AI researchers [
The ability to predict the outcome of battles is interesting because it can be used to dynamically modify the strategy of the player. For example, the player could decide to change the composition of the army, to bring more troops into the battle eld or deploy them di erently, or even to ee if the prospects are not good. In general, an agent able to make predictions (running an internal simulation based on what he knows) might be able to adapt his behavior more successfully than other agent without this ability.
In this work, we compare classical classi cation algorithms like Linear and Quadratic Discriminant Analysis, Support Vector Machines, and two instancebased classi ers based on the retrieval of the k-Nearest Neighbors (kNN). kNN classi ers can be seen as simple Case-based Reasoning (CBR) systems that only implement the retrieval phase of the CBR cycle. In this paper we study the accuracy of the prediction during the course of the battle, the number of games that each algorithm needs to learn, and the stability of the prediction over time.
The rest of the paper is organized as follows. Sections 2 and 3 describe the scenario used in the experiments, the process to extract the data for the analysis and the features chosen to represent the game state. Sections 4 and 5 explain the di erent classi cation algorithms and the results obtained. The paper concludes with the related work, and some conclusions and directions for future research. 2
StarCraft1 is a popular RTS game in which players have to harvest resources, develop technology and build armies combining di erent types of units to defeat 1 http://us.blizzard.com/en-us/games/sc/ the other players. The combination of di erent types of units and abilities, and the dynamic nature of the game force players to develop strategies at di erent levels. At the macro level, players have to decide the amount of resources invested in map exploration, harvesting, technology development, troops, o ensive and defensive forces, among others. At the micro level players have to combine di erent types of units, locate them in the map and use their abilities. In this paper we focus on small battles, that is, at the micro level.
StarCraft also provides a map editor to create custom games. Using this tool, we have created a simple combat scenario (Figure 1) in which each player controls a small army of 6 terran marines (marines are basic ground combat units with ranged attack). The game always begins with the same initial con guration, each army located on opposite sides of the map, and the game ends when all the units of one player are destroyed. In this type of scenario it is very important to strategically locate the units on the map to take advantage of the range attack and concentrate the re on a few units to destroy them as soon as possible. 3
In order to obtain the data to train the di erent classi ers, we played 200 games collecting traces that describe the evolution of the games. We con gured the map so the internal game AI controls both players so (1) we can automatically play as many games as required, and (2) we know that all the games are well balanced (since the StarCraft AI is playing against itself). Finally, there is a third player that only observes the game (it does not intervene) and extracts the game traces to a le so they can be analyzed later2.
The data set contains traces of 200 games in which player 1 won 119 times and player 2 the remaining 81. They are very fast games with an average duration of 19.12 seconds. In each trace we store the game state 6 times per second, so each game is described with approximately 114 games states or samples.
Each game state is stored using a vector of features (Table 1) that represents the combat power of each army and the strategic deployment of the troops in the map. The combat power is represented using the number of units alive in each 2 We use the BWAPI framework to extract information during the game (https://github.com/bwapi/bwapi).
Average number of deaths 0 20
40 60 Game duration (%) 80 100 army and their average life. To represent the strategic distribution of troops in the map we compute the area of the minimum axis aligned rectangle containing the units of each player and the distance between the centers of both rectangles. The rectangle area is a measure of the dispersion of the units, and the distance between the centers indicates how close the two armies are. Each game state is labeled later with the winner of that particular game. The table also shows the game and the current frame for clarity (1 second is 18 game frames although we only sample 6 of them), but we do not use those values in the prediction.
The features to describe the strategic distribution of the troops in the map are especially important during the rst seconds of the game. Figure 2 shows the average number of dead units during the 200 games. As we can see, during the rst half of the game the armies are approaching each other and the ght does not start until the second half. Thus, during the rst seconds of the game the predictions will depend only on the relative location of the units. 4
We will compare the following classi cation algorithms in the experiments:
{ Linear Discriminant Analysis (LDA) [
Base 0.5839 LDA 0.7297 QDA 0.7334 SVM 0.7627 kernel = radial, C = 1, sigma = 0.3089201 KNN 0.8430 k = 5
KKNN 0.9570 kernel = optimal, kmax = 9, distance = 2
Table 2: Classi cation algorithms, con guration parameters and global accuracy.
{ Support Vector Machines (SVM) [
The three rst algorithms use the training data (labeled game states in our
experiments) to infer a generalized model, and then they use that model to
classify the test data (new unseen game states). The last two algorithms, however,
use the training data as cases and the classi cation is made based on the most
similar stored cases. All the experiments have been run using the R
statistical software system [
Table 2 shows the con guration parameters used in each classi er and its accuracy computed as the ratio of samples (game states) correctly classi ed. The optimal parameters for each classi er were selected using repeated 10-fold cross 1.0 0.9 y c ra0.8 u c c a 0.7 0.6 lda qda svm knn kknn 50 time (%) validation over a wide set of di erent con gurations. The accuracy value has been calculated as the average of 32 executions using 80% of the samples as the training set and the remaining 20% as the test set.
The base classi er predicts the winner based only on the proportion of samples belonging to each class (58.39% of the samples correspond to games won by player 1) and it is useful only as a baseline to compare the other classi ers. LDA, QDA and SVM obtain accuracy values ranging from 72% to 76%. The two instance-based algorithms, on the other hand, obtain higher precision values. It is especially impressive the result of kkNN that is able to predict the winner 95.70% of the times. These results seem to indicate that, in this particular scenario, it is quite di cult to obtain a generalized model, and local based methods perform much better.
The global accuracy value may not be informative enough because it does not discriminate the time of the game when the prediction is made. It is reasonable to expect the accuracy of the predictions to increase as the game evolves as it is shown in Figure 3. The x-axis represents the percentage of elapsed time (so we can uniformly represent games with di erent duration) and the y-axis the average accuracy of each classi er for game states from that time interval.
Selecting a winner during the second half of the game is relatively easy since we can see how the battle is progressing, but during the rst half of the game the prediction problem is much more di cult and interesting since we only see lda qda svm knn kknn
100 number of games 150 the formation of the armies (pre-battle vs. during battle prediction). LDA, QDA and SVM do not reach 90% of accuracy until the last quarter of the game. kNN is able to reach the same accuracy at 66% of the game. The results of kkNN are spectacular again, classifying correctly 90% of the game states from the rst seconds. kkNN is the only algorithm able to e ectively nd useful patters in the training data before the armies begin to ght. Our intuition is that the training data is biased somehow, probably because the StarCraft AI is playing against itself and it does not use so many di erent attack strategies. In any case, kkNN seems to be the only algorithm to e ectively predict the outcome of the battle from the rst moves of each army.
Another important aspect when choosing a classi er is the volume of training data they need to perform well. Figure 4 shows the accuracy of each classi er as we increase the number of games used during the training phase. In the rst 20 games all the algorithms perform similarly but then only kNN and kkNN keep improving fast. It makes sense for instance-based algorithms to require a large number of samples to achieve their highest degree of accuracy in complex domains, while algorithms that infer general models stabilize earlier but their prediction is more biased.
Finally, Figure 5 shows the stability of the predictions. We divided the game in 20 intervals of 5% of time. The y-axis represents the number of games for which the classi er made a prediction in that time interval that remained stable lda qda svm knn kknn
50 time (%) 75 for the rest of the game. For example, the y value for x 0 represents the number of games in which the prediction became stable during the rst time interval (0-4.99% of the game). Most of the classi ers need to wait until the last quarter of the game to be stable in 80% of the games, except kkNN that is very stable from the beginning. There are a few games, however, in which all the classi ers are wrong until the end of the game because the army that was winning made bad decisions during the last seconds.
In conclusion, instance-based classi ers seems to perform better in our scenario, and kkNN in particular is the only algorithm that is able to e ectively nd useful patters in the training data before the armies begin to ght. It is also the most stable and it only performs worst than the other algorithms where there is a very small number of training games available. 6
RTS games have captured the attention of AI researchers as testbeds because
they represent complex adversarial systems that can be divided into many
interesting subproblems [
There are several papers regarding the combat aspect of RTS games. [
Several di erent approaches have been used to model opponents in RTS
games in order to predict the strategy of the opponents and then be able to
respond accordingly: decision trees, kNN, logistic regression [
A paper very related to our work is [
In this paper we compare di erent machine learning algorithms in order to predict the outcome when two small marine armies engage in combat in the StarCraft game. The predictions are made from the perspective of an external game observer so they are based only on the actions of the individual units. The proposed approach is not limited to RTS games and can be used in other domains like multi-agent simulations, since it does not depend on whether the actions are decided by each unit autonomously or by a global manager. Our results indicate that, in this scenario, instance-based classi ers such as kNN and kkNN behave much better than other classi ers that try to infer a general domain model in terms of accuracy, size of the training set and stability.
There are several possible ways to extend our work. We have only considered a small battle scenario with a limited number of units. As the number and diversity of units increases, the number of possible combat strategies also grows creating more challenging problems. Our map is also quite simple and at, while most of the StarCraft maps have obstacles, narrow corridors, wide open areas and di erent heights providing locations with di erent tactical value. The high accuracy values obtained by kkNN from the rst seconds of the battle make us suspicious about the diversity of the strategies in the recorded games. We plan to run new experiments using human players to verify our results. Finally, our predictions are based on static pictures of the current game state. It is reasonable to think that we could improve the accuracy if we consider the evolution of the game and not just the current state to predict the outcome of the battle.