In this paper we compare di erent machine learning algorithms to predict the outcome of 2 player games in StarCraft, a wellknown Real-Time Strategy (RTS) game. In particular we discuss the game state representation, the accuracy of the prediction as the game progresses, the size of the training set and the stability of the predictions. Real-Time Strategy (RTS) games are very popular testbeds for AI researchers because they provide complex and controlled environments on which to test di erent AI techniques. Such games require the players to make decisions on many levels. At the macro level, the players have to decide how to invest their resources and how to use their units: they could promote resource gathering, map exploration and the creation of new bases in the map; or they could focus on building defensive structures to protect the bases and training o ensive units to attack the opponents; or they could invest in technology development in order to create more powerful units in the future. At the micro level, players must decide how to divide the troops in small groups, where to place them in the map, what skills to use and when, among others. And all these decision have to be reevaluated every few minutes because RTS games are very dynamic environments due to the decisions made by the other players. Most of the literature related to AI and StarCraft focuses on the creation of bots that use di erent strategies to solve these problems. There are even international competitions in which several bots play against each other testing di erent AI techniques [5, 4, 3]. In this paper we use a di erent approach, our bot does not play but acts as an external observer of the game. Our goal is to be able to predict the winner of the game with certain level of trust based on the events occurring during the game. In order to do it, we have collected data Supported by Spanish Ministry of Economy and Competitiveness under grant TIN2014-55006-R
from 100 di erent 2 player games, and we have used them to train and compare di erent learning algorithms: Linear and Quadratic Discriminant Analysis, Support Vector Machines, k-Nearest Neighbors.
The rest of this paper is organized as follows. Next section describes StarCraft, the RTS game that we use in our experiments. Section 3 explains the process to extract the data for the analysis and the features chosen to represent the game state. Section 4 describes the di erent data mining classi ers that we use to predict the winner. Next, Section 5 analyzes the predictions produced by the di erent classi ers and the accuracy that we are able to reach. The paper concludes with a discussion of the related work, conclusions and some directions for future work. 2
StarCraft1 is a popular Real-Time Strategy game in which players have to harvest resources, develop technology, build armies combining di erent types of units and defeat the opponents. Players can choose among 3 di erent races, each one with their own types of units, strengths and weaknesses. The combination of di erent types of units and the dynamic nature of the game force players to adapt their strategies constantly, creating a really addictive and complex environment. Because of this, StarCraft has become a popular testbed for AI researchers that can create their own bot using the BWAPI2 framework.
In this paper we will focus on just one of the three available races: the Terrans that represent the human race in this particular universe. At the beginning of the game (see Figure 1), each player controls only one building, the command center, and a few collecting units. As the game progresses, each player has to collect resources, build new buildings to develop technology and train stronger troops in order to build an army and defeat the opponents. Figure 2 shows the same game after one hour of play, and now both players control several di erent units. In fact, the mini-map in the bottom left corner of the screen reveals the location of both armies (blue and red dots), and the game seems balanced because each player controls about half of the map3. 3
In order to collect data to train the di erent classi ers we need to play several games. Although StarCraft forces the existence of at least one human4 player in the game, we have found a way to make the internal AI that comes implemented 1 http://us.blizzard.com/en-us/games/sc/ 2 http://bwapi.github.io/ 3 In this example we have removed the fog-of-war that usually hides the parts of the map that are not visible for the current player. 4 Note that human players are actually the ones controlled by bots using BWAPI while computer players are controlled by the game AI.
Fig. 1: StarCarft: rst seconds of the game. s e m 4 a g f o r e b m u 2 n 0
Duration of games 30 60time (min) 90 120 in StarCraft to play against itself. This way we are able to play as many games as we need automatically, and we are sure the game is well balanced since both players are controlled by the same AI.
It is possible to modify the prede ned maps included in StarCraft to make the internal game AI to play against itself using a map editor tool provided with the game. In our experiments we have modi ed the 2 players map Baby Steps, so that StarCraft controls the rst 2 players and there is an extra third human player. There are di erent AI scripts available depending on the desired level of aggressiveness, we have used Expansion Terran Campaign Insane. The human player has no units, will be controlled by our BWAPI bot and has full vision of the map. Finally, we disable the normal triggers that control the end of the game so we can restart the game from our bot when one the rst 2 players wins. This last step is important because the normal triggers would end the game as soon as it starts because the third player has no units. Therefore, our bot cannot interfere in the development of the game but can extract any information we require.
We have created a dataset containing traces of 100 games in which each player won 50% of the times. Figure 3 shows the duration in minutes of the games. There are a few fast games in which one of the players was able to build a small army and defeat the other player quickly, but most games last between 45 and 100 minutes. The average duration of the games is 60.83 minutes.
Figure 4 shows the evolution of resources and units of one player computed as the average values of 100 games. The x-axis represents time as a percentage of the game duration so we can uniformly represent games with di erent duration, and the y-axis the number of resources (left image), buildings and troops (right image). Regarding resources, we see that during the rst quarter of the game the player focus on gathering resources that will be expended during the second quarter, probably building an army and developing technology. During the second half of the game resources do not change so much, probably because 4000 3500 3000 2500 2000 there are not so many resources left in the map and the player has to invest them more carefully. Regarding troops and buildings, the initial strategy is to build an army as fast as possible, while the construction of buildings seems more lineal. During the second half of the game there are more buildings than troops in the map, but we need to take into account that some of those buildings are defensive structures like anti-air turrets or bunkers that also play a role in combat. The nal fall in the number of troops and buildings correspond to the last attacks, in which half of the times the player is defeated.
During the games we collect traces representing the state of the game at a given time. Each trace is represented using a vector of features labeled with the winner of the game (see Table 1). We try to capture the strength of each player using the available resources and the number of units of each particular type controlled at the current time. The table also shows the game and the current frame (1 second are 18 game frames) for clarity, but we do not use these values to predict the winner. We extract one trace every 5 seconds collecting an average of 730 traces per game.
There are 2 di erent types of resources (minerals and gas), 15 di erent types of troops and 11 di erent types of buildings only in the Terran race. So we need a vector of 28 features to represent each player in the current state. We could have decided to represent the strength of each player using an aggregation function instead of using this high dimensional representation, but since this is a strategy game we hope to be able to automatically learn which combination of units is more e ective. 4
We will use the following classi cation algorithms in the experiments:
{ Linear Discriminant Analysis (LDA) [
All the experiments in this paper have been run using the R statistical
software system[
Table 2 shows the con guration parameters used in each classi er. The values in the table for each classi er were selected using repeated 10-fold cross validation over a wide set of di erent con gurations. The overall accuracy value represents the ratio of traces correctly classi ed, and it has been computed as the average accuracy value of 16 executions using 80% of the traces as the training set and the remaining 20% as the test set.
One open problem in classi cation is to be able to characterize the domain to decide in advance which learning algorithm will perform better. We usually do not know which algorithm to choose until we have run the experiments. In our experiments all of them seem to perform very similar. The base classi er predicts the winner according to the number of traces in the dataset won by each player (i.e. ignores the current state to make the prediction) and it is included in the table only as a baseline to compare the other classi ers. The best results are for QDA that reaches a level of accuracy of 71%. 71% might not seem to be very high but we have to take into account that the games are very balanced because the same AI controls both players and the distribution of resources in the map is symmetrical for both players. Besides, in this experiment we are using all the traces in the dataset, so we are trying to predict the winner even during the rst minutes of each game.
Figure 5 shows some more interesting results, the average accuracy of the di erent classi ers as the game progresses. RTS games are very dynamic environments and just one bad strategic decision can tip the balance towards one of the players. How long do we have to wait to make a prediction with some level of trust? For example, using LDA or QDA we only have to wait until a little over half of the game to make a prediction with a level of accuracy over 80%. It is also interesting that during the rst half of the game the classi ers based on lazy algorithms like KNN and KKNN perform better, and other algorithms like LDA and QDA obtain better results during the second half. All the classi ers experience a great improvement in terms of accuracy when we get close to the middle of the game. We think that at this point of the game both players have already invested most of their resources according to their strategy (promoting some type of units over others, locating the defensive buildings in the bases...) so it is easier to predict the outcome of the game. When the games reaches the 90% of their duration, all classi ers obtain a level of accuracy close to 100% but that is not surprising because at this point of the game one the players has already lost an important part of his army.
1.0 0.8 y c a r u c c a 0.6 0.4 lda qda svm knn kknn 0 25 75
100
Another important aspect when choosing a classi er is the number of samples you need during the training phase in order to reach a good level of accuracy. Figure 6 shows the level of accuracy of each classi er as we increase the number of games used for training. Lazy approaches like KNN and KKNN seem to work better when we use less than 25 games for training, and LDA is able to model the domain better when we use more than 30 games.
Finally, we will analyze the stability of the predictions produced by each classi cation algorithm. It is important to obtain some prediction that do not change constantly as the game progresses. Figure 7 shows the number of games at a given time for witch the prediction did not change for the rest of the game (in this experiment we make 20 predictions during each game at intervals of 5% of the duration). So, for example, when we reach the half of the game LDA will not change its prediction anymore for 10 out of the 20 games we are testing.
In conclusion, is this domain and using our game state representation, LDA seems to be the best classi er. It obtains a level of accuracy over 80% when only 55% the game has been played, it learns faster than the other algorithms from 30 games in the training set, and it is the most stable classi er for most part of the game.
20
40 number of games 60 80 lda qda svm knn kknn 0.70 y0.65 c a r u c c a 0.60 0.55
0
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 [
In [
In this paper we have compared di erent machine learning algorithms in order to predict the outcome of 2 player Terran StarCraft games. In particular we have compared Linear and Quadratic Discriminant Analysis, Support Vector Machines and 2 versions of k-Nearest Neighbors. We have discussed the accuracy of the prediction as the game progresses, the number of games required to train them and the stability of their predictions over time. Although all the classi cation algorithms perform similarly, we have obtained the best results using Linear Discriminant Analysis.
There are several possible ways to extend our work. First, all our experiments take place in the same map and using the same StarCraft internal AI to control both players. In order to avoid bias and generalize our results we will have to run more experiments using di erent maps and di erent bots. Note that it is not clear whether the accuracy results will improve or deteriorate. On the one hand, including new maps and bots will increase the diversity in the samples making the problem potentially more complex but, on the other hand, in this paper we have been dealing with an added di culty that is not present in normal games: our games were extremely balanced because the same AI was controlling both players. Each bot is biased towards some way of playing, like humans, and we are not sure about the e ect that may have in our predictions.
Another approach to extend our work is to deal with games with more than 2 players. These scenarios are much more challenging, not only because the prediction of the winner can take values from a wider range of possibilities but because in these games players can work in group as allies (forces in StraCraft terminology). On the other hand, we have addressed only one of the three available races in our experiments and, of course, in the game some units from one race are more e ective against other units of other races.
Finally, in this paper we have chosen to use a high dimensional representation of the game state that does not take into account the distribution of the units and buildings in the map, only the number of units. We do not consider either the evolution of the game to make a prediction, we forecast the outcome of the game based on a picture of the current game state. It is reasonable to think that we could improve the accuracy if we consider the progression of the game, i.e., how the game got to the current state. We think there is a lot of work to do selecting features to train the classi ers.