Identifying and Clustering Counter Relationships of Team Compositions in PvP Games for Efficient Balance Analysis
Authors: Chiu-Chou Lin
Yu-Wei Shih
Kuei-Ting Kuo
Yu-Cheng Chen
Chien-Hua Chen
Wei-Chen Chiu
I-Chen Wu
Venue: Accepted by TMLR ()

Abstract: \textbf{How can balance be quantified in game settings?} This question is crucial for game designers, especially in player-versus-player (PvP) games, where analyzing the strength relations among predefined team compositions—such as hero combinations in multiplayer online battle arena (MOBA) games or decks in card games—is essential for enhancing gameplay and achieving balance. We have developed two advanced measures that extend beyond the simplistic win rate to quantify balance in zero-sum competitive scenarios. These measures are derived from win value estimations, which employ strength rating approximations via the Bradley-Terry model and counter relationship approximations via vector quantization, significantly reducing the computational complexity associated with traditional win value estimations. Throughout the learning process of these models, we identify useful categories of compositions and pinpoint their counter relationships, aligning with the experiences of human players without requiring specific game knowledge. Our methodology hinges on a simple technique to enhance codebook utilization in discrete representation with a deterministic vector quantization process for an extremely small state space. Our framework has been validated in popular online games, including \textit{Age of Empires II}, \textit{Hearthstone}, \textit{Brawl Stars}, and \textit{League of Legends}. The accuracy of the observed strength relations in these games is comparable to traditional pairwise win value predictions, while also offering a more manageable complexity for analysis. Ultimately, our findings contribute to a deeper understanding of PvP game dynamics and present a methodology that significantly improves game balance evaluation and design.

Published in Transactions on Machine Learning Research (09/2024)
Identifying and Clustering Counter Relationships of Team Compositions in PvP Games for Efficient Balance Analysis
Chiu-Chou Lin
Seobscure@outtooos com yoway0, 300mg0003,0@0ai com kuo0404 @gmmail com yacheng8881 111 18 @gmaill com m11 53031 Znnggmall...mmmmmmmmmmmmmmmmmmmz com walon Ccs nchu, edu, tw
Yu-Wei Shih
Kuei-Ting Kuo
Yu-Cheng Chen
Chien-Hua Chen
Wei-Chen Chiu
Department of Computer Science
National Yang Ming Chiao Tung University, Hsinchu 30010, Taiwan
I-Chen Wu
iowu@os iew.@os..yyu.ee. nycu. edu.
Department of Computer Science
National Yang Ming Chiao Tung University, Hsinchu 30010, Taiuann Research Center for Information Technology Innovation Academia Sinica, Taipei 11529, Taiwan
Reviewed on OpenReview: https: // openreview. net/ formf id= 2036o
Abstract
How can balance be quantified game settings? This question is crucial for game designers, especially player-versus-plaee (PvP) games, where analyzing the strength rela- tions among predefined team compositions such as hero combinations in multiplayer online battle arena (MOBA) games decks in card games-Bs essential for enhancing gameplay and achieving balance. We have developed two advanced measures that extend beyond the simplistic win rate to quantify balance in zero-sum competitive scenarios. These measures are derived from win value estimations, which employ strength rating approximations via the Bradlcy-Terry model and counter relationship approximations via vector quantization, significantly reducing the computational complexity associated with traditional win value estimations. Throughout the learning process of these models, we identify useful categories of compositions and pinpoint their counter relationships, aligning with the experiences of human players without requiring specific game knowledge. Our methodology hinges simple technique to enhance codebook utilization in discrete representation with a deter- ministic vector quantization process for an extremely small state space. Our framework has been validated in popular online games, including Age of Empires II, Hearthstone, Brawl Stars, and League of Legends. The accuracy of the observed strength relations these games is comparable traditional pairwise win value predictions, while also offering more manageable complexity for analysis. Ultimately, our findings contribute a deeper un- derstanding of PvP game dynamics and present methodology that significantly improves game balance evaluation and design.
1
Introduction
In the dynamic landscape of player-versuu-player (PvP) games, leam compositions, or 'comps," such as hero combinations or decks formed before matches commence, are pivotal (Costa et al. 2019: de Mesentier Silva ctt al.] [2019 Reis et al.) (021). The gaming industry, now approximately a 200 billion US dollar market [Kristianto] 2023). thrives on the diversity and engagement offered by these compositions, reflecting players'
individuality and sustaining market competitiveness (Figueira. al. 2018 Fontaine al. 2019). However,

---

Published in Transactions on Machine Learning Research (09/2024)
No domination
Comp1 dominates Comp2
G3
08
CG
Comp1 Comp2
Comp2
Comp2
Figure 1: Radar chart comparison of two team compositions across matchups with six different opponents. The left panel illustrates scenario with no domination, where both compositions exhibit their strengths against specific opponents. The right panel shows where Compl dominates Comp2, achieving higher win rates against all opponents, illustrating clear dominance in overall performance.
the key to optimizing player engagement and competitive fairness lies in maintaining reasonable strength relations among diverse team compositions a challenge for both players aiming for victory and designers striving for balance (Levkoff 2014 Bakkes et al., 2014 Beyer et al 2016).
A quantitative mcasure for game balancing is thus essential for addressing this challenge. Currently, win or success rale, use rate, or even the entropy of strategy distributions are available measures across various game genres, targeting optimizations from detailed game parameters to balle- matchmaking among players
(Morosan & Poli 2017 Hunicke] 2005 Rupp et al.] 2023 Nikolakaki et al. 2020 Pendurkar et al., 2023). However, the prevailing reliance on these measures for balance assessment overlooks critical factors such player skill variability and the counter relationships between compositions, rendering evaluations imprecise. Traditional player skill ratings, including Elo rating, TrueSkill, and Matchmaking Rating, predominantly
focus on individual prowess, leaving gap in the strength assessment of team compositions (Elo 1966;
Herbrich et al. 2006 Pramono et. al. 2018).
To better understand strength relations in compositions and analyze game balance, we pose the question: 'How many compositions are not dominated?' If a composition shows no advantage over others, it could be considered redundant. Hence, our goal in this paper is define measures that answer this question. We first integrate the Bradley-Terry model with Siamese neural networks (Bromley et al., 1993) to predict the strengths of team compositions from game outcomes under the competitive scenario (Bradley & Terry 1952 Li et al. 2021). This scalar strength rating helps us identify the strongest or dominating composition more effectively with the numerical max operation compared to the comparison operation over all compositions. However, a single scalar strongth often fails to provide precise predictions due to players potentially altering their playstyle under different stales (Lin et al., 2021] or the inherent intransilivity present in competitive scenarios (Chen Joachims 2016 Balduzzi et al. 2018). Accurate predictions often consider cyclic dominance, such the Paeck-Papr--Siisoor dynamic, which the Bradley-Teore Terry model does not capture. By analyzing discrepancies between actual outcomes and Bradley-Tene model predictions, we learn a counter table through neural discrete representation learning (van den Oord et al. 2017), thereby enhancing prediction accuracy and offering insights into counter dynamics without specific game knowledge. During the learning of counter tables, we found that vanilla vector quantization (VQ) training leads to poor codebook utilization (Zhang et al., 2023), especially in small codebook sizes; hence, we proposed a new VQ Mcan Loss to improve codebook utilization for this new use case. Leveraging these methods, we define new measures of game balance for counting non-dominated compositions that simple win rates face challenges in computation due to high time complexity.
First, we establish two measures for balance by counting the non-dominated compositions: Top-D Diversity, which counts playable compositions given a tolerant win value gap, where the tolerant gap is defined by game designers and can be due to factors like skill or luck that make players willing to play those compositions; and Top-B Balance, which considers counter relationships non-dominated compositions, i.c., how many meaningful counter relationships exist in the game. Next, we introduce the learning of composition strength and counter relationships, reducing the space complexity of
Our contributions are threcfold:
counting
2

---

Published in Transactions on Machine Learning Research (09/2024)
analyzing composition strength relations from ( to O(N+M)), where N is the number of compositions, and M is the category count of the counter table. This reduction in space complexity is crucial not only for storage reasons but also for generating a feasible size of balance report for game designers. Additionally, the time complexity of Top-D Diversity shifts from O(N2) to O(N) and Top-B Balance from O(N²) to O(N + M To clarify, this time complexity is only for the strength relationship analysis. The time for collecting game records and obtaining the strength prediction models not included in this complexity as it depends on how many game records the game designers plan to collect within given time period and does not necessarily increase with the number of compositions. Lastly, the rating and counter relationships derived from learning align with the experiences of human players without requiring specific game knowledge.
We validate our methods across popular online games such as Age of Empires II, Hearthstome, Brawl Stars, and League of Legends, demonstrating precision on par with pairwise strength predictions using neural net- works and also showcasing better generality compared to tabular statistics. Our methodology not only exhibits broad applicability but also underscores its potential to transform the evaluation and design pro- cesses of game balance. Furthermore, we believe these balance measures are not limited to games, as various competitive scenarios includiin sports, movie preferences, peer grading, and elections -exionn ity in comparisons similar to games (Chen & Joachims 2016). Additionally, the strength mcasurement of recent large language models (LLMs) also incorporates PvP paradigms (Zheng et al. 2023
exhibit intransitiv-
2
Game Balance
Game designers are tasked with devising engaging mechanisms and numerical frameworks that enhance player experiences (Schell 2008). Developing an immersive game loop not only encourages participation but also assists players forming a mental model of the game's mechanies (Scllers) 2017). Designers often
apply the Yerkes-Dodson law to optimize player satisfaction, suggesting an optimal arousal level for peak
performance that aligns in-game challenges with player skill progression (Dodson 1915 This dynamic
interaction is crucial for maintaining players in state of mental flow (Csikszentmiihllyi
1990 where game
balance plays pivotal role in sustaining appropriate levels of difficulty and challenge.
As a critical research field within game design and operations (Schell 2008 Novak et al. 2012 Sellers 2017], game balance significantly influences player engagement through diverse strategies and playstyles. It extends beyond mere difficulty adjustments to encompass strategy, matchmaking, and game parameter tuning (Becker & Görlich, 2020 Understanding balance definitions and metries is vital for effectively addressing these components. Traditional metrics such as win rate, win value difference, and game scores have driven the evolution of game balancing techniques, refining the interplay between game mechanics and player satisfaction (Jaffe et al.) 2012 Budijono et al. 2022 Mahlmann et al. 2012).
In PvP scenarios, win value estimation is a common approach, with values often normalized to scales like [0,1] or [1,1] to simplify payoff calculations between competitors (Budijono et al. 2022). However, calibrating the strength of composition with win values typically requires comparisons against multiple opponents
(Fontaine et al. 2019). While strength rating systems like Elo, TrucSkill, and Matchmaking Rating can
identify strength from single scalar rating and suggest greater strength with higher ratings (Elo 1966;
Herbrich et al.) 2006 Pramono et al. 2018),, capturing intransitivity or cyclic dominance in scalar ratings is challenging. This necessitates multi-dimensional ratings (Chen & Joachims 2016 Balduzzi et al. 2018
which reintroduce complexity into balance analysis. Thus, this paper aims to propose a solution that considers intransitivity while maintaining feasible complexity in balance analysis.
Acquiring accurate game data is also crucial for balance analysis, often involving the deployment of rule- based agents during early development phases and integrating human testers later to capture realistic gameplay data. Advances in artificial intelligence, demonstrated by AlphaZero's performance in board games, have enabled lcarning- based agents to contribute to game balance data collection (Tomašev et al. 2022 Com- munity discussions about strategies also provide valuable insights, often grounded in game theory principles or defining some empirical relationship graphs by humans to explain the game scenarios (Schmitz) 2022) Hernández et al., 2020). Although the entropy of a strategy reaching Nash equilibrium can serve as a mca- sure of strategic balance (Pendurkar et al. 2003), computing Nash equilibrium policies at the game action level in complex games is resource-intensive, posing a challenge for practical application in the game design
3

---

Published in Transactions on Machine Learning Research (09/2024)
loop (Bowling et al., 2015 Perolat al. 2022 Although simpler alternative is using the idea of train-
ing adversarial agents or exploiters to identify the weaknesses of main playing strategies (Reis et al. 2024 Vinyals et al,, 2019), using rule-based agents or human players as the data source for game balancing is usually more affordable and remains the main approach.
With a comprehensive understanding of game balance, this paper focuses on analyzing balance directly through win-lose outcomes from human players and counting the number of meaningful compositions, par- ticularly in two-team zero-sum PvP games. Given the variability of opposing team compositions in matches, our exploration spans multiple game types, from the civilization choices in Age of Empire II to hero com- binations in League of Legends. Our methodology confronts the challenge of cataloging and evaluating an extensive array of possible team compositions, aiming to enhance the understanding and application of game balance. Before introducing our methods, let us formally define the target, 'domination", in PvP balance analysis.
Definition 2.1. Define Win : C2 + w as way to estimate the winner, where e and e2 are the compositions of players and 2, respectivcly, and w E R, w E [0. 1] the estimated win value.
Proposition 2.2. We say composition 61 dominates 02 over all compositions c if Win(cr,c) > Win(e2,c).
When Proposition 2.2 is true, 02 is considered useless in terms of win values because ej can perform better than 02 in all cases. Tf game designers can validate all compositions with Proposition 2.2 they can analyze game balance by identifying overly strong useless compositions. If some compositions are very weak meaningless, leading to most compositions being able to defeat them 100% of the time, thus violating the domination relation, designers can either mamually eliminate these compositions from the set of all compositions c or iteratively eliminate dominated compositions by running Proposition 2.2 several times.
However, the time complexity of validating Proposition 2.2 pairwise win value estimation Win(c1, 02). We will try reduce this complexity with approximations later.
O(N)) over N leam compositions with a
3 Learning Rating Table and Counter Table
For understanding the strength relations between compositions (comps) and performing efficient balance analysis, need to quantify the strength and counter relationships first. Our methodology begins with the application of the Bradley-Tery model to allocate scalar value representing the strength of each comp based on win estimations. This process is elaborated upon in Section 3.1 To tackle the issue of cyclic dominance or intransitivity of win values efficiently, epitomized by the Rock-Paper-ee Paoe--aaprssssssors dynamic, we devise a counter table. This involves examining the variances between actual win outcomes from specific comps and the predictions made by the Bradley-Tere Terry model, a process detailed in Section Furthermore, the overarching framework that integrates these components into our learning process delincated in Scction 3.3
3.1 Neural Rating Table
Win rates in PvP games, while useful as a conventional metric, do not fully encapsulate the actual strengths of individual players or team compositions. A player's or comp's true prowess is better reflected in their ability to triumph over comparable opponents, contribute equally to the win rate but signify different levels of strength. The Elo rating system, commonly utilized in chess and similar two-player zero-sumn gamess, offers scalar strength rating for enlities, aligning with the principles of the Bradley-Tery model (Elo 1966 Bradley & Terry 1952). This model predicts the probability of player i defeating player j, as delincated in Equation
victories against both weaker and stronger opponents
%
P(i j)
% 73
where Thr represents the positive real-valued strength of player x. To manage the scale of 7, it is often reparameterized using a rating value À in an exponential function, as shown in Equation 2
txi
P(i j) ed + ex
(2)
4

---

Published in Transactions on Machine Learning Research (09/2024)
Adopting this model, treat comps analogously to individual players, estimating each comp's strength to predict win probabilities. Given the impracticality of analyzing an extensive N x N win rate table for large number of comps, we harness the Bradley-Terry model in conjunction with neural networks to overcome this challenge. Our approach employs a Siamese noural network architecture to deduce the ratings e^ for each comp, utilizing mean square error (MSE) as a regression loss function for model approximations. In our carly experiments, we tried using binary cross entropy as the loss function for its probabilistic nature. However, this approach encouraged the rating values to become very large and prevented the model from converging, similar to using hinge loss. Therefore, we focused on using MSE for stable training.
This integration allows our neural network to learn the rating table Rg from match outcomes, assigning a rating to each comp through (e(c). The ratings are computed using an exponential activation function to ensure appropriate scaling. The loss function, focused on match outcome Wm, is formalized as follows:
Rolem,)
Ln. = B(D(Wm. m. cdmi + emm ) B[D(Wm: Ro (Cm,) + Ro Ro(g))) Ro( )]-
By adopting this methodology, our network efficiently processes diverse comp combinations, offering robust and scalable solution for predicting team composition strengths. We can efficiently identify the strongest composition by tracing the ratings over all compositions with time complexity of O(N).
3.2 Neural Counter Table
Within the framework of adapting the Bradley- model through neural networks, we can list the strength of all N team compositions with a space complexity of O(N). However, the precision of strength relations provided by this method may not match the precision afforded by direct pairwise comparisons for each composition, process that inherently bears space complexity of O(N3). While theoretically feasible via neural networks, such direct prediction incurs a high space complexity, making it challenging to check these ratings and analyze balance, especially with a large N.
The phenomenon of cyclic dominance or intransitivity of win values, a common challenge in analyzing game balance, introduces further complications. An N x N counter table, which would record adjustments from rating predictions to enhance accuracy, becomes impractical due to its high space complexity and cognitive load. In practice, players intuitively grasp counter relationships without the need for exhaustive memorization of large tables. To navigate this, we propose more managcable M x M counter table that serves as an approximation of the full N x N relationships, where M represents a manageable mumber of discrete categories. Beginning with a minimum of to capture basic cyclic dominance patterns, M can be adjusted to strike a balance between prediction accuracy and table interpretability.
For the task of learning discrete categories, we employ Vector Quantization (VQ), a technique of neural discrete representation learning celebrated for its effectiveness (van den Oord et al. 2017). It acts as end-to-end analog to K-means clustering within neural networks, primarily introduced in the context of VQ-VAE (van den Oord et al. 2017 Baevski et al. 2020 Our goal diverges from traditional autoencoder objectives; rather than reconstructing inputs, our focus is on developing a counter table that learns from the residuals between direct win predictions and those derivod from the Bradley-Tere model.
3.2.1 Neural Discrete Representation Learning
Before introducing our design for learning the counter table, we first discuss popular discrete representation learning method with neural networks, VQ-VAE (van den Oord et al. 2017). In scenarios that require discrete representation, clustering is a common approach, with k-means clustering being widely used method for several decades (MacQueen el al.) 1967). This clustering idea is based on finding k reference points in
the feature space to represent corresponding groups of actual features using the nearest neighbor method. However, obtaining an effective feature space from raw observations for this clustcring process critical problem. With the growth of deep learning, variational autoencoder (VAE) (Kingma & Welling 2014) was proposed to learn effective latent. feature spaces for several tasks.
5

---

Published in Transactions on Machine Learning Research (09/2024)
Building the ideas of autoencoders and k-means clustering, VQ-VAE uses the concept of preparing embedding codebook and employing the nearest neighbor method to convert continuous latent features into the discrete indexes of the codebook, thereby obtaining the discrete representation. Afterward, we can restore the discrete representations back to continuous for decoding tasks. This discretization process can be formulated with the lollowing notations: Given an observation and its latent features ze through encoder layers and an embodding space = -.,".., eek with size K (codebook), we can define the following probability function for mapping to discrete space:
{
for k; = minlm -eyll²
( klo)
otherwise.
Through this mapping, can train discrete encoder in an end-to-end manner without the need for feature engineering first as in m-menns clustering.
For training this neural network, we use the following loss functions:
Lree = E(D(o.o')]. Leg E[D(sglze), sg)1. Lcommit = E[D(ze: sg(zg])
(5)
Here, D is distance function, with mean square error (MSE) being a common choice. ze and bq the latent codes before and after nearest neighbor replacement, respectively. The sg[-] denotes the stop-gradient operator. The standard VQ-VAE minimizes the combined loss function L - Liee + Log + x Leommit; where B is a weight term that encourages the encoder to produce latent codes closer to discrete representations.
For applying this loss the encoder, we can use the gradient copy trick with the chain rule, as follows:
O.rec 3zg Deencdder
Oze
TLcommit
V Beneoder
x
B x 00 Oncoodrr
(6)
For applying this loss to the codebook, it is treated as simple regression optimization problem.
3.2.2 Applying Vector Quantization to the Counter Table
After a brief understanding of vector quantization with neural networks, we extend this idea of discrete representation to our counter table application. Given the symmetrical nature of residual win values and our aim to classify compositions into M discrete categories, we utilize Siamese network architectures for both the learning of discrete representations and the prediction of residual win values, illustrated in Figure The residual win value, Wress is defined as:
Ro (m(.))
W Wree(Cma: Cmy Re) = W.. Ro + Ro(Cnny)
(7)
The counter table, denoted Co, comprises discrete encoder Ceg and residual win value decoder C'd.. functioning as follows:
Calem, Cm2) (Cm,(Cm,)) Ceo(Cm,)).
(8)
Here, every output of (εe( belongs to Chp, the embedding space optimized for vector quantization.
The core loss function focuses on the residual win values:
Lires E(D (eD(Wrss(Cmm (Cmpp Cmyy Ro), ColCm, Cmy ))
(9)
complemented by vector quantization loss:
D( D(ze(Cmm): 2g [g + D( 2g (Cm,))
Log
E
(10)
where ze represents the latent code before vector quantization, and 2y denotes the code pust-quantizationn

---

Published in Transactions on Machine Learning Research (09/2024)
In application, require minimal discrete state space to learn the counter table effectively. We observed low utilization of vectors within the embedding space Cko, leading to unselected vectors during training, which cannot construct a comprehensive M x M counter table. This low codebook utilization problem is common in VQ, and there are many techniques to improve it (van den Oord et al., 2017 Yu et al.
2022 Shin et al. 2023 Reg-VQ Zhang al. (2023) specifically discusses this codebook
problem and suggests adopting KL divergence in stochastic VQ and leveraging Gumbel sampling over convolutional feature blocks. However, this raises the question of whether there is a simple and easy way to guarantee codebook utilization improvement conceptually and can be easily implemented for the vanilla VQ process for our simple usage. To handle this, we propose new loss term for embedding vectors, termed VQ Mean Loss, which calculates the distance from the mean vector in the embedding space to the continuous latent code Ze. This mechanism can be seen as another K-means clustering, encouraging the vectors in Ckk to gravilate towards že, thus increasing their likelihood of being selected by the nearest neighbor in subsequent iterations. We define this additional loss as:
For a more concrcte explanation, we provide an example in Appendix A.1
Lmnaan- = E (( ex) + (Mm)(CCm)))) ),&x)
where ε₁ =
Σ ck.
(11)
2
M EgECkp
The gradients for each component in the counter table learning process are calculated with the hyperparam- eters AN and Byr. 8N is utilized in VQ-VAE to ensure the continuous latent codes ze closely align with their quantized versions Zg: and we use IM to activate Lmean, respectively:
Tores
Oze
ÖT.g VCkg = oCeg
+ BM x TTmean VCdg = OCdg
θTres
VCcg = 0zg aCeg
x
+ BN x
(12)
aCke
0Ckg
By employing this M x M counter table, win values We that consider counter relationships can be computed via Equation 13
Ro(CmL) + W Wree(Cmus Cm²)) (C Cmas) Re(Cm)) + Rg(Cm;)
(13)
This approach reduces the space complexity of analyzing strength relations for N compositions from O(N2)
to O(N + M²). When M is a small, constant value, the complexity can simplify further to O(N).
3.3 Learning Procedure
The methodology underlying the construction of the rating and counter tables is encapsulated in the learning framework depicted in Figure 3 This framework requires a datasot consisting of match results, including the team compositions of the competing sides alongside the ultimate win-lose outcomes. The representation of these compositions is adaptable, ranging from simple binary encodings to more nuanced feature descriptions, according to the preferences and requirements set by game designers.
Crucially, the derivation of the Neural Counter Table Co is predicated on the prior establishment of the Neural Rating Table Rg. This sequential approach ensures that the foundational ratings of team compositions are accurately determined before their interrelations and counter dynamics are analyzed. The development and refinement of these tables pave the way for the introduction of novel measures aimed at enhancing diversity and balance within the gaming environment. A comprehensive discussion of these newly introduced balance measures is forthcoming in Section 5 while the effectiveness and precision of the rating and counter tables will be evaluated in Section
4 Accuracy of Strength Relations
With our raling table and counter table, we can approximate the win value of a match given two compositions and identify the strength relations for balance. In this section, we examine the accuracy of strength relations using these tables across different games and investigate the impact of the hyperparameters fN and 8M on counter table training. There are models for each method in our experiments, each trained from a different random seed. The results in the tables are the average values of these models.
7

---

Published in Transactions on Machine Learning Research (09/2024)
Team Comp A
Team Comp B
Encoder
Encoder
Shared Weights
Ze (CA)
Nearest Neighbor
Ze (CB)
Counter Category A
Embedding Vectors
Counter Category B
Restore
Restore
Zq (cn)
Zq (CB)
[Zq (cx), 2q (cx)
[Zq (GB), 2q (ca)
Ceo
FC Layers
FC Layers
tanh
tanh
Xg
X2
X1 - X2
2
Cd8
Residual
Win Value Prediction
Figure 2: Architecture of the Neural Counter Table Cg. The diagram illustrates the process of estimating residual win values between team compositions. Team Comp A and Team Comp B are encoded into latent reprosentations (c(c)) and (c(c)) through sharod encoder weights. These latent codes are then quantized into embedding vectors (y(c and 2y (cB) using the nearest neighbor search. The embedding vectors are classified into counter categories A and B. The decoded quantized vectors [=g(e)), =y(C=)] and [zy(co), 2y (ca)) are fed into fully connected (FC) layers with tanh activation functions to produce intermediate values æ1 and æ2- The residual win value prediction is calculated as the average of the differences between these intermediate values, providing an estimation of the residual win value W Wres- The dashed layer implies shared weights.

---

Published in Transactions on Machine Learning Research (09/2024)
Team
Win-Lose Match Outcomes
Comp
Team Compositions
Team
Rating Encoder
Comp Rating
Shane Weights
Bradley-Terry model
Win Value Pradiction
(Rating Encoder)
Comp B
Rating
Neural Rating Table Ra
Category
Comp A
Encoder
Category A.
Residual Value
Shared
Residual
Team
Category
Counter Category
Prediction
Encoder
Naural Counter Table Co
Figure 3: This diagram illustrates the learning procedure for deriving the Neural Rating Table Rg and the Neural Counter Table Co. The process begins with tcam compositions (Team Comp A and Team Comp B) and their corresponding match outcomes (win-lose results). In the first stage, team compositions are processed through a shared rating encoder to obtain composition ratings (Comp Rating A and Comp Rating B). These ratings are then utilized in the Bradley-Terry model to predict win values, forming the Neural Rating Table Rg. In the second stage, these compositions are further processed through a shared category encoder to determine counter categories. The residual win value predictor uses these categories to refine win value predictions, accounting for cyclic dominance, thus forming the Neural Counter Table Co.
4.1 PvP Games
To assess the accuracy strength relations with our tables, we constructed simple games that emulate practical game scenarios for experiments. Additionally, we applied our methods several open-access sports game records confirm their real-world applicability.
4.1.1 Simple Combination Game
A simple combination game was designed with elements, cach assigned a score equal its index from to 20. A comp consists of three distinct elements. The score 8, of a comp is the of its elements* scores, and the win-lose outcome is binary, sampled via the probability function P(e > e2) [e., +( There are C = 1140 possible compositions in this game. The dataset, comprising 100,000 matches, was generaled by uniformly sampling two comps.
(#., )
4.1.2 Rock- Back-Paper-Scissors
We adhered to the Rock-Paper-Scinne rules, only compositions with win values of 0/0.5/1 for lose/tic tie/win, respectively. The dataset, consisting 100,000 matches, generated by uniformly sampling.
4.1.3 Advanced Combination Game
This game combines the simple combination game with Rock-Papess Rock-Paper-Sciisors rules. The primary rule mirrors the simple combination game, with an additional rule: = se mod 3, assigning T as the counter category of the comp, with 0/1/2 corresponding to Rock/ Rock/Paper/S5i /Paper/Scissors. A winning Rock-Paper-Seissors comp receives +60 score bomus during comp score calculation. There are still C 1140 possible compositions in this setting. The dataset consists of 100,000 matches generated uniformly.

---

Published in Transactions on Machine Learning Research (09/2024)
4.1.4 Age of Empires II (AoE2)
Age of Empires is a popular real-time strategy game. We utilized the statistics (as of January 2024) from aoestale an open-acoess statistics website. The game features 45 civilizations (comps) in Iv1 random map mode across all Elo ranges. Thus, there are 45 compositions in this game. Further combinations of civilizations in team mode or specific maps are not discussed in this paper. The dataset contains 1,261,288 matches.
4.1.5 Hearthstone
For Hcarthstone, popular collectible card game, we accessed the statistics (as of January 2024) from HSReplay an open-access statistics website. We considered 91 named decks as compositions for standard ranking at the Gold level. Therefore, only up to 91 compositions were used, and the detailed hero or card selections within these compositions were not considered for simplicity. The datasct comprises 10,154,929 matches.
4.1.6 Brawl Stars
Brawl Stars is a popular Multiplayer Online Battle Arena (MOBA) game. We focused on the Trio Modes of Brawl Stars, where teams of three compete for victory. Data were sourced from the 'Brawl Stars Logs & Metadata 2023' on Kaggle, initially collected via the public API. With 64 characters, 43 maps, and 6 modes, the composition count could reach C3* x 43 x 6, i.e., the maximum number of compositions can reach 10,749,312. The dataset includes 179,995 matches, with 94,235 unique compositions observed.
4.1.7 League of Legends
For League of Legends, renowned MOBA game with 5-on-5 team competition, used the 'League of Legends Ranked Matches" dataset from Kaggle, which features 136 champions. Thus, the maximum number of compositions is C = 359, 933, 112. The datasct covers 182,527 ranked solo games with 348,498 unique compositions observed, which implies that almost all compositions are different.
4.2 Comparisons of Strength Relation Prediction
To better understand whether win value predictions can provide accurate strength relations, we examine the accuracy of the strength relation classification task Baakker/samm//srrnggeii rather than the prediction error of win values. For example, if there are two compositions, A and B, and the oracle win value is Win the actual outcome we care about is whether A is stronger than B. Now, consider two approximations: Win'(A,B)=0.49 and -006 It. is clear that Win' has a smaller absolute error (0.06) compared to Win" (0.07), but Win' suggests the wrong strongth relation.
In this strength relation classification task, the win value falls within the range of [0.499, 0.501), we designate the prediction as the same; a value below 0.499 indicates weaker, and a value above 0.501 indicates stronger. The classification label is calculated based on the average pairwise win value in the dataset. For example, if CA has a 60% average win value against CB in the dataset, CA is deemed stronger when calculating accuracy. All models are approximated with neural networks and trained for 100 epochs on datasets using 5-fold cross-validation. A linear decay learning rate from 0.00025 to 0 over 100 epochs with the Adam optimizer employed. We then compare the following five methods of win value prediction and provide their definitions with formulations Section A.4.1
WinValue: Prodicts the win value for given composition and compares the win values of the two compositions to determine the winner. If the absolute value of the win value difference not greater than 0.1%, they are considered to be at the same level. This is common method in game statistics that does not require maintaining a large table.
http:://aoestate..it https://hsrep..t net/
10

---

Published in Transactions on Machine Learning Research (09/2024)
Table 1: Accuracies (%) in training (above) and testing (below) for various games, illustrating the effective- ness of NCT with M 81 in achieving high prediction accuracy across different games.
WinValue
PairWin
BT
NRT
NCT M-81
Simple Combination
64.5
71.2
63.9
64.8
66.4
Rock- Rock-Paper- Scissors
51.3
100
51.3
51.3
100
Advanced Combination
57.7
83.5
56.6
57.9
79.4
Age of Empires
68.7
97.3
68.7
68.7
97.7
Hearthstone
81.1
97.8
81.4
83.4
97.4
Brawl Stars
90.2
94.3
53.2
95.9
97.2
League of Legends
79.6
78.9
54.0
88.2
90.9
Simple Combination
64.7
61.8
65.5
64.9
63.9
Rock-Paper-SSissonn
51.1
100
51.1
51.1
100
Advanced Combination
56.5
79.1
57.5
56.5
79.7
Age of Empires II
64.5
75.7
64.5
64.5
75.4
Hcarthstone
80.9
95.4
81.1
81.2
94.8
Brawl Stars
79.7
82.4
53.0
82.8
83.4
League of Legends
51.1
50.9
53.6
51.1
51.0
2. PairWin: Directly predicts the pairwise win value. Some game statistics provide this kind of result when the number of compositions is not too large, and it is a straightforward measure to examine counter relationships. If we have sulficient match results, this method represents the upper bound of strength relation accuracy.
3. BT: Utilizes linear approximation to perform the Bradley-Terry model. This method assumes the rating of a composition can derived from the sum the element ratings within the composition. Common generalized Bradley- Terry models for team setups or Elo ratings in team games use this kind of approach (Coulom 2007).
Merleyy-erry
4. NRT: Employs non-linear approximation to perform the Tradley-Terry model. In many games, combinations of elements in a composition will change the strength of the composition non-linearly,
5. NCT: Enhances NRT with an additional neural counter table of size M M.
Table 1 presents the accuracy of the strength comparison task. Notably, NCT with M = 81 achieves accuracy comparable to PairWin across all games. In games with complex compositions, such as Brawl Stars and League of Legends, a non-lincar approximation essential for estimating comp strength. For games with explicit. counter relationships such as Rock-Paper-Seissorrs the Advanced Combination Game, and Age of Empires II, which exhibit a significant accuracy discrepancy between PairWin and NRT counter table offers a viable solution. The simplistic win value estimation approach, WinValue, usually does not provide the best strength predictions. These results affirm the precision of our rating and counter tables in predicting win values. Notably, in Table 2] as the parameter M increases, so does accuracy, allowing for detailed tracing and analysis of complex counter relationships through the counter table. We provide further discussions regarding the results of counter tables in Appendix A.3
Additionally, we can observe these accuracies to analyze the propertics of the obtained gaming results. the difference accuracy between training and testing small, it implies that there is no significant overfitting and the strength relations be generalized to matches not observed. However, in cases where there is
11

---

Published in Transactions on Machine Learning Research (09/2024)
Table 2: Accuracies (%) training (above) and testing (below) for various games with different sizes of counter tables. As the size of the counter table increases, we can obtain better accuracy. Additionally, we can use the difference in accuracy between PairWin and NRT to identify the magnitude of counter relationships in the game, these cases that single scalar rating system cannot handle.
PairWin
NRT
NCT M-3
NCT M-9
NCT M-27
NCT M-81
Simple Combination
71.2
64.8
64.8
65.2
65.8
66.4
Rock-Paper Saaper-Scissors
100
51.3
100
100
100
100
Advanced Combination
83.5
57.9
57.9
79.4
79.8
79.4
Age of Empires
97.3
68.7
68.7
73.1
83.8
97.7
Hearthstone
97.8
83.4
81.3
85.4
91.7
97.4
Brawl Stars
94.3
95.9
96.3
97.3
97.2
97.2
League of Legends
78.9
88.2
89.5
91.6
92.6
90.9
Simple Combination
61.8
64.9
64.9
64.4
64.2
63.9
Paock-Pape--Siisoors
100
51.1
100
100
100
100
Advanced Combination
79.1
56.5
56.5
79.7
80.1
79.7
Age of Empires
75.7
64.5
64.5
67.7
72.5
75.4
Hearthstone
95.4
81.2
81.3
85.2
91.3
94.8
Brawl Stars
82.4
82.8
82.9
83.3
83.3
83.4
League of Legends
50.9
51.1
51.1
50.9
51.0
51.0
clear overfitting, such as in League of Legends, it suggests the need for more match results to generalize the known strength relations to unknown scenarios. Since League Legends includes a hero ban and pick phase before match starts, players tend to prefer compositions that can counter their opponents and aim improve their win rate. This increases the difficulty of win rate prediction for unobserved cases. The large possible composition space also increases the complexity of accurate model training. For such game cases, recommend collecting more game results for training. Nonetheless, in the training datasets, as our goal is to understand these relations. Initial insights from observed cases can be valuable for early game balancing, although conclusions drawn from these datasets may not necessarily apply to unobscrved sccnarios.
still analyze the strength relations
4.3 Counter Table Utilization
Given the need for a counter table for strength relation analysis, we adopt a vector quantization process in our NCT training. There is an issue with low codebook utilization when the state space is extremely small. We introduced VQ Mean Loss to maximize the utilized M. For vector quantization, as described in Section 3.2 the standard hyperparameters are to 3, 0.01 and BM = 0.25. We explore different configurations of these hyperparameters in Age of Empires II using NCT M-27 since it game requiring large counter table for better strength relation accuracy, as shown in Tables 3 and We found that the commonly suggested 3x 0.25 fvan den Oord et al.) 2017 leads to low utilization. Thus, we selected nearly zero cocfficient Ay = 0.01 to perform regular VQ training. However, even with AN 0.01, if we do not introduce the VQ Mean Loss (set BM = 0), the utilized M is still far from the upper bound of 27. We suggest using 3M = 0.25 for better accuracy and codebook utilization. Also, a coefficient greater than for VQ Mean Loss not reasonable since it suggests gravitating the mean embedding more than the nearest embedding, which breaks the original idea of VQ and results in worse performance.
12

---

Published in Transactions on Machine Learning Research (09/2024)
Table 3: Training accuracy and the number of utilized categories (M) in AoE2 M=27 under different N with a fixed PM 0.25. The common PN in VQ-VAE is 0.25.
Setting
Accuracy (%)
Utilized M
BN 0.01
83.8
26.0
fy = 0.125
71.4
5.4
BN = 0.25
68.7
1.0
Table 4: Training accuracy and the number of utilized categories (M) in AoE2 M-27 under different SM with fixed By 0.01. Too small too large fM cannot provide good codebook utilization.
Setting
Accuracy (%)
Utilized M
BM 0
76.6
13.8
3M = 0.125
83.6
26.0
3M = 0.25
83.8
26.0
3M = 0.5
83.4
25.6
BM 1.0
81.0
21.6
4.4 Tabular Version of Baselines
In Section 4.2 all baselines we used are trained from neural networks for better generalizing unseen compo- sitions. One may ask why not conduct a simple labular approach like common rating or statistical analysis; thus, we also report the tabular version of WinValue, PairWin, and also Elo rating and a multidimensional variant, mElo2 (Balduzzi al. 2018
We test the following five lypes of methods:
WinValue N It the same as WinValue, but using a tabular method get predictions. other words, this method averages the game results directly report the average win values instead of using an approximation from a neural network. For those unseen compositions on any side of players in the test dataset, we set the prediction to undefined and always get wrong prediction since there is no default strength value in the method.
PairWin N-T:
is the same as PairWin, but using tabular method get predictions. other words, this method averages the composiion--uy--omppsttoo game results to give the predic- tion. For those unseen matches, we also set the prediction to undefined and always get wrong prediction. We can imagine that this method would have the best training accuracy but very bad generalizability since training with tabular approximator can have minimal approximation error but no gencralization.
3. Elo N-+:
We apply the standard Elo rating method on compositions. Each composition is player, and the initial rating is 1000. The constant K for updating the Elo rating is 16. We use NRT as the baseline of Elo since they are all derived from the Bradley-Tere model but use different implementations.
4. mElo2: We implement the mElo2 proposed by Balduzzi et al. 20188 which assigns each composition
a scalar rating and two-dimensional vector c. The initial rating is 1000, and the update step K is 16. For the initial vectors of c, we follow a public implementation provided by Lazewatsky (024 uniformly sampled from a real value range [-10, 10).
5. NCT: Enhances NRT with an additional neural counter table of size M M.
These tabular methods share the same training process as neural network approaches, including accessing 100 epochs of training data and the random swapping of compositions in match and corresponding win outcome
13

---

Published in Transactions on Machine Learning Research (09/2024)
Table 5: Accuracies (%) training (above) and testing (below) with different baselines.
WinValue N-T PairWin N-T
Elo N
mElo2
NCT M-81
Simple Combination
64.5 + 64.5
71.2
99.9
64.8 + 64.3
56.6
66.4
Rock-Papess Kock-Paper-Seissors
51.3 + 51.3
100 + 100
51.3 + 73.3
100
100
Advanced Combination
57.7 - 57.7
83.5
99.9
57.9 57.1
52.7
79.4
Age of Empires
68.7 + 68.7
97.3 + 100
68.7 - 53.1
51.2
97.7
Hearthstone
81.1 + 81.1
97.8
98.0
83.4 - 74.8
61.4
97.4
Brawl Stars
90.2 + 95.8
94.3 + 99.7
95.9 + 98.0
97.5
97.2
League of Legends
79.6 - 99.9
78.9
100
88.2
100
100
90.9
Simple Combination
64.7 64.7
61.8 + 6.5
64.9 + 64.4
57.2
63.9
Rock- Patkk--ppp--Scssoor
51.1 + 55.8
100 + 100
51.1 + 73.6
100
100
Advanced Combination
56.3 + 56.7
79.1 + 8.2
56.5 + 56.1
51.3
79.7
Age of Empires II
64.5 + 64.0
75.7 75.4
64.5 + 52.4
51.0
75.4
Hearthstone
80.9 + 81.5
95.4 + 95.0
81.2 + 74.9
61.1
94.8
Brawl Stars
79.7 + 69.8
82.4 69.3
82.8 - 77.8
83.1
83.4
League of Legends
51.1 -
50.9 + 0
51.1 - 6.3
50.2
51.0
adjustment. The results in Table 5 show that labular methods can have better prediction on training data since they have less approximation error. However, they do not have generalizability and may fall into severe overfitting. If we focus on popular online games, using the neural network version of PairWin or NCT=81 as the win value predictor is still a better choice.
5 New Balance Measures
The creation of rating and counter tables allows us to devise new ways to measure balance in games, going beyond simple win rates to consider domination relations as described in Proposition 2.2 In games where two players compete against each other, a common goal is to equalize win rates, aiming for each player to have a win rate near 50%. This is easier to achieve real-time games with symmetric settings for each player, but it harder in turn-based games because the player who goes first often has an advantage (Beau) & Bakkes 2016). The main challenge in balancing is determining which player has the upper hand and the extent of their advantage. We propose two new ways to measure balance based on estimated win values and explain how to calculate these measures using our approximations to reduce computational complexity.
Next, we will examine the diversity of comps players might choose in Section 5.1 and identify how many comps might give players an advantage in Section 5.2
First, let us define some important concepts:
Ra(o)) Assumption 5.1. The Tradley-Terry rating function Ra(c) provides estimate of Win Reles)
Proposition 5.2. The composition Ctop with the highest rating Rş (Crop) over rating function Rş is con- sidered to dominate all others with lower ratings.
Considering Definition 2.1 Proposition 2.2 and Assumption 5.1 we can conclude that Proposition 5.2 is
_1_ $2 true because žyナz x2+y when Fı > x2 > O. According to Proposition 5.2 if there is only one composition Ctop with the highest rating, is considered the best choice before considering counter strategics. This information often sufficient for some balancing methods, such as identifying and adjusting the strongest comp (oontaine et al. 2019). The time complexity of identifying Ctop be done in O(N) over N comps,
14

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm Compute Top-D Diversity Measure
Input: neural rating table Rg, top-rated comp Ctops acceptable win value gap G
Output: Top-D Diversity Measure D Initialize count. D + 0
for each comp e in the set of comps do Re(c)
Ra + G 2 0.5 then
D DeD+1
end if end for
whereas traditional win rates cannol. directly provide Ctop- If we average the win rates over N comps, the time complexity is ((V3). In the following sections, we aim to determine how many compositions might be acceptable players compared this top composition and use the new counter table to gain better understanding of balance through domination with counter relationships.
5.1 Top-D Diversity Measure
We are examining how many different game compositions (comps) players might prefer lo play. More choices can enrich the game content for fun and also help designers generate revenue by selling these comps. We want to know which comps players will pick based on their chances of winning. Here are some definitions and assumptions for this measure.
Definition 5.3. Let define acceptable win value gap G, where G R, G [0,
Assumption 5.4. Players think that small difference in win value, up to G, can be attributed to factors like skill or luck, and they are willing to play again under this belief.
Assumption 5.5. Tf comp is considered not dominated by Crap: is considered not dominated by any comps.
Lemma 5.6. Players are likely to choose comps e where Micso))
R(o) G 0.5.
By accepting Definition 5.3 Assumption 5.1 Assumption 5.4 Assumption 5.5 and Proposition 2.2
Lemma 5.6 is true, since comps that meet this condition are considered not dominated by any other comps. We use Algorithm [ to count how many comps meet this condition, and this number represents the game's 's Top-D Diversity measure, where a larger D implies more diverse game content. The time complexity of this algorithm is O(N) over N comps. Without the property of a single scalar rating, the time complexity to check and define win value gaps on pairwise compositions is O(N2).
5.2 Top-B Balance Measure
To further explore game balance, we recognize that the dynamics of counterplay are vital, and it rare have a single dominating comp. Our goal is identify the number of comps that are not dominated by any other comps, considering their counter relationships.
Assumption 5.7. The Bradley-Terry model with the rating function Ra, enhanced with counter table Ca, provides more reliable predictions than using the Bradley-Tere model alone.
Based on Assumption 5.7 derive the following:
Proposition 5.8. A comp Cr dominates 02 if, for every comp c, Win(es,))+Co(eeed) >
However, verifying this for all comps still computationally challenging (O(N3)). To mitigate this, we can categorize comps and record the top comp of each category, leading to the following propositions:
Proposition 5.9. If comps ei and co fall into the same calegory in Co, then e₁ dominates co when Ro(ci) Ro(c2).
Proposition 5.10. comp e₁ dominates c2 and c2 dominates ca, then eo also dominates c3-
15

---

Published in Transactions on Machine Learning Research (09/2024)
Algorithm 2 Compute Top-B Balance Measure
Input: rating table R, counter table Cø, set of all comps
Output: Number of non non-dominated comps B List all comps based on R and categorize them using Co Keep only the highest-rated comp in each category Initialize count
for each top comp e. in each category do
Assume e is not dominated
for each other lop comp d' in other categories do domi + true
for each top comp c" in all categorics do if R(e') Me))((e") Co(c', cd) S Mec)+eer) + Co(c,c") then
R(e)
domi false and break end if end for if domi then
Mark e as dominated and break end end for if is not dominated then
B t B+1 end if
end for
Deriving from Proposition 5.8and and Assumption 5.7
Proposition 5.9 simplifss the determination of domination establishes transitive relationship in domination. These
within the same category, and Proposition 5.
propositions collectively support Lemma 5.11
Lemma 5.11. Given a rating table Ro following the Bradley- Terry model and counter table Co covering comps across M calegories, all non-dominaled comps con be identified among the highest-rated ones in each of the M categories.
After finding the top comp in each category (O(N M)), we use Lemma 5.11 identify non-dominatod comps. This methodology is detailed in Algorithm 2 calculating the Top-B Balance measure in O (MN+M*), where larger B implies more balanced game content.
6 Case Study of Top-D Diversity and Top-B Balance
With our new balance measures, previous works on game balancing, as mentioned in Sections I and can now incorporate these measures to adjust game mechanisms beyond merely achieving 50% win rate in PvP scenarios. In this section, we conduct two case studies using our measures for direct balance change suggestions in Age of Empires II and Hcarthstone, employing our first model of rating and counter tables in the experiments demonstrate an application. The actual ratings and counter calegories of these tables be found in Appendix A.3 We also discuss the case and information for suggesting balance updates with our methods and existing approaches, including win rate observations and natropy-based methods.
6.1 Case Study on Age of Empires
In Age of Empires II, there are 45 civilizations as compositions in 1vl mode. We first examine the Top-D Diversity measure in Table 6(a) The top composition identified was the Romans with a strength 1.08145. The result on Top-D Diversity suggests that to enhance general balance, sctting the win value's standard deviation larger than 4% is reasonable. Such adjustments could be implemented through matchnaking mechanisms, map randomness, game rule variations, etc. A lower randomness level implies imbalance,
16

---

Published in Transactions on Machine Learning Research (09/2024)
Table 6: Top-D Diversity and Top-B Balance in Age of Empires 11 with different settings.
(a)
(b)
Setting
Top-D Diversity
Setting
Used M
Top-B Balance
Training Accuracy
G = 0.01
2
M = 3
1
69.6
= 0.02
9
8
77.0
0.04
25
27
26
86.0
0.08
44
M 81
45
45
98.9
forcing almost every player to choose Romans, especially since it is part of the DLC (requiring purchase for competitive advantage).
Regarding Top-B Balance in Table 6(b) when we assume there are 9 categories considering counter rela- tionships, showed that one category is dominated. According to our ad-hoc analysis in Appendix A.3.1 it an economic powerhouse category, and the top civilization this category is Poles. This indicates the potential necessity enhance civilizations within this category on their economic bonuses to improve balance, as even the best among them, Poles, is dominated by other top civilizations.
When we exlend the size of the counter table to M = 27, Aztecs and Chinese were identified as dominated. This suggests review of the counter relationships within their category might be warranted to discuss potential improvements. Generally, the balance is commendable, with 24 non-dominated civilizations.
When we assume the counter relationships can very complex and it is worthwhile for expert players to memorize a large counter table, we find that there no truly dominated civilization the M = 81 setting, All civilizations are assigned distinct categories and show their advantages in specific matchups. The accuracy of strength relations in M = 81 is 98.9%. This evidence shows that Age of Empires II is balanced when counter relationships are meticulously examined. The game features complex counter loop, allowing for a counter civilization to almost any other. However, there is still room for balance improvement for beginner players if we do not want such a large counter table.
These insights provide game developers with guidance on addressing balance weaknesses in future updates. They also offer players a deeper understanding that even generally strong civilization, like Romans, has specific counter civilizations. Traditional game balance techniques, which often aim for fair win rate (e-g.. 50% in 2-player zero-sum games), might overlook the intricacies of counter relationships and game theory when merely weakening strong comps strengthening weak ones.
6.2 Case Study Hearthstone
When examine another game, Hearthstone, first discard decks with fewer than 100 game records in our dataset to ensure the analysis is not biased by outliers. There are 58 decks remaining after our filtering,
From the Top-D Diversity in Table 7(a) the balance is not good since even with a 4% tolerant win value gap, there are only 3 decks considered not dominated. The top deck is Treant Druid with strength of 1.48915 (please see Figure 11 for the strengths of other decks), and is clearly too strong.
When we check Top-B Balance in Table 7(b) under M 3, Treant Druid dominates the others. If we extend the counter table to M 9 (we provide an ad-hoc category analysis in Appendix A.3.2). the balance is surprisingly good with 9 Top-B Balance. This is because there is a clear counter deck, Aggro Paladin (1.17278), to Treant Druid. Even though Aggro Paladin has a general strength of only 1.17278, it has a strong counter ability to Treant Druid, and all top decks in M = have their advantages.
When we use larger counter table, M 27 or M 81, the game balanced enough since the difference between Used M and Top-B Balance is not significant. This analysis suggests that for this version of Hearthstone, Treant Druid requires specific adjustments. The counter relationships are balanced.
17

---

Published in Transactions on Machine Learning Research (09/2024)
Table 7: Top-D Diversity and Top-B Balance in Hearthstone with different settings.
(a)
(b)
Setting
Top-D Diversity
Setting
Used M
Top-B Balance
Training Accuracy
G = 0.01
1
M = 3
3
81.3
= 0.02
M
9
9
87.0
0.04
27
25
90.6
0.08
M 81
54
53
97.2
6.3 Discussion on Different Types of Balance Measures
When considering game balance measures, the major concerns are the type of information these measures provide and how this information can help modify the game mechanics. We focus on measures with fewer subjective factors, specifically those related improving players' chances of winning. Mcasures dependent on player preferences, such as use rate, learning difficulty, popularity, and other factors, are not included in the main discussion.
Starting with the most common mcasure, win rates, it is very clear and general in PvP games. Whether using a simple win rale or a more detailed win rate with specific opponent compositions, making each composition have similar strength is a common idea (Becker & Görlich 2020). Achieving an average 50% win rate for each composition an average case without considcring its opponents is a specific solution. Designers can check the win rate of each composition and increase the strength of those below 50%, commonly referred to as "buffing" in the player community. For compositions with over 50% win rates, especially those with large advantage, designers may try to weaken their strength, referred to "nerfing" in the player community or develop new specific compositions to counter them. However, these changes may not always align with players' desires for entertainment or satisfaction with game depth. Players often pursue diversity or want to demonstrate individuality with different strategy settings (Rheinberg) 2020). Keeping every setting or composition at the same strength level can violate this intention. Therefore, studying different distributions of strength over win rates can provide various solutions, not just achieving 50% average case win rates, Our Top-D Diversity and Top-B Balance measures also rely win rates but focus different aspects like the tolerant win value gap and the size of mcaningful counter relationships.
Using another possible balance measure, the entropy of strategy, especially strategies that reach Nash equi- librium (Pendurkar et al.) 2023), can be considered another application of win rates. A policy reaching Nash equilibrium implics its opponent cannot change itself to gain more benefits. When balance is defined by maximizing the entropy of this policy, it suggests increasing the strengthh of low sampling probability strategies and reducing the advantages of high sampling probability strategies. This idea is similar to the goal of achieving 50% win rates the same average case strength but defined more complex relationship with Nash equilibrium. However, this idea may have the same limitation achieving 50% win rates since it cannot explicitly differentiate those compositions that share the same strength relations: for example, making all strategies nearly the same. Therefore, Pendurkar et al. (023)) also proposed using a parameter regularization term to trade off the choice of entropy, which may guide parameters to the same strength, and the inherent. diversity of game settings.
Previous measures can help with game balance; however, they cannot guarantee that the updates would not tend to reduce the inherent diversity of the game mechanies since there is usually global optimal solution that sets all parameters for different compositions nearly the same. Although this result is very balanced, it is also boring for players since there is almost one actual composition decorated as several different compositions or at least sharing the same distribution of win values. If we analyze the potential effect of these balance changes from the player's experience angle, would converge to a case with not improved balance since the actual game content would be very similar to one strong composition dominating the game since we do not have study which composition is better, all have the same strength, except the mechanism or playstyle of each composition is different. This raises the question: what result are players pursuing for game balance?
18

---

Published in Transactions on Machine Learning Research (09/2024)
We propose new explanation: the size of counter relationships. Explicitly increasing the complexity of counter relationships can increase the game's depth, requiring players to study and practice more to master the game with different counter categories to dynamically adjust to the strategies of other players. This ensures a diverse game sctting, which is what Top-B Balance can help achieve. Also, accepting the idea of uncertainty from player skill or luck can enrich the game content. Tf there are weaker compositions, we do not necessarily have to change them to improve balance. Keeping them within tolerant win value gap allows players to try them occasionally based on the belief in tolerance reasons, increasing the diversity of game mechanics. This is what Top-D Diversity can help with.
There is no clear advantage of one balance mcasure over another since they can be used simultancously to provide suggestions. The final decision on which suggestions to use is the responsibility of game designers. Different balance measures provide different information, and we believe our new balance measures can enrich the choices for balance suggestions. Additionally, balance is just one of many factors considered in game design (Schell 2008). Designers sometimes compromise on balance in favor of more important themes or features that enhance the game experience [Schell 2008), or players may prioritize playstyle diversity to express their individuality (Lin et al. 2024). To address these kinds of requirements, the regularization term in the entropy-basod balance mcasure (Pendurkar et al. 2023) serves as an example of implementing this trade-off, similar to how the tolerance gap functions in our Top-D Diversity measure.
We also give two simple examples to demonstrate the advantages of our new measures that previous measures cannot explicitly report. Case one: a game without counter relationships, as seen in our Simple Combination Game. There is a theoretically optimal composition: (18,19,20). If we consider the strategy reaching Nash equilibrium, there is only one strategy selecting this composition, and the entropy of this strategy is zero, indicating super imbalance. However, if we consider some slightly weaker compositions: (17,19,20) and (13,17,19), their expected win rates against the best composition are 49.115% and 42.496%, with standard deviations (Vp(1-p)) of 49.992% and 49.434%, respectively. This shows some probability of reporting (17,19,20) or (13,17,19) as stronger than (18,19,20) with small samples, which may make players feel balancod based on small sample sizes. In this case, Top-D Diversity would help quantily this type of scenario and would not strongly require all compositions to have the same strength, which might need exhaustive effort to develop mechanisms that are not the same but have the same strength.
Another example: we can imagine two extended variants of Rock-Paper Paper-- with payoff matrices in Figure [ In the original game, we already know that the mixed strategy reaching Nash equilibrium is (1/3,1/3,1/3) and is the uniform distribution. For both the upper variant and the lower variant, the uniform distribution is still a Nash equilibrium solution strategy, and using this strategy would result in a 50% average case win rate. Thus, both entropy-based and simple win rate measures would suggest they are both at the same level of balance. Howeeer, when applying our Top-B Balance measure, we can use only a 4 4 counter table to fully describe the counter relationships in the upper variant (Rock2, Paper2, Scissors2 share the same counter category), but in the lower variant, need 6 x 6 counter table. This result implies that the lower case has larger size of counter relationship and players need to study and adjust their strategy for every composition, aligning with our new explanation of improving game balance.
7 Conclusion and Future Works
The quantification of balance competitive scenarios is crucial for analyzing how many participants are meaningful. This paper focuses on a special case of two-team zero-sum competitive scenarios, PvP game compositions. With our approximations of rating and counter relationships, domination relationships can now be quantified efficiently. In the past, most balancing techniques have primarily relied on win rate analysis. Our experiments, conducted in popular online games, underscore the efficacy and practicality of our approach. We believe our work enhances the tools available for game balancing, leading to more balanced and engaging player experiences.
There are still many topics to explore further in the realm of PvP game compositions. For example, we have only considered bre-b compositions, but measuring the balance of elements that form a composition is also important for games with a vast number of element combinations, such as the individual cards in
19

---

Published in Transactions on Machine Learning Research (09/2024)
Rock
Paper
Scissors
Rock2
Paper2
Scissors2
Rock
0
-1
0
0
Paper
1
-1
0
0
Scissors
-1
0
0
0
Rock2
0
0
0
0
Paper
Scissors
Paper2
0
0
0
0
Scissors2
0
0
0
0
Rock
-1
Paper
0
Rock
Paper
Scissors
Rock2
Paper2
Scissors2
Scissors
-1
1
0
Rock
Paper
Scissors
-1
Rock2
Paper2
0
Scissors2
0
-1
Figure 4: An example of extending the classical Rock-Papor-Scissony
complex cases.
Hearthstone, the specific tech tree in Age of Empires II, or even the equipment in League of Legends. For games where it is difficult to cnumcrate all compositions, considering composition building first is essential.
Expanding our focus to broader applications, our approach can be applied to domains where the assessment of competitor strength is crucial in competitive scenarios, such as sports, movie preference, peer grading, elections, and language model agents (Chen & Joachims) 2016 Zheng et al., 2023). In the realm of cutting- edge artificial intelligence research, our approach could ofler insights into multi-agent training with counter relationships to exploit weaknesses (Vinyals et al., 2019) and potentially benefit fields like Al safety for attack and defense analysis (Amodei et al. 20016). Thus, our methods hold promise for wide range of applications, marking step forward in the quantitative analysis of competitive dynamics.
Broader Impact Statement
Our rating and counter tables are learned models and do not guarantee that the results will always be the same. It is necessary to carefully check and train several models for critical applications to ensure the results are not based on random guesses. Our balance measures focus on helping pinpoint the advantages and weaknesses of each composition rather than identifying a single dominating composition. However, if misused, this approach could potentially aid in creating market monopolies rather than improving balance. It is important to use these measures ethically and with the intention of promoting fair competition. Additionally, our met hodology built on a scalar rating system and tested on two-team zero-sum symmetric games, which may limit the applicability of balance measures other types of games, especially those without a win rate.
Acknowledgments
We appreciate all the valuable feedback and insights from everyone who reviewed this research, which greatly helped in refining and improving this work. Additionally, we would like thank Gamania Digital Entertainment Co., Ltd. (Gamania) for inspiring the research topics related game balance in our early studies.
20

---

Published in Transactions on Machine Learning Research (09/2024)
References
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul F. Christiano, John Schulman, and Dan Mané. Concrete problems in Al safety, CoRR, abs/1606.06566 06565, 2016.
Alexei Baevski, Steffen Schneider, and Michael Auli. vq-wav2vec: Self-supervised learning of discrete speech representations. In International Conference on Learning Representations (ICLR), 2020.
Sander Bakkes, Shimon Whiteson, Guangliang Li, George Viorel Vişniue, Efstathios Charitos, Norbert Heijne, and Arjen Swellengrebel. Challenge balancing for personalised game spaces. In IEEE Games Media Entertainment (GEM), 2014.
David Balduzzi, Karl Tuyls, Julien Pérolat, and Thore Graepel. Re-evaluating evaluation. In Advances in Newral Information. Processing Systems (NeurIPS), 2018.
Philipp Beau and Sander Bakkes. Automated game balancing of asymmetric video games. IEEE conference on computational intelligence and games (CIG), 2016.
Alexander Becker and Daniel Görlich. What is game balancing? examination of concepts. ParadigmPlus, 2020.
Marlene Beyer, Aleksandr Agureikin, Alexander Anokhin, Christoph Laenger, Felix Nolte, Jonas Winter- berg, Marcel Renka, Martin Rieger, Nicolas Pflanzl, Mike Preuss, et al. An integrated process for game balancing. In IEEE Conference on Computational Intelligence and Games (CIG), 2016.
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. Heads-up limit hold'em poker is solved. Science, 447, 2015.
Ralph Allan Bradley and Milton E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 1952.
Jane Bromley, James W. Bentz, Léon Bottou, Isabelle Guyon, Yann LeCun, Cliff Moore, Eduard Säckinger, and Roopak Shah. Signature verification using A "Siamese' time delay neural network. International Journal of Pallern Recognition and Artificial Intelligence (IJPRAI), 7, 1993.
Nathaniel Budijono, Phoebe Goldman, Jack Maloney, Joseph B Mueller, Phillip Walker, Jack Ladwig, and Richard G Freedman. Ludus: An optimization framework to balance auto battler cards. In AAAT Conference on Artificial Intelligence (AAAI), 2022.
Shuo Chen and Thorsten Joachins. Modeling intransitivity in matchup and comparison data. In Interna- tional Conference on Web Search and Data Mining (WSDM), 2016.
Lincoln Magalhães Costa, Alinne Crintinne Corréa Souza, and Francisco Carlos M. Souza. An approach for team composition in league of legends using genetic algorithm. In Brazilion Symposium Computer Games and Digital Entertainment (SBGames). 2019.
Rémi Coulom. Computing 'clo ratings" of move patterns in the game of go. Journal of the International Compuler Gomes Association (ICGA journal), 2007.
Mihály Csikszentmihálli. Flow: The Psychology of Optimal Experience. Harper & Row, 1990.
Fernando de Mesentier Silva, Rodrigo Canaan, Scott Lee, Matthew C. Fontaine, Julian Togelius, and Amy K. Hoover. Evolving the hearthstone meta. In IEEE Conference Games (CoG), 2019.
Jacob D. Dodson. The relation of strength of stimulus to rapidity of habit-formation in the kitten. Journal of Animal Behavior, 1915.
Arpad E. Elo. The USCF Rating System: Its Development, Theory, and Applications. United States Chess Federation, 1966.
21

---

Published in Transactions on Machine Learning Research (09/2024)
Felipe Machado Figueira, Lucas Nascimento, Jose da Silva Junior, Troy Kohwalter, Leonardo Murta, and Esteban Clua. Bing: A framework for dynamic game balancing using provenance. In Brazition Symposium on Computer Games and Digital Entertainment (SBGames), 2018.
Matthew C Fontaine; Scott Lee, Lisa Soros, Fernando de Mesentier Silva, Julian Togelius, and Amy K Hoover. Mapping hearthstone deck spaces through map-clites with sliding boundaries. In The Genetic and Evolulionary Compulation Conference (GECCO), 2019.
Ralf Herbrich, Tom Minka, and Thore Graepel. TrueSkillM; A Bayesian skill rating system. In Advances in Newral Information Processing Systems (NTPS), 2006.
Daniel Hernández, Charles Takashi Toyin Ghadamosi, James Goodman, and James Alfred Walker. Metagame autobalancing for competitive multiplayer games. In IEEE Conference on Games (CoG), 2020.
Robin Humicke. The case for dynamic difficulty adjustment in games. In ACM SIGCHI International Conference on Advances in computer entertainment technology (ACE), 2005.
Alexander Jaffe, Alex Miller, Erik Andersen, Yun-Ei Liu, Anna Karlin, and Zoran Popovic. Evaluating com- potitive game balance with restricted play. In AAAI Conference Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2012.
Diederik P. Kingma and Max Welling, Aulo-encoding variational bayes. In International Conference on Learning Representations (ICLR), 2014.
Donny Kristianto. 2023 gaming spotlight: Mobile is set to surpass $108 billion this year maintaining its 2.7x global revenue lead over pe/mac, 2023. URL https://www /tt.ttps////w..aaaaaaaa/////aaaa
2023 2023-gaming gaming--sotllight--eeee
Daniel Lazewatsky. melo re-evaluating evaluation.
2024.
Accessed: 2024-07-22.
Steve Levkoff. On balance-optimmizing the pvp experience, 2014. URL http:://ww.gemmdwweeppr...... com/
Shiyu Li, Hao Ma, and Xiangyu Hu. Neural image beauty predictor based on bradley-terry model. CoRR, abs/2111..0111 2021.
Chiu-Chou Lin, Wei-Chen Chiu, and I-Chen Wu. An unsupervised video game playstyle metric via state discretization. In Conference Uncertainty in Artificial Intelligence (UAI), 2021.
Chiu-Chou Lin, Wei-Chen Chiu, and I-Chen Wu. Perceptual similarity for measuring docision-making style and policy diversity in games. Transactions on Machine Learning Research, 2024.
James MacQueen al. Some methods for classification and analysis of multivariate observations. In Berkeley symposium mathematical statistics and probability, volume 1. Oakland, CA, USA, 1967.
Tobias Mahlmann, Julian Togelius, and Georgios N. Yannakaki.. Evolving card sets towards balancing dominion. In IEEE Congress on Evolutionary Compulation (CEC), 2012.
Mihail Morosan and Riccardo Poli. Automated game balancing in ms pacman and stareraft using evolution- ary algorithms. In Giovanni Squillero and Kevin Sim (eds.), Applications of Evolutionary Computation (EroAApllications) 2017.
Sofia Maria Nikolakaki, Ogheneovo Dibie, Ahmad Beirami, Nicholas Peterson, Navid Aghdaie, and Kazi A. Zaman. Competitive balance in team sports games. In IEEE Conference on Gomes (CoG), 2020.
Jeannie Novak, Meaghan O'Brien, and Jim Gish. Game development essentials, volume 3. Delmar Cengage Learning, 2012.
22

---

Published in Transactions on Machine Learning Research (09/2024)
Sumedh Pendurkar, Chris Chow, Luo Jie, and Guni Sharon. Bilevel entropy based mechanism design for balancing meta in video games. In International Conference on Aulonomous Agents and Multingent Systems (AAMAS), 2023.
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 2022.
Muhammad Farrel Pramono, Kevin Renalda, and Harco Leslie Hendric Spits Warnars. Matchmaking prob- lems in moba games. Indonesion Journal of Electrical Engineering and Computer Science, 2018.
Simão Reis, Luis Paulo Reis, and Nuno Lau. VGC Al competition A new model of meta-game balance Al competition. In IEEE Conference on Games (CoG), 2021.
Simão Reis, Rita Novais, Luís Paulo Reis, and Nuno Lau. An adversarial approach for automated pokémon team building and melagane balance. IEEE Trans. Games, 16, 2024.
Falko Rheinberg. Intrinsic motivation and flow. Motivation Science, 2020.
Florian Rupp, Manuel Eberhardinger, and K. Eckert. Balancing of competitive two-player game levels with reinforcement learning. 2023 IEEE Conference on Games (CoG), 2023.
Jesse Schell. The Art of Game Design: A book of lenses. CRC press, 2008
Tim Schmitz. A better way to measure game balance using game theory, 2022. URL https:// quantimachmi tz. wat.comm/222
Michael Sellers. Advanced game design: a systems approach. Addison-Wesley Professional, 2017.
Woncheol Shin, Gyubok Lee, Jiyoung Lee, Eunyi Lyou, Joonseok Lee, and Edward Choi. Exploration into translation-eequivrraatt image quantization. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2023.
Nenad Tomašev, Ulrich Paquet, Demis Hassabis, and Vladimir Kramnik. Reimagining chess with alphazero. Communications of the ACM, 2022.
Aäron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural discrete representation learning. Tn Advances in Newral Information Processing Systems (NeurIPS), 2017.
Oriol Vinyals, Igor Babuschkin, Wojciech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang, L. Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg, Alexander Sasha Vezh- nevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard, David Budden, Yury Sulsky, James Molloy, Tom Le Paine, Caglar Gulcehre, Ziyun Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy P. Lillicrap. Koray Kavukeuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft ii using multi-agent rein- forcement learning. Nature, 2019.
Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu, Jason Baldridge, and Yonghui Wu. Vector-quantized image modeling with improved VQGAN. In International Conference Learning Representations (ICLR), 2022.
Jiahui Zhang, Fangueng Zhan, Christian Theobalt, and Shijian Lu. Regularized vector quantization for tok- enized image synthesis. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing, Hao Zhang, Joseph E. Gonzalez, and lon Stoica. Judging Ilm- as-a-judge with mt-bench and chatbot arena. In Advances in Newral Information Processing Systems (NeurIPS), 2023.
23

---

Published in Transactions on Machine Learning Research (09/2024)
Comp
Comp
Always select the nearest vector, and make their position be closer during training.
Still select the vector, but also make vectors be slightly closer to the target &g to increase the codebook utliization.
Codebook Cigy
Codebook Cike
Zep
Eqp
Zga
J
Zap4
ZA2
Zg5
Without VQ Mean Loss
With VQ, Mean Loss
Figure 5: Demonstration of codebook utilization improvement using VQ Mean Loss.
A Appendix
A.1 Enhancing Codebook Utilization Through VQ Mean Loss
We tackle the issue of underutilization in codebooks for Vector Quantization (VQ) by introducing the VQ Mean Loss technique. This method significantly improves the use of the embedding space in VQ models. As depicted in Figure traditional VQ- VAE approaches depend on nearest neighbor selection for determining latent vectors, which lead to sparse utilization of the codebook. The integration of VQ Mean Loss obviates the need for meticulous codebook initialization or hyperparameter fine-tuning to overcome low utilization problems.
A.2 Illustrative Examples of Top-D Diversity Measure and Top-B Balance Measure
We elucidate the Top-D Diversity Measure with an example Figure 6 When utilizing a single scalar for strength measurement. of compositions, identifying the composition with maximum strength (denoted as A in the figure) is straightforward. By defining acceptable win value gap G, for instance, G = 5%, which may represent a game's 's error margin, compositions with rating equal to or greater than 1.47 are considered playable. Such a demarcation is akin to tier tables commonly created within gaming communities, suggesting that our rating table could facilitate the construction of insightful analyses or tier tables.
Comp
Rating
A
1.8
8
1.7
Top-D Diversity Measure: 4
C
1.6
D
1.5
E
1.4
F
1.3
0.05 2
1.8
= x 147
Figure 6: Demonstration of Top-D) Diversity Measure, showcasing compositions with ratings above specified threshold playable.
24

---

Published in Transactions on Machine Learning Research (09/2024)
For the Top-B Balance Measure, present simplified example in Figure 7 Here, compositions assigned ratings and categorized according to the Mock-Paper-Seissons framework. In this extended gameplay, the highest-rated composition within each category is presumed to be dominant. Therefore, to assess game balance, one only needs to examine the win value relationships between these top compositions. Compositions that are dominated may represent beginner-level less costly options, requiring players to progress and level up to obtain higher-strength compositions for fair competition ultimately.
Rock-Comp
Rating
Paper-Comp
Rating
Scissors-Comp
Rating
1.6
1.4
Top-B Measure:
R3
1.3
P3
1.1
53
1.1
R5
1.0
P5
0.7
S5
0.9
0.2
Counter
Rock-Comp
Paper-Comp
Scissors-Comp
Rock-Comp
0
-50%
+50%
Paper-Comp +50%
-50%
Scissors-Comp -50%
+50%
Figure 7: Explanation of the Top-B Balance Measure, illustrating the assessment of balance by analyzing top compositions within each Rock- Bock-Paper-oe Scissors category.
Paper-Scissors
A.3 Rating Tables and Counter Tables in Online Games
This appendix provides a discussion of the rating tables and counter tables derived from our first model in Age of Empires II, Hearthstone, and Brawl Stars. Each game's tables reveal interesting insights into the dynamics of team compositions and their interactions. We also explore the rationality and categorization inferred from these tables.
A.3.1 Age of Empires II
The x counter table for Age of Empires II (Figure 8 clucidates the complex interplay of civilization strengths, weaknesses, and counter strategies in the gamne With each civilization boasting unique attributes that cater different playstyles, the table categorizes them into nine distinct groups, reflecting their strategic affinities and shared advantages.
The groups are delineated as follows:
1. Technological and Age Advancement Group: Civilizations such as the Malay with accelerated age advancement, the Malians with their fast university research, and the Bulgarians with free militia-line upgrades and significant cost reductions for Blacksmith and Siege Workshop technologies, offering them a strategic edge pacing the game.
2. Heavy Cavalry Group: Notable for their robust cavalry units, civilizations like the Franks and Lithuanians dominate open-field engagements with their superior mobility and combat prowess.
Anti-Cavalry and Anti- Group: This cohort, including the Goths with their cconomical infantry and the Indians with their camel units, specializes in countering cavalry and archers, altering the flow of battle with their unique troop compositions.
25

---

Published in Transactions on Machine Learning Research (09/2024)
Age Empires Counter Table
[malay, bulgarians,spanish. ethioplans, burmese. bengalis]
Jurnns, lithuanians]
[hindustanis.gotte gurjaras]
[romans, sicilians, bohemians, vikinns,
armenians, japaaase,,peeeeeee
[turks, portuguese, talians,
talians,dravidiann dravidians,)
[persians, magyars, shmer,mayans,)
[mongols.tatane tatars,
britons,koreans, koreans, vietnamese]
saracens,
burgundians,chines,,
byzantines,
georgians]
-10%
[malay malians, bulgarians, ethioplans burness. bengailss]
[franks cummnss Ithuamanns)
Dindustanis goths, gurjaras)
fromans, sicilians, bohemiant wiking, teutonns cetts.
[turks pww.sguuuuuee.. Rtalian, di dreviddaans)
[persians, berbbers magyara yars, khmer mararaaaasnn aons.]
[mangels, Imangols,Laanm tatars, britons, lorreas, vetmamese
Ipoles sarae arracens, bur burgundianss, chineie.]
lincas lincassslann slavs, byzantimes
Figure 8: The x 9 counter table for Age of Empires II, illustrating the intricate balance of civilization
match-ups.
26

---

Published in Transactions on Machine Learning Research (09/2024)
4. Infantry Dominance Group: Comprising civilizations with formidable infantry units, this group excels in foot-soldier combat, sustaining front-line engagements and applying pressure through sheer force.
5. Cunpowder-Intensivee Group: Civilizations in this category leverage the destructive capacity of gunpowder units to gain decisive advantage in warfare.
6. Cavalry and Horse Archer Factions: Balancing strengths between cavalry and horse archers, these civilizations maintain flexible and dynamic combat tactics, adept at swift raids and retreats.
Dominated by civilizations with powerful ranged units, this group wields archers as the cornerstone of their military strategy, excelling in long-range engagements.
Archery Group:
Economic Powerhouses: These civilizations thrive on economic prowess, underpinning their mil- itary campaigns with robust economies and resource accumulation.
Trash and Counter Unit Group: With a focus on cost-effective 'trash units' and specialized counter units, this group adeptly negates enemy strategics, maximizing efficiency in resource man- agement.
Category1
Category2
Category3
Category4
Category5
Category6
Category7
Category8
Category9
Malay
Franks 0.99444
Hindustanis
Romans 1.08145
Turks
Persians
Mongols 0.99319
Poles 0.91685
Incas
1.00146
1.06402
1.03038
0.99886
1.02497
Malians
Cumans 0.97313
Goths 0.99500
Sicilians
Portuguese
Huns 0.98785
Tatars 0.83885
Saracens 0.88485
Slavs
0.97565
1.02928
0.91956
1.00203
Bulgarians 0.96124
Lithuanians 0.96764
Gurjaras 0.93271
Bohemians 1.02476
Italians 0.88166
Berbers
Britons
Burgundians 0.88276
Byzantines
0.97427
0.83176
0.89442
Spanish 0.94718
Vikings 0.99278
Dravidians
Magyars
Koreans 0.79998
Chinese 0.85114
Aztecs
0.87841
0.95044
0.87008
Ethiopians 0.94380
Teutons 0.97401
Khmer 0.90366
Vietnamese 0.79796
Georgians 0.76448
Burmese
Celts
Mayans 0.88710
0.87361
0.94887
Bengalis
Armenians
0.87242
0.91716
Japanese
0.89536
Figure 9: The rating table for Age of Empires II, depicting the overall strength and viability of each civilization.
The rating table (Figure complements the counter table by offering a quantitative assessment of each civilization's overall strength. This allows for a broader perspective beyond direct match-ups, giving insight into how each civilization fares in the general meta.
The counter table not only outlines how civilizations within the same group perform against each other but also illustrates the inherent strengths and weaknesses they possess against other groups, shaped by their distinct technologies, units, and economic bonuses.
For instance, the Heavy Cavalry Group is susceptible to the powerful Anti- Cavalry capabilities civilizations like the Hindustanis or Goths. They may also find themselves a disadvantage against Infantry-dominated factions but can leverage their cavalry's mobility gain an upper hand against civilizations that rely heavily gunpowder archery for ranged attacks. Goths, while typically facing a disad in matchups against
27

---

Published in Transactions on Machine Learning Research (09/2024)
other Infantry-focused civilizations, prove to be highly effective against Archery-based groups. It is commonly believed that Infantry-centrie civilizations can be countered by those that specialize in gunpowder units and archers; however, they are usually quite efficient against civilizations that rely on 'trash units. Economically focused civilizations display more fiexibility and tend to have less pronounced counter relationships.
Recognizing and understanding these counter dynamics is essential for competitive play. enables players predict and neutralize the strategies of their opponents, resulting in more sophisticated and informed decision- making both prior to and during matches. This strategic depth accentuates the long-standing charm of 'Age of Empires II' as competitive real-time strategy game, where tactical knowledge and strategic planning are as crucial as agility and execution.
A.3.2 Hearthstone
The 9x9 Hearthstone counter table (Figure 10p represents a strategic breakdown of deck matchups, reflecting how various playstyles interact within the game. Fach category is defined by distinct tactical approaches, and the table illustrates the expected performance of these categories against one another, with green indicating favorable matchup and red indicating disadvantage.
[Jeathhiione Courder Tablle
Uighlander Shemen Lighlander Paledin, sifflerder Contid Ihick nighrunder deren Nurker sright)
Ulreurt Uru di Tugan Dravve Hlunte Islon Sheman
[Maqe Dragon DrucsPech hlguu
Taurn Warner
[tatthen Naludn]
(nigh Anoume Secret Mays tightarderr
Highlande Bruis Maning Werood busth tonght tign Mirado Rogas Naturr Bruad
fromm liuund Jerans
lighlender rigpic
Weining floqus aarrock Paladin Ulmmetta
Aqpro Dumin Hurber Wakking Toggu.Thheoaie MaperMalare Nalura
Ogra hopes,
Mach Mape
[Maing Warner Centrol Waraar Rarizow Hage; koftander
AAgire Paladin Shoussonm Paudin]
Shoma.
1OOT-
Figure 10: The 9 x 9 counter table for Hearthstone, detailing the strengths and weaknesses of various deck archetypes.
1. High- Value Control Archetypes (Category 1): These decks, often Singleton with no duplicate cards, rely on high-value individual cards and powerful board clears, such as the notorious Reno Jackson hero card, to win by value over time. Examples include Highlander Shaman, Paladin, and Demon Hunter, well as Control Priest and Blood Death Knight.
Tempo-Dependent Decks (Category 2): These archetypes require a specific mana curve play cards efficiently and can dominate when curving out correctly. Decks like Treant Druid and Big Rogue, which need to establish board and then buff it, fall into this category.
28

---

Published in Transactions on Machine Learning Research (09/2024)
3. Combo-Reliant Archetypes (Category 3): These decks hinge key cards to enable combina- lions but lack exceptionally fast draw engines. Naga Priest and Dragon Druid, which require a mix of Naga and spells, or Dragon cards in hand respectively, are typical of this category.
4. Midrange Archetypes with Strong Creatures (Category 4):
This category thrives on deploy- ing minions with both high attack and health, sustaining board presence to win. Earthen Paladin is prime example, using minions that can endure and dominate board trades. Their area of effect spells also gives them an advantage against swarm- swarm-based strategies (Category 7).
Midrange Value Decks (Category 5): These decks aim to overwhelm the opponent with the sheer quality of their cards, not necessarily through a quick victory but through sustained pressure and superior trades.
Diverse Midrange Archetypes (Category 6): A mix of decks that don't neatly into one archetype but generally win by card value. They often don't have as stark counter relationships and tend to have more even matchups.
7. Aggro and Snowball Archetypes (Category 7):
These decks look to establish an early board presence and snowball to victory. They perform well against decks that struggle to clear multiple thrcats, such as general aggro docks (Category 9).
8. Valuc-Oriented Decks with Combo Finishers (Category 8): This group features decks that maintain board control with ample resources and are capable of executing a one-turn-kill (OTK) combo in the late stages of the game. Notably, Control Warrior can build up a significant armor stack to unleash a massive hit, while Rainbow Mage is known for its combo potential to achieve an OTK.
9. Aggressive Paladin Archetypes (Category 9): threats early on and aim to end the game before the opponent stabilizes.
These decks spread the board with multiple
The analysis reveals that control archetypes (Category 1) are effective against high-value creature decks (Category 4) due to their abundance of removal options. However, they struggle against decks with late- game OTK capabilitics (Category 8) because such decks bypass control strategies with sudden win condition. Tempo (Category 2) decks falter against stable midrange (Category 4) due to board clears disrupting their momentum, while also struggling against the faster-paced aggro decks (Category 9) that can establish a quicker board presence.
Combination-relinn decks (Category 3) tend to underperform against aggressive Paladin strategies (Category 9) due to the Paladins' ability to conclude games before combos can be assembled. Mcanwhile, the snowball potential of decks in Categories and makes them strong against tempo decks but vulnerable to control archetypes with multiple board clears.
Value-oriented docks with combo finishers (Category 8) excel against control decks by circumventing their gradual value game with sudden win condition, yet they might struggle against decks with large minions that their additional resources can't efficiently counter.
Through the counter table, Hcarthstone players can better strategize their deck choices and gameplay, considering the prevalent matchups in the current meta. The table thus serves as a critical tool for players aiming to optimize their strategies and achieve higher win rate in competitive play.
29

---

Published in Transactions on Machine Learning Research (09/2024)
Table Strength relation accuracies (%) in training and testing for Brawl Stars 2 Heroes.
Training Accuracy
Testing Accuracy
WinValue
56.7
56.7
PairWin
80.0
74.9
BT
50.9
50.7
NRT
58.0
57.1
NCT M-3
58.1
57.1
NCT M=9
61.5
60.2
NCT M-27
63.5
61.9
NCT M-81
65.6
63.7
Category1
Category2
Category3
Category4
Category5
Category6
Category7
Category8
Category9
Highlar
Naga Priest 1,20033
Farther Palacin
Miniing Roguh
Mage
Aegro Paladin
1.C2839
Hiihhtr der Patadin
Biy Rogue
Druid 1.5328
Pallddin
Arcane Hlunte
Sludge Warfock
Undcad Priiet 0.78334
Mining Warr 0.86667
Showwoow Paladin 2.00791
Hightar der Priest 0.2 0.81985
Cleavi Hanter 1.08808
Mech Rogue 1.00164
Secret Mage 1.0112
Siver Hand Paladin 0/859/1
Relic Demon
Control Wariior 0,57570
Control Prrest
icter Shaman 98/73
Secret Hunter 09550
Highta ncer Blood Diveth Knight 1.00966
blemental Mage D 0.811 76
Unholly Death Knight 0-4092
Rambow Mage D RE-192
P5igS
nighlar der Demon Hunter
Rock in' sull Warrior 0,89733
Ulementall Sluman
Fighl Higllaneee Unuid 1,00240
Age a Uee on Hunner 0.81080
Ugre Prient 0,/0467
0.65439
Blood Death Knight 0.17535
Cursa Warlook 0.82253
Mech Paladin 0.77766
Maguc Death Knight 0.90257
Wishing Roguc 0.77634
Highlandor Mage 0.63054
Highlander Warrior 0b66662
Tount Warnor 0.646/0
Big Shaman 0.90223
Thadalus Warlock 0.77232
Mconbeom Cruid
0.01308
(hadddis Uruid
Seczret Rogua 0.6985S
Control Warlock
Oigne Rogue
Breekkfatt Hunter
0.55146
n.98740
0.20175
0.170011
Figure 11: Rating table for Hearthstone docks, showcasing the top cight decks within each category based on their performance in the current meta. The ratings are indicative of the deck's 's overall strength and potential to win matches within their respective categories.
A.3.3 Brawl Stars
In games with complex combinations for building compositions like Brawl Stars, it requires much more game knowledge to explain the possible meaning of counter categories from learning. For example, if we consider the composition number only three heroes Brawl Stars, there are C = 41664 available compositions. It not easy check all these compositions and further check their pairwise relationships. According Table D the counter relationship not clear in Brawl Stars with three heroes and the corresponding game modes and maps. Using NRT can achieve 95.9% average accuracy and adding an M 81 counter table only improves 1.3% extra accuracy. This implies that the scalar rating value already reflects most strength relationships and there is not much significant information that an extra counter table can help with. Thus, we trained another composition setting in Brawl Stars. We only considered two-hero combinations as the compositions, and for each game match, we split into C2 x C 9 game matches as the training and testing dataset. The corresponding accuracies of this setting are listed in Table
In this setting, the accuracy improvement with the M counter table is 3.5%, implying that some meaningful categories identified for describing counter relationships. We selected the best model of the
30

---

Heroes like Barley, Frank, and Buster have powerful Published in Transactions on Machine Learning Research (09/2024)
Biatal Stars 2 Heroes Counter Tab
KOP SANDYIIIA LE
JAMBER RA INK.
GENEIIE GAMM) IGRA PIJCOLT P.OTTS WAIJIEEMJJLLONRRUURR LARRO
WELLMMMTUMM ANCAUAL MIUUUUSTTLLLE HIAMRI Jous TER NJCOLLL TE LJESS (AGH SHILL.
GETIE
SPODU JHANGL DLA) (eaa,, (ati ou oLASea (Jo-Ne, TARAy
BULL, TRSSTRRTSTTTTOO SQUE/RICCCLETTEE LOUI SEAIIBE (ic, MUNTTR
jiMig IKFF MARTSS TSS
BUSTERISSEIIIEEE JARAEBULL BYYRON NAII, JONNEL HUR BROOK BUITS SAR (90, MANI COL TAANI
jAiNE SAAR AAARE SUI |JUUST SANDD P-SIT BER MANTI ONNIE, PON)
(OU SPROLITY JACK [TRAK SAND)) JOOLETTE COLLTTE.GPROM,CCMM SUSSSURGEJDRRRR LAARRA (PROUT]]
JENU
IMSEREENNNI TRONNE ROZ7TROA..PROU
(CHESTER,CLL SO,OGE REJJAMBB R,ANET LESSH MANDI
HR (FF111 (LO.ARCO)
FRUGCAA
BROOK CUU
FANEL FAMELLOIA CENE,TMO TMD4
ILETTE (LETT__LC) LCU) KJRIL M VORTIS
LLEEETTT OCKUPUITS) (6AN)
EUS RUPPS] TER SAADD INIE PAN
LRUFTS KSScin VLSPROUTI
TASSIT SESTEE CONOOO
Figure 12: The 9x9 counter table for Brawl Stars under two heroes combinations.
M counter table among five models, where the training accuracy is 62.0% and testing accuracy is 60.2%. The corresponding accuracy improvement from the used NRT model is 4.0% and 3.2%.
Figure 12 shows the result of this counter table. We only list the first nine compositions for each category and try to analyze these compositions with our game knowledge to check whether these compositions also have some clear meaning.
The groups are delineated as follows:
1. High Mobility and Sustained Output: Heroes like Sandy, Darryl, and Edgar possess high mobility, while others like 8-Bit, Sprout, and Mr. P provide sustained output.
Versatile Skills and Comprehensive Abilities: Heroes such as Janet, Lola, and Gray have transformative abilities, allowing them to switch states.
Strong Crowd Control and Suppression: control and suppression abilitics.
High Burst Damage and Support: Heroes like Edgar, Brock, and Fang offer high burst damage, while others like Gus, Gene, and Tara provide support and assistance.
5. Long-Range Control and Arca Damage: Herocs like Sprout, Squcak, Barley, and Grom possess long-range control and area damage abilities.
6. Multi-Skill Coordination: Heroes like Bonnie, Ruffs, and Byron can coordinate multiple skills, providing sustained output and support.
Sustained Output and Support: Heroes like Mandy, 8-Bit, and Pam provide sustained output and support
31

---

Published in Transactions on Machine Learning Research (09/2024)
8. Versatility and Flexibility: Heroes like Gale, Gus, and Edgar offer versatility and flexibility, adapting to various tactios.
Quick Burst and Control: Heroes like Chester, Shelly, and Buzz possess quick burst and control abilities.
Since there are C available compositions and our limited game knowledge, we do not guarantee that these analyses are entirely correct, but we can find some interesting relationships. High Mobility and Sustained Output has advantage over the Long-Range Control and Area Damage category due to their high mobility but may be countered by Sustained Output and Support in modes requiring prolonged engagement. The three categories with versatility: 2, 6, and & tend to form a cycle where 2 > 6 > 8 > 2.
These kinds of ad-hoc explanations may help game designers to change the game mechanisms from a more general aspect. there game that is very hard to explain the counter table or tables diverge when trained from different random soeds, we may need more detailed attributes of the combination elements summarize reasonable update direction.
A.4 Neural Network Architectures and Details
In our study, we employ distinct neural network architectures tailored to the specific requirements of each player-versus-llayer (PvP) game in our dataset. Below we provide detailed description of the network designs and input features for cach team composition:
Simple Combination Game: 20-dimensional binary vector representing elements.
Rock- Paeck--aper-Sssssors: 3-dimensional one-hot vector for category representation.
Advanced Combination Game: 23-dimensional vector combining 20-dimensional binary element en- coding with 3-dimensional one-hot category encoding.
Age of Empires II: 45-dimensional one-hot vector for civilization representation.
Hearthstone: 91-dimensional one-hot vector for deck naming.
Brawl Stars: 115-dimensional vector encoding the complex dynamics of Trio Modes. This includes binary encoding for the presence of 64 unique heroes, one-hot encodings for 43 distinct maps plus an indicator for any map not listed, and similar encoding scheme for the 6 game modes and any unrecorded mode. This encoding captures the essence of team compositions, map strategies, and game modes, essential for predicting match outcomes in Brawl Stars.
League of Legends: 136-dimensional binary vector for champion representation.
Each network is constructed to handle the dimensionality and characteristics of the input features:
WinValue Network: Processes individual compositions to out direct win rates.
PairWin Network: Predicts the pairwise win rate between two compositions.
BT Network: Implements a lincar approximation of the Bradlcy-Torry model.
NRT Network:
Offers non-linear approximation of the Bradley-Terry model, capturing complex relationships.
NCT Network: The neural counter table consider counter relationships.
For cach neural network configuration, we present architectural diagrams that illustrate the structure and flow of data through the network and these network configuration are shared with all games. These visuals serve to complement the textual description and provide an at-a-glance understanding of each model's design.
32

---

Published in Transactions on Machine Learning Research (09/2024)
A.4.1 Formulations of Strength Relation Methods
For more formal definition of the methods used in the strength relation classification task, use the following definitions. For each match outcome, we have two compositions, A and B, and a strength relation label with three valid states: weaker traakr/ssme/streee /saee//rr/og/err. The ground truth of each matchup A, B is determined by the tabular PairWin method, which simply counts the average win value of this composition matchup. For example, if a matchup A, has 100 game results with 60 wins, 30 losses, and 10 ties, the win value is (60 1.0 + 30 0.0 10 0.5)/100- 0.65. For I 0.501, the strength relation label is stronger; for 0.499, the strength relation label is weaker; and for 0.499 same.
0.501, the strength relation label is
WinValue: Given a win value estimator WinValueg(C) of composition C without considering its op- ponent, if WVnValuue, (A) WinV (anValee((B) (B) 0.001, the prediction stronger. If WinV WinValueg( B) WinV (A)) 0.001, the prediction is weaker. If [WinV alues WWnnuauueeC (A) WinV VinVallu)(B) S 0.001,
the prediction is same.
PairWin: Given win value estimator PairWino(C1,, C2) of compositions C1 and C2 in a matchup, if PairWing ing(A A, B) 0.501, the prediction is stronger. PairW in, B) 0.499, the prediction is weaker. If 0.499 S (oir B) < 0.501, the prediction is same.
BT Network: Given strength estimator Ro(C) for composition C, if Ro(A)+RR (B) > 0.501, the
Ro(A)
prediction is stronger. If Rs(A) 0.501, the prediction same.
Ro 0.499, the prediction is weaker. If 0.499 I (o(A)+
Ro(A)
NRT: This method the same as BT but uses a non-lineat activation function in the neural networks.
NCT Network: Given a strength estimator Ro(C) for composition C and an extra counter ta- ble Wo(C1, C2) for adjusting the win value between compositions C and C2 in a matchup, if Re(A) Ro( Wo(A, B) > 0.501, the prediction is stronger. If Ro + Wo B) 0.499, Re(A) the prediction is weaker. If 0.499 < (L Wo(A, < 0.501, the prediction is same.
Ro(A)
We count the accuracy of the strength relation label predictions.
33

---

Published in Transactions on Machine Learning Research (09/2024)
Comp
FC 128, LeakyReLU(a=0.01)
FC 128, Leaky)eL
FC 128, LeakyReLU(a=0.01)
FC 128, (ea0y)e)
FC 1, Sigmoid
Win Rate
Figure 13: The architecture of the WinValue neural network.
34

---

Published in Transactions on Machine Learning Research (09/2024)
Comp A
Comp B
FC 128, LeakyReLU(x=0.01)
FC 128, LeakyReLU(a=0.01)
FC 128, (ea0))))
FC 128, LeakyReLU(a=0.01)
FC 1, Sigmoid
Win Value
Figure 14: The architecture of the PairWin neural network.
35

---

Published in Transactions on Machine Learning Research (09/2024)
Comp
FC 128, Linear
FC 128, Linear
FC 128, Linear
FC 128, Linear
FC 1, Exponential
Rating
Figure 15: The architecture the linear Bradley-Ters Terry (BT) model network.
36

---

Published in Transactions on Machine Learning Research (09/2024)
Comp
FC 128, (ea0))))
FC 128, (eakyReLU(x=0.01)
FC 128, LeakyReLU(a=0.01)
FC 128, (ea0))e)U(x=0.01)
FC 1, Exponential
Rating
Figure 16: The architecture of the Non-lineat Rating Table (NRT) network.
37

---

Published in Transactions on Machine Learning Research (09/2024)
Comp A
Comp B
FC 128, LeakyReLU(c=0.01)
FC8 LeakyReLU(a=0.01)
FC 128, LeakyReLU(a=0.01)
FC 128, LeakyReLU(a=0.01)
FC 128, Linear
FC 128, Linear
VQ
VQ
Zq (A)
Zq (B)
[zg (A), Zg (B)1
Izg (A), Zg (B)]
FC 128, LeakyReLU(c=0.01)
FC 128, LeakyReLU(a=0.01)
FC 128, LeakyReLU(c=0.01)
F28, LeakyReLU(a=0.01)
FC 128, LeakyReLU(a=0.01)
FC8, LeakyReLU(==00001
FC 128, LeakyReLU(a=0.01)
FC 128, LeakyReLU(a=0.01)
FC 1, tanh
FC 1, tanh
X1
X2
X1 - X2
2
Residual Win Value
Figure 17: The architecture of the Neural Counter Table (NCT) network.
38


Reviews:
[{"review_id": "2fMfPLdzec", "reviewer": "Reviewer_99kt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1. Single-dimensional ratings are indeed problematic and identifying cycles is important. This work is tackling an interesting problem.\n2. Attempts to tackle the scale problem using category clustering.\n3. I enjoyed the case studies of real games in the appendix.\n\nWeaknesses\n\n1. There are no non-neural-network baselines. I would have liked to see baselines against simple average, Elo, and multidimensional Elo.\n2. I feel the space/time complexity analysis is misleading or at least should be clarified.\n3. I feel the wrong parts of the paper are emphasized (clarified below).\n\nMinor Comments\n\n1. “MOBA” is undefined in the abstract.\n2. “Beginning with 3 to capture basic cycle dominance…”. Cycles can appear with just two strategies (matching pennies). I suppose this  paper mainly focuses on symmetric two-player zero-sum which requires three actions.\n3. Figure 2: Some boxes are dashed while others are not.\n4. Lemma 5.6 - is this a Lemma?\n5. I’m unsure of the distinction between “​​PairWin” and “WinValue”.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Strategies in strategic interactions can be given scalar ratings that capture in some sense their “strength”. However, scalar ratings cannot predict cycles that may appear in a strategic interaction, and instead can only capture some transitive relationship between the strategies. Knowing if a strategy dominates another from ratings is useful, but one cannot be sure that there are no cycles.\n\nThis paper focuses on PvP games for the “strategic interactions” and team compositions for the “strategies”. It proposes a multidimensional rating that attempts to provide a more accurate win-rate prediction compared to single dimensional approaches (averages, Elo, etc.). It is based on finding a base win-rate and adding a residual network to further hone the win-rate. Importantly, this residual has smaller dimensionality, because it clusters compositions allowing the approach to scale. To demonstrate the utility of their rating method they propose balance measures which may help game designers better balance their compositions so that each composition fits some sort of niche (and is not strictly dominated by all other compositions).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "[Important] Please add simple baselines (average, Elo, mElo) in Table 1.\n\n[Important] The authors need to be careful when talking about space complexity. Significant information will be stored in the weights of the neural network. Having approximately 6x128x128 weights in a neural network to rate compositions with N << 6x128x128 and describing it as O(N) will raise a few eyebrows. Please reword or de-emphasise the space complexity. Or only mention it in the O(M^2) part - where it is better motivated.\n\n[Important] Furthermore the authors need to be careful with time complexity. A lot of network pre-training is involved and the neural network weights cannot be used for different datasets. Therefore it is misleading to say that it only takes O(N+M^3) to do top B balance, because it involves so much pre-training.\n\nThere are a bunch of definitions, assumptions, propositions and lemmas scattered in the text. I did not find this format easy to follow. Is Lemma 5.6 a lemma, for example? The proofs could be more precise. \n\n[Important] The use of neural networks is under-motivated. The main advantage of using a function approximator is to exploit either its a) generalization capabilities, b) representation efficiencies, or c) both. I guess the LOL dataset does have many more possible compositions than examples, but the rest do not, and therefore do not utilize generalization. And for many of the datasets, computing statistics over the whole dataset requires fewer parameters than the number of weights in the network. I think it is particularly important to address this question because the authors use the network to enumerate the O(N) statistics after training it. Why not just compute the exact statistics directly. (I get that there is an implicit defense of this for the O(M^2) residual part, but I think this needs to be addressed directly in the text). \n\nThe method proposed only works with symmetric, 2-player, zero-sum, games. The team games are analyzed as two-player games, where each team is a player. This is not a weakness, as many other rating schemes have this limitation, but I think it should be mentioned in the text.\n\nThe “secret sauce” of the paper seems to be the clustering part which, using a differentiable model, clusters the compositions to allow one to deal with statistics that are only O(M^2). This allows one to scale. I *like* this scalability property - I think that is the interesting part of the paper. I suppose I would have preferred the paper to focus on selling that part rather than distracting the readers with lemmas that do not feel tight, over-emphasising the importance of neural network training, or being a bit misleading with complexity.\n\nI hope this review is helpful and improves your paper.", "broader_impact_concerns": "I have no ethics concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sNyxzFmCu8", "reviewer": "Reviewer_6sdD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* The introduction and application of the dominance based metrics to measure strength and balance in combinatorial spaces with transitivity demonstrates value towards understanding and improving balance in games.\n* The NCT method of learning counter relationships combines several good ideas.\n    * The learning signal is derived from the “residual win value”, identifying that the difference between actual outcome and predicted outcome based on scalar strength contains the composition counter information.\n    * The methods use neural encoding in general and  vector quantization in particular to represent the large composition space in a much smaller and more manageable space with interpretable membership qualities.\n\n\n\n\n# Weaknesses\n* In Tables 1 and 2, several games exhibit large discrepancies between the train and test accuracies which usually indicates overfitting. This is not addressed in the paper. In particular, the proposed NCT method achieves >90% train accuracy on League of legends with only a 51% test accuracy indicating almost no gain over random guessing. \n* The descriptions of the baseline models of WinValue, PairWin, and Bradley-Terry are not described clearly in the same way as NRT and NCT. Additional information is given in the Appendix but this is not mentioned in the baseline descriptions. WinValue and BT appear nearly identical to NRT with WinValue having a difference in the label (win rate vs rating), and BT lacking non-linear activation functions in the network layers. These may be more clearly represented as an ablation of variants of the NRT method.\n* The paper introduces a new method to address low codebook utilisation in vector quantization. While they mention other methods which address this problem, they do not provide a comparison of VQ Mean Loss to any other method. \n* In the case studies, analysis of game balance is made under different experimental settings such as the number of categories. There are some instances of unclear and apparent contradiction in conclusions. In the Hearthstone study authors state that “From Top-D diversity… the balance is not good”, and “If we extend the counter table to M = 9, … the balance is surprisingly good”, and “When we use a larger counter table, M = 27 or M = 81, the game is balanced enough.” All of these experiments are done on the same dataset representing the game in the same state of balance. The descriptions are referring to how the metrics portray balance differently under different settings, not real changes to the balance of the game.\n* In the AoE II and Hearthstone case studies, experiments are run with M=81 indicating 81 composition categories. However in the datasets used there are only 45 comps in AoE II and 58 for Hearthstone after filtering to comps with more than 100 appearances. This means there are more possible categories than compositions in these experiments which runs contrary to the motivation of reducing the comparison space.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces methodologies for comparing the strengths of team compositions, and measuring the degree of balance between compositions in games, with an emphasis on video games. The introduced methods aim to address weaknesses of approaches based on analysis of win-rates by taking into account counter relationships, and using neural representations in embedding space rather to avoid high cost enumeration over the combinatorial space of compositions.\n\nThe paper makes contributions in several areas:\n* The design and training of neural networks to represent team composition strength and counter relationships. This entails encoding team compositions, and using vector quantization to cluster them into a set number of categories, to reduce the complexity of analysing pairs. The authors address the known problem of low codebook utilisation in vector quantization by introducing a new loss term to encourage all codes to move towards the embedded composition, rather than only the nearest neighbour.  \n* Introduction of metrics to quantify the level of balance in a game, in terms of the number of viable compositions. These metrics build on the learned counter relationships to reduce the algorithmic complexity to scale with the number of categories, rather than the number of possible compositions.\n* The paper includes analysis of case studies using the learned ratings, and counter relationships in order to validate the learned relationships with human subject matter expert knowledge, and provide examples of how the knowledge can be used to inform interventions to improve the gaming experience.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "We request additional information and clarification in the following areas:\n\n* Strengthen\n    * In section 4.1, counts of the number of instances, and possible compositions are listed for each of the datasets. It would also be informative to include the number of unique compositions represented in the datasets. This can highlight the differences between games like AoE II where a composition is defined by one of 45 factions, all of which are represented, and League of Legends where the composition space is combinatorial and much larger than the number of instances.\n    * In eqn. 3, the training objective for the NRT method is described as the mean squared error between the match outcome and the predicted match outcome probability. It is more common in Bradley-Terry inspired models to minimise cross entropy due to the probabilistic nature of the variables. An explanation for the choice of mean squared error would strengthen the understanding.\n    * In order to demonstrate the effectiveness of the clustering on the high dimensional compositions spaces, authors may consider adding a case study on a game with combinatorial composition space such as League of Legends or Brawl Stars. While full analysis of all comps is not feasible, distributional level statistics on the cluster membership, and champion cluster membership could be enlightening.\n    * Authors should provide definitions of gaming terminologies such as “buffing” and “nerfing.”\n\n* Critical\n    * An explanation for the train/test discrepancy and low test accuracy for the League of Legends experiments is necessary.", "broader_impact_concerns": "The included broader impact statement adequately covers concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mk91wrXcVX", "reviewer": "Reviewer_F1ex", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper presents a good ablation study providing insightful conclusions. Such a study makes it easier for the reader to understand the effect of hyperparameters on performance based on use cases.\n2. The paper seems very reproducible as the paper + appendix provides most of the details required to reproduce the results. (In any case, I encourage authors to release their code). \n3. The paper discusses literature from both video games as well as ML community, which helps to motivate the importance of the problem being tackled. \n\nWeakness\n1. The writing is not clear in some parts, especially the counter table implementation section. See Requested Changes for more details. \n\n2. The paper does not discuss the related work in an appropriate context. \n     1. E.g., How do the papers Bowling et al. 2015, and Perolat et al. 2022, support your claim that computing Nash equilibrium is expensive in general? Yes, it might be expensive for the games considered, but not for all games (like rock paper scissors). Pendurkar et al. 2023 present such a study. \n     2. Some related (and recent) papers are not discussed (e.g, Hernandez et al 2020., Reis et al. 2023)\n     3. The paper cites Pendurkar et al. 2023 in the section that discusses win rate based metrics (Section 1 Introduction). However, the original paper proposed an entropy-based objective orthogonal to win-rate-based metrics (Not cited when you discuss this in the paper). The authors should avoid citing work in the wrong places.\n3. Comparison with previous work is missing, making the claims of faster evaluation of metrics weaker. The paper needs an empirical study, of when the proposed metrics are faster/slower to evaluate, and how much these metrics differ from one another (discussing the 'quality' of balance). \n\nHernandez, Daniel, et al. \"Metagame autobalancing for competitive multiplayer games.\" 2020 IEEE Conference on Games (CoG). IEEE, 2020.\n\nReis, Simão, et al. \"An Adversarial Approach for Automated Pokémon Team Building and Meta-Game Balance.\" IEEE Transactions on Games (2023).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on the problem of `game balance’ that is prevalent in the current video game industry. Although the problem is prevalent; quantifiable metrics are not standardized to measure game balance. Although some measures based on win rates, and entropy of strategies at Nash equilibrium have been proposed in the current literature, the authors claim such methods can be resource-intensive. They propose learning two models namely, the machine learning based Bradley-Terry model and the machine learning based counter table. The authors use these two models to propose two novel metrics namely Top-D Diversity and Top-B Balance which have a better time/space complexity when compared to win rate based metrics. The authors conclude their paper with an in-depth discussion (ablation study) of the proposed methods, suggesting guidelines for tuning the hyperparameters for specific use cases.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested Changes\n1. I would like to see a comparison of compositions considered balanced with (1) win-rate based method (2) entropy of strategies at Nash equilibrium-based method (Pendurkar et a. 2023). (3) proposed methods. That is, highlighting the differences not only between the proposed methods but also with the current literature to support the claim that calculating the proposed metrics is easier (at least in some cases) and better/comparable. These experiments + addressing related work concerns would address my concerns regarding `Claims And Evidence'\n\nWriting Changes\n1. 'Treant Druid needs a specific nerf’ The ML audience is not familiar with terms like 'nerf’ and 'buff’. Please define them. \n2. In Section 4.1 please mention the composition size per game. (similar to 'k’ and '|M|’ in Pendurkar et al. 2023).\n3. Please cite original work on the siamese neural network (page 2 line 2) (Bromley et al. 1993)\n4. The section on the counter table model is not very clear, especially, because the background is not appropriately introduced. I would suggest authors add a subsection at the beginning that provides some idea on vector quantization training and defines terms like `codebook’. VQ Mean Loss seems like a contribution for the paper, the differences from the literature should be clearly highlighted. \n\nQuestions (I hope authors use my questions to update their paper as well for clarity). \n1. What are gameplay policies used (after composition) for each game to collect the data?\n2. When should one use Top-D Diversity and when should one use Top-B Balance? Such a discussion is missing. Based on my understanding, it seems Top-B is more useful when using counters (see rock-paper-scissors-fire-water variant used in Pendurkar et al. 2023 which might serve as an easy example to demonstrate this). \n3. Are the proposed metrics limited to two-player zero-sum games? What are the challenges if one were to scale them to multi-player games (especially with counter table)? If yes, then please clearly state this while discussing the limitations. \n4. Page 2 para 2. ''which counts.. given a tolerant win value gap’’ what do you mean by `tolerant value group’?\n5. How is Proposition 5.9 True? Do you assume the ML model for BT rating is accurate? Further, maybe countering c1 might be easier than countering c2 (this might happen if the categories are not appropriately identified). In such cases, 5.9 might not hold. Please clarify your assumptions here. \n\nBromley, Jane, et al. \"Signature verification using a\" siamese\" time delay neural network.\" Advances in neural information processing systems 6 (1993).\n\nMinor\n1. Just above Definition 2.1 define the target, ‘’domination,’’ -> ‘‘domination’’,\n2. Ralf Herbrich, Tom Minka, and Thore Graepel. Trueskilltm: A bayesian skill rating system. \nIn Advances in Neural Information Processing Systems (NIPS), 2006. (Apologies for bad formatting here) ™ should be in upper case (so should be B in Bayesian).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers (as well as myself) agree on the relevance of this work to (a subset of) the TMLR audience.

We also mostly agree on the claims of the paper being supported by the experiments and discussion, just with one potential concern remaining regarding the discussion and/or comparison to other types of measures of game balance proposed in prior research. In light of this, **I have the following suggestion for what I think would be a very minor revision** (where I invite the authors to also explain if they feel that this would be a bad change to make):

At the end of the third paragraph of Section 6.3, there is currently one sentence alluding to the regularization term that was proposed by Pendurkar et al. (2023) for their entropy-based approach, which, without such a term, could suffer from the existence of undesirable solutions that maximise entropy simply by making every behave exactly the same (which would be a "balanced" solution with equal win percentages for all comps, but also uninteresting in terms of player experience). More specifically (not yet discussed in your paper), this regularization term punishes the balancing procedure of Pendurkar et al. (2023) for moving game parameters too far away from the initial parameters, where the initial parameters are assumed to have been set by the game designers. This initial game design is likely not solely informed by wishing to produce a balanced game, but also the wish to ensure that certain comps/decks/characters fit specifically designed playstyles, match a certain theme/personality of a character, and so on. My impression is that such considerations would not solely be relevant to the specific algorithm of Pendurkar et al. (2023), but could be a relevant consideration (maybe: a constraint) for **any** measure of game balance. Regardless of which measure of balance a game designer would use (any of the ones proposed in this paper, or others discussed as related work in Section 6.3 of this paper), there would often be a constraint not to drift too far from the original game design.

I would suggest that it may be worth adding a few (e.g., two or three) sentences to discuss these ideas in the larger discussion of Section 6.3.

---

Aside from the above suggestion, I would like to remark to the authors:
- Please do not forget to turn all text back to the regular black text for the camera-ready version.
- Throughout the Appendix, the letter "x" is used in a few places where $\times$ (typeset using `$\times$`) would look much nicer: specifically, when discussing "9x9 counter tables" for Age of Empires 2 and Hearthstone.
Decision: Accept (poster)