Keeping a player within the ow in a game is a central goal for game designers, making the game neither too easy nor too hard. Dynamic Di culty adjustment seeks to ful ll this goal by dynamically tuning di culty according to player actions in the game. In this paper we demonstrate that case-based reasoning with time series can serve to automatically identify the ability of a player in a game, and thus serve as the input for di culty adjustment based on player ability. We try di erent con gurations for the generation of the case base from game logs, and compare them in terms of how well they classify player ability.
culty Adjustment in Tetris with Time
Series?
Player satisfaction is the most important goal for computer games, mainly because if a player does not have fun, then he will stop playing the game [16]. So, maintaining \ ow" or the engagement of the player is crucial. According to Nakamura and Csikszentmihalyi [13] in order to maintain \ ow" they should perceive challenges that enhance their skills, clear goals and immediate feedback. The challenges proposed should be at the \right" level, in the way that the players are challenged but not overwhelmed.
Even in the most simple games, there are several factors that distinguish one player from another, hence there is not a static con guration in level of di culty for everyone. If we are able to di erentiate players by their interaction within the game, then we had improved their satisfaction.
The dynamic di culty adjustment (DDA) can be applied in many games,
despite its genre [
To improve players satisfaction, we can apply an implicit approach in order to use machine learning techniques to adjust a game's di culty [21]. Dynamic Difculty Adjustment helps to maintain the right balance depending on the player behavior. However, DDA usually involves a great amount of work for developers and designers that cannot be reused in other video games. That is why research is important to decrease the costs related to development of adaptive video games using di erent techniques, such us, automatically extracting information from players interaction.
It is possible to know players skill level by evaluating their behavior
during gameplay. Their expertise can not be determined from a single action or
move. However, it can be resolved with the behavior displayed in a period of
time. A time series data is a series of observations made sequentially over time
[
Our main goal, is to create a general approach for DDA that receive as input
the players behavior and ways to modify di culty of a game, and produces an
output with the right level of di culty. We had started our journey with a simple
game like Tetris to determine the best way to achieve this. We extract traces
from previous games and build a case base in which each case describes how the
user places pieces in the game board. Case-based reasoning is a popular approach
for learning by experience [
The rest of the paper is organized as follows. First, we discus the game and the features extracted from the game traces to characterize the level of skills. Then, we explain our approach to dynamically adjust the di culty of the game. Next, we present the experimental setup and the results obtained. Finally, the paper closes with related work, conclusions and directions for future research. 2
Tetris (Figure 1) is a very popular video game in which the player has to place
di erent tetromino pieces that fall from the top of the screen in a rectangular
game board. When a row of the game board is complete, i.e. it has no holes,
the row disappears, all pieces above drop one row and the player is rewarded
with some points. As the game progresses the new pieces fall faster and faster,
gradually increasing the di culty, until one of the new pieces does not t in the
board and the game ends. The goal of the game, therefore, is to complete as
many lines as possible to increase the score and make room for the next pieces.
Although the game is quite simple to play, it is also very di cult to master and
hard to solve from a computational point of view [
In our experiments we use Tetris Analytics, a version of the game that looks like an ordinary Tetris from the point of view of the player but provides extra functionality to extract, store and reproduce game traces. From these traces, we can select the most signi cant features to characterize the playing style of each player, determine his skill level and dynamically adjust the di culty of the game. This way, we can personalize the game for each player in order to improve his user experience.
Each time a new piece appears on the top of the game board, the player has to make two di erent decisions. The rst one, that we call tactical, is to decide the nal location and rotation of the piece. The second decision involves all the moves required to lead the piece to its nal location. For now we have considered only the tactical decisions in order to de ne the skill level of the player, but we are aware that we could also extract valuable information from the concrete moves (looking at parameters like speed, cadence, moves undone, ...) and we plan to extend our work to consider them in the future.
In our previous work [
In Dynamic Di culty Adjustment in Tetris [
In this work, we focus on the problem of deciding the skill level of the player more dynamically, not only at the beginning but throughout the entire game. This way, we expect to better adjust the di culty to the progression of the player. In order to do it we have selected a few number of game features that we describe in the next section, and we study how they evolve over time. 3
In order to collect data we asked 10 di erent players with diverse skill levels to play a total of 60 games of Tetris Analytics. Next we analyzed the game traces and extracted the following features for every tactical decision the players made in the game, that is, every time they placed a new piece in its nal location: { Number of piece: the number of the current piece from the beginning of the game. Since we only consider tactical decisions, the number of piece corresponds to the moment of the game in which this sample is extracted. { Current score: the accumulative game score obtain by the player after placing the current piece. We expect to see a clear correlation between the score during the game and the skill level of the player. { Number of holes : if the pieces are not placed carefully in the board, it is common to leave empty holes under other pieces in the same column. Good players tend to compact very well the pieces in the board without leaving holes so that will be easier to complete lines with the next pieces. { Height of the board : measured as the highest row with some piece. Good players tend to play most of the game in the lowest half of the board because each time they complete a line the height of the board decreases in one unit.
For example, the game state in Figure 1 correspond to the 8th piece of the game, the game score will be 105 plus the points obtained for placing the current piece, and the height of the board is 6 because that is the highest occupied row in the last column on the right side of the board. In this way, a game can be seen as a sequence of tuples or samples describing these values for each piece placed.
Game scores 0 1000 2000 3000 4000 5000 6000 7000 8000
Note that, in contrast with other approaches that use more complex state representations (like the state of each cell in the board), our features try to summarize the skill of the player from very little information. On the other hand, we will look at the progression of those features over time to classify the player instead of just looking at the current game state.
We can classify each game in a di erent skill class based on the nal score obtained. Figure 2 shows the distribution of the game scores in the traces. We can see groups of points very close to each other in some intervals and some gaps between those intervals. Those gaps are good candidates to split the di erent skill classes and in fact we used them to range 3 di erent skill levels: { Newbie: games with a total score between 0 and 2999. { Average: games with a total score between 3000 and 5999. { Expert: games with more than 6000 points.
After the analysis 21.6% of the games were classi ed in the newbie category, 46.2% in the average category and 32.2% in the expert category. Once we know the category of each game we can tag every sample in that particular game with the same category and use any supervised learning algorithm to build a classi er. 4
Samples in the dataset summarize the state of the game (score, number of holes and board height) after the player places each new piece in the board. In general it is not easy to predict the skill level of the player from a static picture of the game, it is much easier if we consider the evolution of the game during some seconds. With this idea in mind, we decided to reorganize the data to create time series describing the evolution of each parameter.
For example, Figure 3 shows the progression of the di erent parameters during one particular game. The blue line represents the game score. It starts in 0 and always increases because the player gets points each time a new piece appears on the top of the board. The abrupt changes in the score correspond to complete lines removed from the board as the result of a good tactical move.
Parameters evolution during a game 2500 2000 1500 e r o c 1000 S 500 0 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61
Num holes
Board height
Score
In this example the player got 2260 points after 61 pieces so this game will be classi ed in the Newbie category. The green line represents the evolution of the board height and changes from 0 (an empty board) to 20 (last row and end of the game). We can see that the player had some problems around piece 25 when the board height reached the row 17, but he was able to control the situation and keep the board height stable for another 30 pieces. It is interesting to note the correlation between the score and the board height: completed lines decrease the height of the board and quickly increase the game score. Finally, the red line corresponds to the number of holes in the board. Usually, the more holes in the board the more di cult is to complete lines. This last parameter shows a higher variability compared to the other two during the game.
Next we divided each game in small fragments that we call cases and represent the evolution of the game during a certain time window. The size of the time window controls what part of the game is captured in each case and determines the length of the time series that we have to consider. Each case is made of 4 parameters: the number of the piece describing the moment of the game in which the case was created; and 3 time series describing the evolution of the score, number of holes and board height during the last n pieces or tactical decisions.
There are di erent approaches to divide a game into cases. Figure 4 shows the ones we have considered: { Single: each case only describes the current game state and there is a case for each piece in the game. We do not use time series in this rst approach (o equivalently the time window size is 1). { Consecutive: we only create new cases every 10 pieces and each case contains 3 non-overlapping time series to describe the evolution of the parameters during the last 10 pieces. A disadvantage of this approach is that the player can only be classi ed again every 10 pieces.
TS sampling
{ Overlapped : same idea but now the time series overlap in time, so we create a case describing the evolution of the parameters during the last 10 pieces. { From start : we create a new case for every piece describing the evolution of the parameters from the beginning of the game to the current moment. In this approach time series have di erent length depending of the moment of the game when they are sampled.
These approaches result in 4 di erent case bases. In order to decide the skill level of a new player we use a k nearest neighbor classi er (k-NN), and the player skill class is decided by a majority vote among the retrieved cases. It is interesting to note that when we look for similar cases in the case base we only consider those that were created at the same moment in previous games. For example, in order to predict the skill level of the player at piece number 20 we only consider cases created at piece 20 in previous games. This lter reduces signi cantly the number of cases to consider and let us to compare time series with the same length (even in the From start approach).
The similarity between 2 cases is computed as a liner combination of the similarities between the normalized time series. Several di erent distances have been proposed for time series [18], in this work we use a simple similarity measure based on the euclidean distance: simc(c1; c2) =
1 simts(c1:score; c2:score) + simts(r; s) = 1 2 simts(c1:holes; c2:holes) + 3 simts(c1:height; c2:height) vu n uX(ri t i=1 si)2
As part of the future work, we would like to investigate other distances between time series and study their e ect in the case retrieval phase. In the following section we evaluate the performance of each case base. For every approach, we evaluate data from di erent moments throughout the game to predict players skill level. We do this to avoid two possible scenarios. First, the users cheating the classi er playing like newbie at the beginning and then playing with their real skill level, which will give them great advantage. Second, the user playing odd in brief period of time due to external factors.
Each one of the 4 approaches described before results in 4 di erent
casebased reasoning (CBR) systems. Now we intent to know which approach is more
accurate to determine the players skill level throughout the game. This way,
we will be able to adjust the di culty of the game in several moments during
gameplay. In the comparison we also include our previous approach based on
clustering of game traces [
The Cluster based classi er used in our previous work does not perform very well when use it to classify users according to their skill level throughout the entire game. CBR approaches, on the contrary, obtain better results because they are based on a reduced number of selected features (the training data is simpler and less noisy) and because we can tune the similarity measure to provide di erent importance to each of the parameters. All CBR approaches in Table 1 were evaluated using 10-NN in which the player skill class was decided by a majority vote, and the optimal weights were selected using a exhaustive grid search with increments of 0.05.
It is interesting to note that all the approaches based on time series are better than the Single classi er. In particular, the approach based on overlapped time series obtains the highest precision (65.42%) and has the advantage that can be used in any moment of the game after piece number 10. Using time series from the start of the game to the current time seems to have no bene cial e ect, probably because the euclidean distance considers equally important all the values in the time series. In games, recent events are usually more important that those that occurred long time ago and we think the precision could be improved using a similarity measure for time series that takes this into account. Regarding the weights, the score is the predominant parameter to decide the skill level as it was expected, followed by the number of holes. The height of the
Precision during the game 100,00 90,00 80,00 70,00 60,00 50,00 40,00 30,00 20,00 1 5 9 31 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 011 105 109 113 117 121 125 129
10 consecutive single 10 overlaped From start board is negligible, probable because of the correlation between this parameter and the score that was explained in the previous section (see Figure 3).
Table 2 shows the precision of each system when we retrieve a di erent number of similar cases to make the prediction. Except in the From start approach, the more cases we consider to classify the player the higher the precision of the system.
Finally, Figure 5 shows the evolution of the precision during the game. In general, the more advanced is the game the easiest is to predict the level of the player. Note however that in order to dynamically adjust the di culty of the game and improve the player experience it is important to classify the player soon and adapt the di culty of the game accordingly. 6
Nowdays there are two approaches for setting up the di culty adjustment of a
game. The rst approach is to let the user to manually set the level of di culty
of the game (e.g. easy, medium, hard). But this implies that the game have
to use a speci c heuristic that employs the main features of the game for each
di culty level. This is a disadvantage because makes it hard to transfer to other
games, requires additional testing and programming, which means higher costs
[
Alternatively, we have Dynamic Di culty Adjustment which is used for
automatically alter games di culty in order to meet players expectations [
With Machine Learning techniques, we can learn and make predictions based
on data resulting from player behavior. Romdhane and Lamontagne [15,14] used
a CBR system with Tetris to assess the quality of the cases and to maintain
control in the size of the case base. They discover that case usage is the best
criteria for forgetting cases. Also, Floyd and Esfandiari [
In this work, we present a game called \TetrisAnalytics", which is like a simple Tetris game, but allows you to save the players interaction and the state of the board. During gameplay the user have to avoid the pieces reach the top of the board by doing lines. The game extract the number of pieces, current score, number of holes and height of the board per tactical move, i.e. every time the player locate a piece on the board, we collect the mentioned features.
With the data collected, we are able to create a database of past experiences and each tactical move can be classi ed by newbie, average and expert depending on the total score of the game to it's belong. By creating new cases every 10 consecutive tactical moves, each case containing 3 overlapped time series, we are able to describe the evolution of the parameters during that period of time. This way, the player only have to play without DDA the rst 10 tactical moves. This approach give us a better accuracy for predicting the players skill level, because not only evaluates the individual moves, but the evolution of the player in a period of time.
As future work, we will implement this approach in \TetrisAnalytics" and verify with new players if their user experience is improved notably by applying dynamic di culty adjustment during gameplay in comparision to our previous experiments where di culty was adjusted just once in the game. 13. Nakamura, J., Csikszentmihalyi, M.: Flow and the Foundations of Positive Psychology: The Collected Works of Mihaly Csikszentmihalyi, chap. The Concept of Flow, pp. 239{263. Springer Netherlands, Dordrecht (2014), http://dx.doi.org/ 10.1007/978-94-017-9088-8_16 14. Romdhane, H., Lamontagne, L.: Forgetting reinforced cases. In: Advances in Case-Based Reasoning, 9th European Conference, ECCBR 2008, Trier, Germany, September 1-4, 2008. Proceedings. pp. 474{486 (2008), http://dx.doi.org/10. 1007/978-3-540-85502-6_32 15. Romdhane, H., Lamontagne, L.: Reinforcement of local pattern cases for playing tetris. In: Proceedings of the Twenty-First International Florida Arti cial Intelligence Research Society Conference, May 15-17, 2008, Coconut Grove, Florida, USA. pp. 263{268 (2008), http://www.aaai.org/Library/FLAIRS/2008/ flairs08-066.php 16. Sweetser, P., Wyeth, P.: Game ow: a model for evaluating player enjoyment in games. Computers in Entertainment (CIE) 3(3), 3{3 (2005) 17. Tom, C.F.: Combining Time Series and Clustering to Extract Gamer Pro le Evolution pp. 262{271 (2014) 18. Warren Liao, T.: Clustering of time series data-a survey. Pattern Recogn. 38(11), 1857{1874 (Nov 2005), http://dx.doi.org/10.1016/j.patcog.2005.01.025 19. Yang, K., Shahabi, C.: A multilevel distance-based index structure for multivariate time series. In: Temporal Representation and Reasoning, 2005. TIME 2005. 12th International Symposium on. pp. 65{73. IEEE (2005) 20. Yang, K., Shahabi, C.: An e cient k nearest neighbor search for multivariate time series. Information and Computation 205(1), 65{98 (2007) 21. Yannakakis, G.N., Hallam, J.: Real-time game adaptation for optimizing player satisfaction. IEEE Transactions on Computational Intelligence and AI in Games 1(2), 121{133 (2009)