In a challenge set to teams the world over to construct the most efficient machine learning model, EBTIC walked away with first and second place. Their model to predict win rates of the most popular decks of online video game Clash Royale will now be used to improve the game’s AI engine as well as add new objectively vetted predictive capabilities to the work of EBTIC and its partners.
Clash Royale is a video game combining elements from collectible card games, tower defense and multiplayer online battle arena, mixing all the popular game mechanics into a card-based online video game that surpassed USD2.5 billion revenue in the three years since its launch in 2016.
The game’s objective is to destroy the most opposing towers, with playable troops, buildings, and spells represented as cards. Prior to each battle, players construct a deck of eight cards which they use to attack and defend against their opponent’s cards. Clash Royale is a hugely popular game, and even has its own e-sports world championship.
The machine learning element enters into the game at the very start, with both players beginning with four randomly chosen cards from their deck of eight. Once a card has been played, a new card is automatically drawn from the player’s deck. Dr. Dymitr Ruta and Dr. Ling Cen from EBTIC’s Big Data Analytics group developed a model to achieve the most accurate win rate predictions from the cards chosen. The two researchers enhanced support vector machine models with their own parallelized greedy search algorithms to take first and second place in the competition.
In machine learning, support-vector machines (SVM) are supervised learning models with associated learning algorithms that analyze data and then classify them. Given a set of training examples, each marked as belonging to one or another category, an SVM algorithm builds a model that assigns new examples to each category. Support vector regression (SVR) extends the original capability of the SVM model into the regression space, wherein the relationships among variables are estimated.
“The Challenge focused on efficiently predicting the win rates of the most popular Clash Royale decks in 1v1 play using support vector regression,” explained Dr. Cen. “Specifically, the intention was to find out whether it is possible to build an efficient win-rate prediction model on a relatively small subset of decks, whose win rates were estimated in the past.”
“Support vector regression is a powerful supervised machine learning model especially well-suited to normalized or binarized data,” said Dr. Ruta. “However, its quadratic complexity in the number of training examples eliminates it from training on large datasets, especially high dimensionally data with frequent retraining requirements.”
In other words, support vector regression would not be appropriate to use on large datasets like the Clash Royale Challenge 2019 training dataset, which included 100,000 decks comprising exactly 8 cards out of the total of 90 unique possible cards with accompanied win rates computed for over 160 million games.
“We proposed a simple two-stage greedy selection of training data for SVR to maximize its validation set accuracy at the minimum number of training examples and illustrate the performance of such a strategy in the context of the competition,” continued Dr. Ruta. “Hundreds of thousands of labelled data examples were reduced to just hundreds.”
A greedy algorithm is a simple, intuitive algorithm used in optimization problems. It makes the optimal choice at each step given the data available at each step as it attempts to find the optimal way to solve the entire problem. Such algorithms will take all of the data in a particular problem and then set a rule for which elements to add to the solution at each step.
“With the first place scored by our model, we have demonstrated an extreme efficiency of the proposed data editing strategy, which relatively quickly squeezed out the winning accuracy out of just 1 percent of the original dataset,” said Dr. Ruta. “Our model outperformed over one hundred competitive teams from around the world and our results will now be used to improve the game’s AI engine.”
The team was presented with their awards at the Federated Conference on Computer Science and Information Systems (FedCSIS) 2019 conference in September 2019.
Jade Sterling
News and Features Writer
29 September 2019
