Monte Carlo Tree Search for Feature Model Analyses: a General Framework for Decision-Making

Monte Carlo Tree Search for Feature Model Analyses: a General Framework for Decision-Making Jose-Miguel Horcas University of Seville Seville, Spain [email protected] José A. Galindo University of Seville Seville, Spain [email protected] Ruben Heradio National Distance Education University (UNED) Madrid, Spain [email protected] David Fernandez- Amoros UNED Madrid, Spain [email protected] David Benavides University of Seville Seville, Spain [email protected] ABSTRACT The colossal solution spaces of most configurable systems make intractable their exhaustive exploration. Accordingly, relevant analyses remain open research problems. There exist analyses alternatives such as SAT solving or constraint programming. However, none of them have explored simulation-based methods. Monte Carlo-based decision making is a simulationbased method for dealing with colossal solution spaces using randomness. This paper proposes a conceptual framework that tackles various of those analyses using Monte Carlo methods, which have proven to succeed in vast search spaces (e.g., game theory). Our general framework is described formally, and its flexibility to cope with a diversity of analysis problems is discussed (e.g., finding defective configurations, feature model reverse engineering or getting optimal performance configurations). Additionally, we present a Python implementation of the framework that shows the feasibility of our proposal. With this contribution, we envision that different problems can be addressed using Monte Carlo simulations and that our framework can be used to advance the state of the art a step forward. KEYWORDS configurable systems, variability modeling, feature models, Monte Carlo tree search, software product lines 1 INTRODUCTION The Automated Analysis of Feature Models (AAFM) [ 9 , 58 ] is one of the most active Software Product Line (SPL) research areas in the last decade [ 8 ]. In highly configurable systems, the AAFM is a challenging task because it requires to cope with numerous interrelated features and colossal configuration spaces. For example, we find multiple operations such as counting the number of products [ 23 , 35 , 70 ] and optimizing configurations [ 30 , 37 , 49 ] that are performed over the whole configuration space. Also, there are operations that are performed over the feature models (e.g., evolution [ 44 ] and reverse engineering [ 18 , 43 ]). Finally, there are other analyses over the products (e.g., testing [ 26 , 57 ]) or over the constraints of the feature models [69]. Many of these analyses have to to deal with uncertainty, as undertaking an exhaustive exploration of the whole configuration space is usually intractable. In addition, other relevant analyses have not been explored in-depth yet. In some cases, complex computations are required to take simple actions. For instance, deciding when to include or exclude a feature in a configuration impacts the convenience and analysis of further selections [ 54 , 55 ]. Moreover, those decisions are not commonly intuitive. For instance, when reverse engineering feature models, practitioners have to decide the structure of the resulting feature model in terms of the parent-child relationships [ 4 , 43 ]. Other situations require tackling uncertainty because of the aforementioned combinatorial nature of the configuration space. For instance, solving analyses of probability in configuration selections according to performance is challenging [48, 53]. When coping with large search spaces, existing techniques present several drawbacks [ 58 ]. AAFMs have relied on propositional logic or SAT solving [ 7 , 67 ], constraint programming [ 9 ], Binary Decision Diagrams (BDD) [ 22 , 35 ], statistical analysis [ 33 ], genetic algorithms [ 42 , 43 ], or metaheuristics [ 75 ], among others [ 25 ]. However, SAT solvers could face scalability problems for large-scale models [ 67 ], statistical analysis [ 32 , 33 ] require the construction of BDDs, which can be intractable [ 70 ] and other approaches like genetic algorithms [ 42 , 43 ] and metaheuristics [ 75 ] require to incorporate specific domain knowledge, and analyzing and inferring results from the final solutions which is not straightforward. In this paper, we present a conceptual framework based on socalled Monte Carlo methods [ 39 ], which use randomness for deterministic problems that are difficult or impossible to solve using traditional approaches. They can be used with little or no domain knowledge, and have succeeded on difficult problems where other techniques have failed. In particular, we adopt the Monte Carlo Tree Search (MCTS) [ 12 , 14 ] method. MCTS has been successfully applied to several domains [ 12 ], standing out in game theory [ 65 ] where has been shown to scale to large search spaces such as those that typically characterize SPLs. Thus, we conjecture that MCTS will show great promise in the AAFMs. In this paper, we make the following contributions: •We formally present our MCTS framework (Section 2). • We identify a set of analysis problems in SPL that can be worthy of examining with the MCTS method, and map them to the conceptual framework (Section 3). • We formally describe different problems over configurations (Section 4) and features models (Section 5) using our framework, and explain the knowledge we can infer with MCTS. • We provide a Python implementation of our proposal (Section 6) 1 . MCTS has already had a profound impact onartificial intelligence for domains that can be represented as trees of sequential decisions, particularly games and planning problems. With this contribution, we envision that different problems can be addressed using Monte Carlo simulations and that this new approach can be of big value to advance the state of the art of the AAFMs a step forward. 2 MONTE CARLO TREE SEARCH This section presents our conceptual framework (Section 2.1) to model problems that can be solved with Monte Carlo methods, and especially with the Monte Carlo Tree Search method (Section 2.2). 2.1 MCTS conceptual framework Monte Carlo Tree Search (MCTS) [ 14 ] is a method for finding optimal decisions in a given domain by taking random samples in the decision space and building a search tree according to the results. The resulting search tree is then used for possible future decisions. MCTS is based on decision and game theory [ 62 ], and on Monte Carlo [ 39 ] and bandit-based methods [ 47 ], where sequential decision problems are modeled as a Markov Decision Process [ 62 ] with the following elements (𝑆, 𝑠0, 𝑡, 𝐴,𝜃, 𝜇): •𝑆: the set of states. •𝑠0∈𝑆 : the initial state which specifies how the problem is set up at the start. •𝑡 : 𝑆→B : a terminal condition, which is true when the problem is over (i.e., there are no more decisions to be taken) and false otherwise. States where no more decisions can be taken are called terminal states. The set of terminal states is called 𝑆𝑇⊆𝑆 . •𝐴 : the set of valid actions. An action is valid if it can be applied to a state under a certain condition of applicability. •𝜃 : 𝑆×𝐴→𝑆 : the state transition function, which defines the result of applying an action, leading to a new successor state. •𝜇 : 𝑆→R :reward function (also known as utility,objective or payoff function). It defines the final numeric value for a problem that ends in a terminal state 𝑠𝑡∈𝑆𝑇. As illustrated in Figure 1 (a), the initial state 𝑠0 , the set of actions 𝐴 , and the transition function 𝜃 define the search space for the problem — i.e., a tree where each node represents a state of the domain, and directed links to child nodes represent actions leading to successor states. Thus, overall decisions are modeled as sequences of (𝑠𝑡𝑎𝑡𝑒, 𝑎𝑐𝑡𝑖𝑜𝑛) pairs. Monte Carlo methods are used to decide the optimal decision (i.e., choosing an action) from a given state 𝑠 by running simulations. A simulation is a random or statistically biased 1https://github.com/diverso-lab/fm_montecarlo  ŝŶŝƚŝĂůƐƚĂƚĞ Ɛ Ϭ    ƉƉůŝĐĂďůĞ ĂĐƚŝŽŶƐĨŽƌ Ɛ Ϭ ƐƵĐ ƐŽƌƐ ŽĨ Ɛ Ϭ ƌĞǁĂƌĚǀĂůƵĞŽĨ ƚĞƌŵŝŶĂůƐƚĂƚĞ Ɛ ƚ  Ɛ nj ŝ ŝ ƚŚ ƐŝŵƵůĂƚŝŽŶ Y;ƐĂ ϭ Ϳ E;ƐͿ Ă ϭ Ă Ϯ Ă Ŷ Y;ƐĂ Ŷ ͿY;ƐĂ Ϯ Ϳ Ɛ ƚ ;ĂͿ^ĞĂƌĐŚƐƉĂĐĞ ;ďͿDŽŶƚĞĂƌůŽƐŝŵƵůĂƚŝŽŶƐ >ĞŐĞŶĚ ƐƚĂƚĞƐ ŝŶŝƚŝĂůƐƚĂƚĞ ƚĞƌŵŝŶĂůƐƚĂƚĞƐ ĂĐƚŝŽŶƐ Figure 1: Problem modeled as a sequence of (𝑠𝑡𝑎𝑡𝑒, 𝑎𝑐𝑡𝑖𝑜𝑛)decisions (a), and the Monte Carlo simulations approach (b). sequence of actions applied to the given state until a terminal terminal state 𝑠𝑡 is found. The terminal state 𝑠𝑡 is then evaluated using the reward function 𝜇 and obtaining a reward value 𝑧𝑖 associated with that simulation, as shown in Figure 1 (b). Running a number of simulations 𝑁 from the given state 𝑠 , Monte Carlo approximates the expected reward of each action that can be performed from that state 𝑠 ,i.e., 𝑄(𝑠, 𝑎) . The expected reward of an action is called the 𝑄 -value (also called Monte-Carlo value or MC value) [ 29 ] of that action and is defined as the mean of all rewards obtained from the simulations performed from state 𝑠choosing the action 𝑎: 𝑄(𝑠, 𝑎)=1 𝑁(𝑠, 𝑎) 𝑁(𝑠) Õ 𝑖=1 I𝑖(𝑠, 𝑎)𝑧𝑖(1) where 𝑁(𝑠, 𝑎) is the number of times action 𝑎 has been selected from state 𝑠 ; 𝑁(𝑠) is the number of times a simulation has been run from state 𝑠 ; 𝑧𝑖 is the reward result of the 𝑖 th simulation; and I𝑖(𝑠, 𝑎) is 1 if action 𝑎 was selected from state 𝑠 on the 𝑖 th simulation run from state 𝑠or 0 otherwise. A great benefit of Monte Carlo methods is that the values of intermediate states do not have to be evaluated. Only the value of the terminal state at the end of each simulation is required. 2.2 The Monte Carlo Tree Search method The MCTS method [ 14 ] extends the Monte Carlo principles by using the expected reward ( 𝑄 -values) obtained from simulations to build an incremental and asymmetric search tree which is then used for subsequent decisions. As shown in Figure 2, the basic algorithm of MCTS (summarized in pseudocode in Algorithm 1) involves iteratively building and using a search tree until some predefined computational budget (e.g., time, memory, number of iterations) is reached. Four steps are applied per search iteration [14]: (1) Selection. Starting with the initial state 𝑠0 , the search tree is traversed by recursively applying a selection function from the root node until a leaf node 𝑠𝑙 is reached. Several strategies for selecting the nodes in the tree can be found in [ 12 ]. The most popular one is the upper confidence bound for trees (UCT) [ 38 ] that, using the 𝑄 -values, attempts to balance exploitation (i.e., look in areas which appear to be promising) and exploration (i.e., look in areas that have not been well explored yet). (2) Expansion. From the selected leaf state 𝑠𝑙 , one or more child nodes are added to expand the tree according to the actions 𝐴. (3) Simulation. A simulation is run from the new node(s) by making random actions until a terminal state is reached. The terminal state is evaluated, producing an outcome 𝑧 (i.e., the reward value). 1. The tree search is recursively transversed until a leaf node is reached 2. One or more nodes are added to the search tree 3. A simulation is run taking random choices 4. The reward result of the simulation is backpropagated in the tree BackpropagationSelection Expansion Simulation Repeated X times Figure 2: The MCTS approach (adapted from [14]). Algorithm 1 General Monte Carlo Tree Search method. 1: procedure MCTS(𝑠0) 2: while within computational budget do 3: 𝑠𝑙←SELECTION(𝑠0)⊲Apply the child selection tree policy. 4: EXPANSION(𝑠𝑙)⊲Add one or more nodes to the search tree. 5: 𝑧←SIMULATION(𝑠𝑙)⊲Apply the default policy. 6: BACKPROPAGATION(𝑧, 𝑠𝑙)⊲Backup the reward. 7: end while 8: return BEST_ACTION(𝑠0) 9: end procedure (4) Backpropagation. We update the statistics of each state in the tree that was traversed during the selection step. That is, the visit counts 𝑁(𝑠, 𝑎) are increased, and the expected reward 𝑄(𝑠, 𝑎) is modified according to the outcome 𝑧from the simulation. As soon as the search terminates, the best action of the initial state 𝑠0 is selected ( BEST_ACTION(𝑠0) ). Several criteria are described in [ 15 ], such as choosing the action with the highest reward. In addition to the best decision, MCTS also provides useful knowledge in the form of statistics stored in the tree search that can be used to make analyses, as we will show throughout the paper. 3 AUTOMATED ANALYSIS OF FEATURE MODELS WITH MCTS In this section we present our running example, and identify a set of problems to be formalized and analyzed with the MCTS framework. 3.1 Preliminaries and running example Definition 3.1 (Feature, Feature model). Afeature 𝑓 is a characteristic or end-user-visible behavior of a software system [ 2 ]. A feature model 𝑚 is a set of features 𝐹 and their relationships. Formally, a feature model 𝑚is defined as a 4-tuple (𝐹,𝑟, R,Π): •𝐹is a finite set of features. •𝑟∈𝐹is the root feature. • R ⊆ 𝐹×𝐹𝑛×𝜆 is a decomposition relation representing the relationship of a parent feature and its 𝑛 sub-features with a multiplicity 𝜆 , where the lower and the upper bounds are the minimal and the maximal number of features that can be selected in a configuration. We use the notation (𝑓 , [𝑔1,𝑔2, . . . , 𝑔𝑛],⟨𝑎..𝑏⟩) to represent the elements of 𝑅 meaning that 𝑓 is the parent of sub-features 𝑔𝑖, 1 ≤𝑖≤𝑛 with a multiplicity of ⟨𝑎..𝑏⟩ . We use ⟨ 0 .. 1 ⟩ for optional features and ⟨ 1 .. 1 ⟩ for mandatory features when 𝑛= 1; and ⟨ 1 .. 1 ⟩ for alternative-groups and ⟨ 1 ..𝑛⟩ for or-groups when 𝑛> 1. For convenience, we will also use the notation 𝑓≺𝑔 to represent that feature 𝑓 is the parent of feature 𝑔 regardless multiplicity; and we use the notation 𝑓≺≺ 𝑔 to represent that feature 𝑓is an ancestor of feature 𝑔. •Π is a set of cross-tree constraints defined as arbitrary propositional formulas over the set of features 𝐹,i.e., Π⊆B(𝐹). Legend: AAFMFramework Packages Solvers System pycosatpython-sat pyGlucose pyPicosat MiniSAT PicoSAT Glucose Linux Win PicoSAT => pycosat ∨ pyPicosat Glucose => python-sat ∨ pyglucose MiniSAT => python-sat Win => ¬ pyPicosat PicoSAT => pycosat ∨ pyPicosat Glucose => python-sat ∨ pyglucose MiniSAT => python-sat Win => ¬ pyPicosat mandatory optional or group alternative group Figure 3: SPL for an AAFMs framework in Python. Figure 3 shows a feature model representing a product line for a Python framework to support AAFMs [ 24 ]. AAFMFramework is the root of the feature model. The mandatory relation between the root and the System feature can be described by the relation ( AAFMFramework , [ System ], ⟨ 1 .. 1 ⟩ ), while the relations between the AAFMFramework feature and its optional children are described by the relations ( AAFMFramework , [ Packages ], ⟨ 0 .. 1 ⟩ )and ( AAFMFramework , [ Solvers ], ⟨ 0 .. 1 ⟩ ), respectively. To reason about the models and implement the analysis operations, the framework can use a selection of Solvers represented by the or-group relation ( Solvers , [ MiniSAT , PicoSAT , Glucose ], ⟨ 1 .. 3 ⟩ ). Each solver will require one or more Python package which offer the implementation for that solver. For instance, the MiniSAT solver is provided by the python-sat package, while the PicoSAT solver is offered by the pycosat or by the pyPicosat packages. These kind of relations are represented as textual cross-tree constraints in the feature model, as for example PicoSAT ⇒pycosat ∨pyPicosat . Finally, a specific version of the framework can be deployed in Linux or Win dows systems, relation represented by the alternative-group (System, [Linux,Win], ⟨1..1⟩). Definition 3.2 (Configuration, Partial Configuration, Valid Configuration). Aconfiguration 𝑐 of a feature model 𝑚 is a subset of its features, i.e., 𝑐∈ P(𝐹) , meaning that features in 𝑐 have been selected as part of the configuration 𝑐 . Other features in 𝐹 are considered as not selected as part of the configuration 𝑐 . A configuration 𝑐 is partial if there are features in 𝐹 that need to be still decided in order to be selected or not selected as part of the configuration 𝑐 [ 7 ]. A configuration is valid if and only if it fulfills all the feature dependencies of 𝑚 . The feature dependencies of 𝑚 are given by the set of decomposition relations R (i.e., the tree hierarchy) and the set of cross-tree constraints Π . A partial configuration is valid if the selected features do not neglect the dependencies of 𝑚. An example of a valid configuration of the feature model depicted in Figure 3 is {AAFMFramework , System , Linux , Solvers , MiniSAT , Packages , python-sat} . An example of a valid partial configuration is {AAFMFramework,System,Solver}. 3.2 Types of analyses with MCTS In SPL, MCTS can be applied to find optimal decisions in problems where decisions can be difficult to handle and take because of the high number of potential configurations, products, and variants. Some of the analyses that can be performed with MCTS include: Analyses of complex systems from simple actions .There are problems where we can easily measure the complete set of actions within the system but we are unsure of the aggregate result. For example, selecting a feature to be incorporated in a product is a very simple action to model, but analyzing how that feature selection contributes to the complete product is challenging due to the existing relations in the feature model and the cross-tree constraints [ 63 ]. Here, MCTS can examine how each feature selection contributes to the complete product by modeling the feature selection optimization problem [ 20 , 30 , 74 , 75 ] as a sequence of decision steps. We illustrate this type of analysis in Section 4. Analyzing unintuitive results . There are problems where the current solution is not the only possible solution. For instance, multiple feature models can be extracted from a given set of configurations (this problem is known as reverse engineering of feature models [ 18 , 43 ]). Without taking into account domain knowledge, features appearing in all products (i.e., the core features [ 9 ]) may be considered interchangeable in the resulting feature model. Here, MCTS can help us exploring the alternatives that we may pass unnoticed if we simply observe the extracted feature model. We show this type of analysis in Section 5. Analyses of the uncertainty . There are problems that require handling uncertainty due to the impossibility of dealing with the complete search space. An example is the optimization of configurations based on non-functional properties in large-scale feature models [ 30 , 37 ]. Best configurations may be spread across the configuration space, leading to a search-based software engineering technique to deal with many local optima [ 42 ]. In this case, MCTS is useful to incorporate probability into the analysis. MCTS helps us understanding the probability distribution of the best configurations and analyzing how such distribution will impact the searchbased optimization, so that we can penalize the uncertainty or incorporate it into the search-based technique. In addition to those analyses, in general, MCTS may be used for analyses that have a probabilistic interpretation [ 33 ] or where simulation rather than optimization is the most effective decision support tool [ 12 ]. As stated by Schmid [ 1 ], Monte Carlo techniques can be promising for sensitivity analyses, but they require a sound understanding of the uncertainty in the problem to be analyzed for achieving correct and useful results. 3.3 Mapping to MCTS conceptual framework In order to apply the MCTS method to the AAFMs, we need to formulate the problems as a sequence of (𝑠𝑡𝑎𝑡𝑒, 𝑎𝑐𝑡𝑖𝑜𝑛) decisions using the conceptual framework (𝑆, 𝑠0, 𝑡, 𝐴, 𝜃, 𝜇) introduced in Section 2.1. Figure 4 shows a list of SPL problems that can be described as a sequence of decisions and mapped to the MCTS conceptual framework. The most important definition is the concept of state, and thus, we classify the problems according to what a state represents. In SPLs, a state may represent a configuration of a feature model, a partial configuration, a final product, a feature model, an extended feature model, a sample of configurations, a performance model of a sample of configurations, a variation point and the set of its variants to be decided, etc. The definition of the state will depend on the problem’s nature. For example, in product configuration problems, the states will represent configurations (valid or invalid) of a feature model, partial configurations, or both partial and complete configurations; while in problems dealing with the evolution of feature models, a state will represent a feature model itself. Each definition of state will lead to a different set of actions. States representing configurations will define actions that allow moving from one configuration to another (e.g., actions for selecting a feature and A state is a feature model Applicable problems • Reverse engineering of feature models • Evolution of feature models • ... A state is a configuration of a feature model Applicable problems • Finding minimum valid configurations • Completion of partial configurations • Localizing defective configurations • Optimization of configurations • ... Others definitions of state Examples and applicable problems • A state is a product of an SPL (e.g., test suite priorization problem) • A state is a configuration + variation point (e.g., next release problem) • A state is a (feature, attributes) pair (e.g., QAs generation problem) • A state is a sample of configuration (e.g., feature interaction coverage) • ... States (S): Configurations of a feature model (e.g., configurations, partial configurations,…) Actions (A): Selection/Deselection of features (e.g., select root feature, select mandatory feature, select optional feature, select feature alternative,…) s0tµ s0tµ s0tµ s0tµ s0tµ s0tµ s0tµ s0tµ States (S): Feature models (e.g., feature models, cardinalitiy-based, extended feature models,…) Actions (A): Creation/Modification of features, relations, and constraints (e.g., add root feature, add optional feature, add mandatory feature, add alternative-group relation, add or-group relation, add feature to alternative-group, add feature to orgroup, add requires constraint, add excludes constraint,…) s0tµ s0tµ s0tµ s0tµ θθ s0tµ θA S s0tµ θA S s0tµ θA S s0tµ θA S s0tµ θA S s0tµ θA S s0tµ θA S s0tµ θA S Figure 4: Mapping of SPL problems to the MCTS framework. adding it to the configuration). States representing feature models will define actions to modify the feature models (e.g., adding a new mandatory or optional feature to the model). Different definitions of states and actions will lead to a different search space. Some of the definitions in the framework (𝑆, 𝑠0, 𝑡, 𝐴,𝜃, 𝜇) can be shared across several problems, while others will be specific of a particular situation or problem instance. On the one hand, the set of actions and the transition function are normally reused across different problems that share the same definition of state. For example, the actions for selecting a feature in problems where a state represents a configuration. On the other hand, the initial state 𝑠0 , the terminal condition 𝑡 , and the reward function 𝜇 are problem specific or even different for a specific instance of a particular problem. For example, the initial state is different in each problem instance of the completion of partial configurations being the initial state a different input partial configuration. The terminal state can also be instance-specific, such as in the problem of the feature interaction coverage, where a state represents a set of configurations and a terminal condition can be a sampling of configurations satisfying the 𝑡-wise coverage for a specific feature [57]. In the following, we detail how to model different types of SPL problems using the MCTS conceptual framework and analyze them. 4 CONFIGURATION BASED ANALYSIS One of the most important and widely studied types of problems in AAFMs deal with feature model configurations. Example of these problems are the optimization of configurations according to non-functional properties [ 30 , 63 , 75 ], the completion of partial configurations [ 71 ], the localization of defective configurations in SPL testing [ 10 , 11 , 28 , 31 ], or the diagnosis of configurations [ 21 , 71 ], among other many problems. In order to analyze this kind of problems with MTCS, we first model the concepts that are shared among these problems. That is the definition of the set of states 𝑆 , the set of actions 𝐴, and the state transition function 𝜃. The set of states 𝑺 is the set of all possible configurations of the feature model. Depending on the definitions of the actions, 𝑆 may consider either valid/invalid configurations or both. The set of actions 𝑨 . There are multiple possibilities to define the set of valid actions that can be performed over a given configuration. An action is valid if it can be applied to a state under a certain condition of applicability (CA). The most basic action is to select a random feature of 𝐹 (see the formalization of the action 𝑎0 in Appendix A). This action is independent of the relations defined in the feature model (Definition 3.1), and thus it can be used for any other definition of feature model as long as it is based on a set of features. However, this action leads to an intractable search space with all possible valid and invalid configurations (i.e., 𝑆 = P(𝐹 ) ) where most of the states represent invalid configurations. Note that the search space is bigger than 2 𝐹 because we can reach the same configuration through a different sequence of actions. A more convenient definition for the actions is considering the relations of the feature model, reducing the resulting search space. Following our Definition 3.1 for feature models, we define the following set of actions 𝐴 = {𝑎1, 𝑎2, 𝑎3, 𝑎4, 𝑎5} (see formalization of the actions in Appendix A): select root feature ( 𝑎1 ), select mandatory feature ( 𝑎2 ), select optional feature ( 𝑎3 ), select feature alternative ( 𝑎4 ), and select feature selection (𝑎5). Note that the configuration is always built from scratch step by step. In each execution of the MCTS method, a unique feature will be selected following the tree hierarchy structure of the feature model. This way, we do not need to define actions for de-selecting a feature and avoid cycles in the tree search space. The successive application of the actions 𝐴 assures the validity of the (partial) configurations according to the tree hierarchy structure of the feature model, but not for cross-tree constraints. We can define a generic condition of applicability for all actions so that an action can only be applied if the resulting partial configuration does not violate any relation nor constraints in the model (e.g., checking it with a SAT solver). The state transition function 𝜽 : 𝑺 ×𝑨 → 𝑺 defines the result of applying an action 𝑎 ∈ 𝐴 to the given configuration 𝑐 . Starting from the initial empty configuration 𝑐0 and iteratively applying the state transition function with all possible applicable actions, we could build the whole search space. However, this is an intractable task, and the Monte Carlo methods, and in particular MCTS, will explore the search space resulting of applying the transition function only to the most promising pairs of (𝑠𝑡𝑎𝑡𝑒, 𝑎𝑐𝑡𝑖𝑜𝑛). The initial state, the terminal condition, and the reward function are specific for each problem. In the following, we show how to model three concrete problems where a state represents a configuration by providing complete definitions of the concepts (𝑆, 𝑠0, 𝑡, 𝐴, 𝜃, 𝜇) . 4.1 Localizing defective configurations A common problem in software testing and maintenance is to identify the configurations that lead to a given defect or some other undesired program behavior [ 10 , 28 , 31 ]. Continuing with our running example, let us suppose we want to identify those valid configurations in our feature model (Figure 3) that present anomalies when they are deployed. Anomalies in the Python framework for AAFMs may happen due to incompatible versions of packages, deprecated libraries, or some other errors. Despite those defective configurations can be found with a search-based software engineering technique [ 42 ], localizing the feature that causes the configuration to fail is not an easy task due to the complex relations between the features, requiring complex analysis for the complete configuration. Moreover, Python packages are often updated and may cause breaking changes. Kästner et al. [ 11 ] define a breaking change as any change in a package that would cause a fault in a dependent package if it were to adopt that change blindly. Thus, in order to provide a robust Python Framework for AAFMs, apart from identifying the defective configurations, we need to identify those features that Step 1 AAFMFramework Step 3 AAFMFramework Packages Solvers System pycosatpython-sat pyGlucose pyPicosat 1.00 0.00 0.33 0.76 0.00 0.67 Step 4 AAFMFramework Packages Solvers System pycosatpython-sat pyGlucose pyPicosat 1.00 1.00 1.00 1.00 1.00 Step 2 AAFMFramework Packages Solvers System 0.00 0.281.00 1.00 + -normalized Q-values [0.00, 0.20) [0.20, 0.40) [0.40, 0.60) [0.60, 0.80) [0.80, 1.00] Figure 5: Step-wise decisions for defective configurations. cause the defects. Using a step-wise decisions approach, we can infer which feature(s) is causing the configuration to fail. Modeling the problem .We model this problem in the MCTS conceptual framework (𝑆,𝑠0, 𝑡, 𝐴, 𝑓 , 𝜇)as follows: •𝑆=P(𝐹) : the set of all possible configurations of the feature model, including partial and complete configurations. •𝑠0=∅ : the initial state is the empty configuration where no feature has been already selected. • The terminal condition 𝑡 determines that a configuration is terminal if it is a valid complete configuration or no more valid actions can be applied to the configuration: 𝑡(𝑠)=𝑇𝑟𝑢𝑒, if 𝑖𝑠_𝑣𝑎𝑙𝑖𝑑 (𝑠) ∨ 𝑎𝑝𝑝𝑙𝑖𝑐𝑎𝑏𝑙𝑒_𝑎𝑐𝑡𝑖𝑜𝑛𝑠 (𝑠)=∅, 𝐹𝑎𝑙𝑠𝑒, otherwise The is_valid(s) operation [ 9 ] is performed with a SAT solver. • The set of valid actions 𝐴={𝑎1, . . . , 𝑎5} defined in Appendix A. • The state transition function 𝜃 : 𝑆×𝐴→𝑆 is given by the definitions of the actions and their conditions of applicability. •The reward function 𝜇for a terminal configuration: 𝜇(𝑠)=𝑒𝑟𝑟𝑜𝑟𝑠 (𝑠),if 𝑖𝑠_𝑣𝑎𝑙𝑖𝑑 (𝑠) ∧ 𝑒𝑟𝑟𝑜𝑟𝑠 (𝑠)>0 −1,otherwise where 𝑒𝑟𝑟𝑜𝑟 (𝑠) is a function that counts the number of errors that the configuration presents when it is deployed. In our running example, this value corresponds with the number of Python packages selected that raise errors when installing them. The reward value of partial and invalid configurations, as well as for those valid configurations that do not contain errors is -1. Algorithm 2 Generic algorithm to solve a problem with MCTS. 1: procedure FindSolution(𝑠0) 2: 𝑠𝑡𝑎𝑡𝑒 ←𝑠0 3: while not 𝑖𝑠_𝑡𝑒𝑟𝑚𝑖𝑛𝑎𝑙 (𝑠𝑡𝑎𝑡𝑒)do 4: 𝑠𝑡𝑎𝑡𝑒 ←𝑀𝐶𝑇𝑆 (𝑠𝑡𝑎𝑡𝑒)⊲Run the MCTS (Algorithm 1). 5: end while 6: return 𝑠𝑡𝑎𝑡𝑒 7: end procedure Solving the problem and analyzing results .We can solve this problem by consecutively applying MCTS from the initial empty configuration (Algorithm 3). Each execution of the MCTS method (line 3) will decide and add the most promising feature to the current configuration following the four steps of the MCTS method presented in Section 2.2. The most promising feature is the next feature in the tree hierarchy of the feature model (according to actions 𝐴 ) that moves the configuration closer to the complete valid Algorithm 3 Finding defective configurations with MCTS. 1: procedure FindDefectiveConfiguration(𝑠𝑡𝑎𝑡𝑒) 2: while 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑠𝑡𝑎𝑡𝑒) ≤ 0and 𝑎𝑐𝑡𝑖𝑜𝑛𝑠 (𝑠𝑡𝑎𝑡𝑒)≠∅do 3: 𝑠𝑡𝑎𝑡𝑒 ←𝑀𝐶𝑇𝑆 (𝑠𝑡𝑎𝑡𝑒)⊲Run the MCTS (Algorithm 1). 4: end while 5: if 𝑟𝑒𝑤𝑎𝑟𝑑 (𝑠𝑡𝑎𝑡𝑒)> 0 then ⊲Defective configuration found! 6: return 𝑠𝑡𝑎𝑡𝑒 7: else 8: return 𝐹𝑎𝑙𝑠𝑒 9: end if 10: end procedure configuration with more number of errors. We modify the stopping condition of the generic Algorithm 2 so that the search will run until a configuration with errors is found or no valid actions can be applied to the current configuration (line 2 in Algorithm 3). The execution of the algorithm is illustrated step by step in Figure 5. We use a data visualization technique called heat maps [ 41 , 72 , 73 ]. A heat map encodes quantitative values as colors (like in the weather maps), so that it compacts large amounts of information (our 𝑄 - values) to bring out coherent patterns in the data (optimal feature selections over the feature model). As shown in Figure 5, we use a grey-scale heat map for each algorithm step representing the contribution of each feature selection, where darker colors mean a higher probability of finding a defective configuration if that feature is selected. Given the empty configuration as initial state, in the first step, the only action available is to add the root feature AAFMFramework (Step 1 in Figure 5). In Step 2, three possible features can be added to the configuration according to the set of actions 𝐴 . To make a choice, MCTS performs a number of simulations (e.g., 100) that consist in completing the configuration with random selections (always following the set of actions 𝐴 ), evaluating the number of errors for the complete configuration achieved in each simulation, and gathering the statistical outcomes of the simulations as explained in Section 2.1 — i.e., the 𝑄 -values. Figure 5 shows normalized 𝑄 -values in range [ 0 , 1 ] , being 1 the most promising feature decision. In Step 3, the pyPicosat package is selected as part of the configuration, while, in Step 4, any possible decision will lead to defective configuration (i.e., all candidate features are 𝑄 -values 1). This suggests that the previous choice ( pyPicosat ) is the feature provoking the failure. The algorithm will continue completing the configuration with a valid selection of features (e.g., selecting mandatories features), but MCTS has only needed four steps to discover the problematic feature. The algorithm finishes when it find a valid defective configuration, as for example the final state found: { AAFMFramework , Solvers , System , Linux , Packages , pyPicosat , PicoSAT }. As Figure 6 shows, when deploying that configuration in Python some errors raise: the package pyPicosat cannot be correctly installed in Linux. In fact, following this procedure, we found that deploying any configuration containing the pyPicosat feature in the Linux system, leads to failures, so we may decide to update the constraint ( Win ∨Linux ⇒ ¬ pyPicosat ) converting it into a dead feature [9]. Using the knowledge gathered by MCTS in the tree search, we can infer two interesting results: (1) which features are more probable to be the cause provoking the defect in the configuration; and (2) which features are contributing more to the solution obtained, so that we may find additional defective configurations by following the sequence of feature selections done by MCTS to find the current Figure 6: Deploying a defective configuration. configuration. In the following section, we show how we can solve another problem where a state represents a configuration by only modifying the reward function and reusing the other definitions. 4.2 Finding minimum valid configurations In our running example, a requirement for the development of the AAFMs framework in Python is to depend on the smallest number of third-party packages as possible. Thus, we are interested in finding a valid configuration with the minimum number of features. Modeling the problem .We reuse the definitions of (𝑆, 𝑠0, 𝑡, 𝐴,𝜃) of the previous problem and modifying the reward function 𝜇. The reward function 𝜇 counts the difference between the number of features in the feature model ( |𝐹| ) and the number of features in the configuration represented by the state 𝑠. 𝜇(𝑠)=|𝐹| − |𝑠|,if 𝑖𝑠_𝑣𝑎𝑙𝑖𝑑 (𝑠) −1,otherwise Solving the problem and analyzing results .We use generic Algorithm 2 where the terminal condition checks if the current state is a complete valid configuration. Figure 7 shows the number of decisions (features) taken by MCTS to find minimum valid configurations starting from the empty configuration. We run 30 executions for each number of iterations (simulations). Using the complete version of the AAFMs Python framework (see Section 6), we can observe as the number of decisions decreases as long as we increase the number of simulations, improving the solutions found. In this problem, the tree search built by MCTS contains statistical information regarding decisions to select the minimum set of features to form a valid configuration. Figure 8 shows the resulting heat map with the accumulated 𝑄 -values when we use a partial configuration as initial states (as we will show in the following section). 𝑄 -values capture the expected reward of a decision if we decide to make such choice. When using the empty configuration as initial state, higher 𝑄 -values indicate which feature may be selected to obtain a minimum valid configuration, and features in darker colors will approximate to the core features. In addition, the heat map shows the feature pyPicosat in blank, indicating that it has never been considered in a decision. Effectively, the constraint we updated ( Win ∨Linux ⇒ ¬ pyPicosat ) prevents that feature from being part of any configuration, indicating that it is a dead feature. 4.3 Completion of partial configurations The previous problem of finding minimum valid configurations can be seen as a specialization of the problem of completing partial configurations [ 71 ]. The completion of partial configuration problem 20 40 60 80 100 0 10 20 30 40 50 Simulations Features (decisions) Valid configurations Median Figure 7: Finding minimum valid configurations. AAFMFramework Packages Solvers System pycosatpython-sat pyGlucose pyPicosat 0.08 0.02 0.16 0.14 MiniSAT PicoSAT Glucose Linux Win PicoSAT => pycosat ∨ pyPicosat Glucose => python-sat ∨ pyglucose MiniSAT => python-sat Win ∨ Linux => ¬ pyPicosat PicoSAT => pycosat ∨ pyPicosat Glucose => python-sat ∨ pyglucose MiniSAT => python-sat Win ∨ Linux => ¬ pyPicosat 0.14 0.16 0.52 1.00 0.00 + -normalized Q-values 0.00 User selection Dead feature Figure 8: Heat map for completion of partial configurations. consists of finding the set of non-selected features necessary for getting a complete valid configuration. While in a complete configuration each feature is decided to be either present or absent in the resulting configuration, in partial configurations, some features are undecided (see Definition 3.2). In our case study, let us suppose we have decided to use the Glucose solver in our AAFMs framework. We are interested in finding the minimum valid complete configuration with such user’s requirement. Modeling the problem .We modify the initial state 𝑠0 , while leaving the other definitions (𝑆, 𝑡, 𝐴,𝜃, 𝜇) as in the previous problem. In order to provide a valid initial state 𝑠0 to the MCTS method so that 𝑠0 does not violate the tree hierarchy of the feature model and allows applying our actions 𝐴={𝑎1, . . . , 𝑎5} , we pre-process the initial configuration provided by the user by recursively selecting all parents for the features already selected. If the resulting partial configuration does not violate the tree hierarchy nor cross-tree constraints, we can use it as initial state for MCTS. In other case, the partial selection made by the user is not valid. Solving the problem and analyzing results .We use the features {AAFMFramework , Solver , Glucose} as initial configuration and execute Algorithm 2 where the terminal condition checks if the current state is a valid complete configuration, as in the previous problem. Figure 8 shows the resulting heat map for completing the partial configuration given as initial state by the user with the minimum valid selections. Features in darker colors indicate selections to be first made in order to get closer to a complete configuration, as for example the Packages and the System features. The Packages features appears with a higher normalized 𝑄 -value, indicating that MCTS has first explored that feature (in contrast to the mandatory feature System ). That is because a complete configuration needs to include both features, satisfying the cross-tree constraints (i.e., the Glucose solver is implemented by the python-sat or the pyglucose package), so that the Packages feature must be selected. To satisfy the constraint, the python-sat or the pyglucose package must be selected. They appear with a higher normalized 𝑄 -value than the other alternative packages. Note that how other features like pycosat (0.08) or the solver MiniSAT (0.02) are not strictly necessary to complete the configuration, but has been marked as possible candidates. Remember that MCTS is based on simulations and probabilities and those feature selections have also been explored resulting in valid configurations. 5 FURTHER ANALYSES Analyses with MCTS can also be performed over other concepts beyond the configuration space of an SPL, such as feature models, extended feature models, variation points and variants, or products. This section shows how to model and analyze a problem where the concept of state can represent a feature model. Examples of these problems are the reverse engineering of feature models [ 4 , 43 ], the extraction of feature models from propositional formulas [ 19 ], or the evolution of feature models [ 44 ]. Here, we illustrate the reverse engineering of feature models problem [4, 43]. 5.1 Reverse engineering of feature models A well-known problem in SPLs is to synthesize a feature model from a set of configurations automatically. Given a set of feature combinations present in an SPL (i.e., a set of configurations), the goal is to extract a feature model that represents all the configurations. Formally, let be 𝐶𝑖 the set of configurations given as input. 𝐹𝑖 is the set of features present in 𝐶𝑖 . The problem is to build a feature model 𝑚 with features in 𝐹𝑖 so that 𝐶𝑖⊆𝐶𝑚 where 𝐶𝑚 is the set of valid configurations of the feature model 𝑚. Modeling the problem .We formulate the problem with the following definitions of (𝑆, 𝑠0, 𝑡, 𝐴,𝜃, 𝜇): The set of states 𝑺 is the set of all feature models that can be built with any combination of the input features 𝐹𝑖 following the Definition 3.1 of feature model. Thus, 𝑆={𝑚|𝑚=(𝐹,𝑟, R,Π)} where 𝐹∈ P(𝐹𝑖) and Π⊂ {𝑓⇒𝑔, 𝑓 ⇒ ¬𝑔|𝑓 , 𝑔 ∈𝐹𝑖}2 , 𝑟 is the root of the feature model, and the set of relations R is the same as in Definition 3.1 (i.e., optional, mandatory, alternative, and or). The initial state 𝒔0 is the empty feature model, with no features. The terminal condition 𝒕 determines that a feature model is terminal if it contains all features given as input (i.e., 𝐹=𝐹𝑖). The set of actions 𝑨 includes 9 actions ( 𝐴={𝑏1, . . . , 𝑏9} ) to be performed over a feature model (see formalization of the actions in Appendix A): add the root feature ( 𝑏1 ), add an optional feature ( 𝑏2 ), add a mandatory feature ( 𝑏3 ), add an or-group relation ( 𝑏4 ), add an alternative-group relation ( 𝑏5 ), add a feature to an existing or-group ( 𝑏6 ), add a feature to an existing alternative-group ( 𝑏7 ), add a “requires” constraint ( 𝑏8 ), and add a “excludes” constraint ( 𝑏9 ). Each action is also applicable under a certain condition of applicability (CA). An invariant condition of applicability that holds for all actions is that the features to be added are not already in the feature model (i.e., ∃𝑓∈𝐹𝑖, 𝑓 ∉𝐹). The state transition function 𝜽 defines the result of applying an action 𝑎∈𝐴to the given feature model 𝑚. 2 To simplify the problem we consider here only “requires” and “excludes” constraints. Extracted feature model •Total steps: 8 •Configurations: 191 •Input configurations: 110 •Captured configurations (Relaxed value): 60 •Deficit of configurations (deficit value): 50 •Irrelevant configurations (surplus value): 131 •Total time: 228.31 s Step 4: 231 decisions 1. (System, [Win,Linux], <1..2>) 1.00 2. (Packages, [Solvers,pyglucose], <1..2>) 0.56 3. (Packages, [pycosat,Solvers], <1..2>) 0.55 … pyPicosat Win Linux pycosat pyglucose Glucose PicoSAT MiniSAT AAFMFrameworkAAFMFramework SystemSystemPackagesPackages SolversSolvers pythonsatpythonsat pyPicosat Win Linux pycosat pyglucose Glucose PicoSAT MiniSAT AAFMFramework SystemPackages Solvers pythonsat Step 1: 13 decisions 1. root AAFMFramework 1.00 2. root Packages 0.61 3. root System 0.35 … AAFMFrameworkAAFMFramework Step 1: 13 decisions 1. root AAFMFramework 1.00 2. root Packages 0.61 3. root System 0.35 … AAFMFramework Step 2: 156 decisions 1. (AAFMFramework, [Packages,System], <1..2>) 1.00 2. (AAFMFramework, [Packages,pycosat], <1..2>) 0.65 3. (AAFMFramework, [System,Win], <1..2>) 0.63 … AAFMFrameworkAAFMFramework SystemSystemPackagesPackages AAFMFramework SystemPackages Step 2: 156 decisions 1. (AAFMFramework, [Packages,System], <1..2>) 1.00 2. (AAFMFramework, [Packages,pycosat], <1..2>) 0.65 3. (AAFMFramework, [System,Win], <1..2>) 0.63 … AAFMFramework SystemPackages Win Linuxpyglucose AAFMFrameworkAAFMFramework SystemSystemPackagesPackages SolversSolvers Win Linuxpyglucose AAFMFramework SystemPackages Solvers Step 3: 225 decisions 1. (Packages, [Solvers,pyglucose], <1..2>) 1.00 2. (System, [Win,Linux], <1..2>) 0.76 3. (Packages, [pyglucose,pycosat], <1..2>) 0.72 …pyglucose AAFMFrameworkAAFMFramework SystemSystemPackagesPackages SolversSolvers pyglucose AAFMFramework SystemPackages Solvers Figure 9: Step-wise decisions for reverse engineering of feature models. The reward function 𝝁: for a terminal feature model is a combination of two objective functions extracted from [43]: 𝑅(𝑠)=𝑅𝑒𝑙𝑎𝑥𝑒𝑑(𝑠) − 𝑀𝑖𝑛𝐷𝑖𝑓 𝑓 (𝑠) where 𝑅𝑒𝑙𝑎𝑥𝑒𝑑(𝑠) expresses the concern of capturing primarily the configurations provided as input. Its value is the number of configurations in 𝐶𝑖 that are valid according to the feature model 𝑚 represented by this state. We want to maximize the 𝑅𝑒𝑙𝑎𝑥𝑒𝑑(𝑠) value. 𝑀𝑖𝑛𝐷𝑖𝑓 𝑓 (𝑠) is a minimal difference function expressing the concern of obtaining a closer fit to the configurations provided 𝐶𝑖 while other configurations are not relevant. Its value is the sum of the number of configurations in 𝐶𝑖 that are not contained in the configurations 𝐶𝑚 of the feature model (also called deficit value), and the number of configurations in 𝐶𝑚 that are not contained in the required input configurations 𝐶𝑖 (also called surplus value). So 𝑀𝑖𝑛𝐷𝑖𝑓 𝑓 (𝑠)=𝑑𝑒 𝑓 𝑖𝑐𝑖𝑡 (𝑠) + 𝑠𝑢𝑟𝑝𝑙𝑢𝑠(𝑠), value to be minimized. Solving the problem and analyzing results .We use as input the set of 110 configurations of our running example (excerpt shown in Figure 3). We can use the same generic Algorithm 2 to solve this problem. Starting from the empty (void) feature model (i.e., initial state), MCTS will incorporate in each decision step a feature or a cross-tree constraint to the feature model until all features contained in the given configurations are present in the feature model. Figure 9 shows the first four decision steps made by MCTS and the final extracted feature model. The resulting feature model looks similar to the expected one (Figure 3) with some significant differences. It leads to a total of 191 configurations, 60 of which correspond with the 110 configurations provided as input, presenting a deficit of 50 configurations (almost half of the configurations). Such deficit may be corrected with a couple of manual changes over the resulting feature model. In each step, MCTS has run 1000 simulations, meaning that to make a decision, it has completed up to 1000 random feature models, enumerating their configurations with a SAT solver, and calculating the reward value for each model. The most interesting result obtained from MCTS is the information gathered in its tree search over the process. In this case, the tree search contains statistical information about how promising is to add a specific feature, relation, or constraints. As illustrated in Figure 9, for each step, we show the best three possible decisions (with normalized 𝑄 -values), highlighting the choice selected. For example, step 1 adds the root feature, where the three most promising options (from 13 candidates) are to use AAFMFramework , Packages , or System as root. In the following step, or-group relations are added with features Packages and System as children, but the tree search offers information about how promising other alternatives are out of a total of 156 possibilities. This can be seen as user-assistant to make better decisions, offering to the user alternatives so that she does not have to blindly rely on the result of a black box tool. MCTS can be integrated as part of a recommender system [ 51 , 56 , 61 ] to assist the user. Monte Carlo Conceptual Framework for SPLE Stopping Conditions • Iterations constraint • Time constraint • Memory constraint • ... Best Action Selection Criteria • Highest reward • Most visit state • Highest visit count and reward • Maximize lower confidence bound • ... Monte Carlo Algorithms • Monte Carlo • flat Monte Carlo • flat UCB • Monte Carlo Tree Search • UCT Algorithm • Greedy MTCS • Heuristic MCTS • MC-RAVE • ... Python framework for Automated Analysis [Galindo & Benavides, 2019] Variability Models • Feature Model • CNF Model • Configuration • ... Operations • Valid Configuration • Valid Partial Configuration • Core Features • Products • ... <<interface>> Action + execute(s: State): State + is_applicable(s: State): bool <<interface>> Action + execute(s: State): State + is_applicable(s: State): bool <<interface>> State + find_successors(): list[State] + find_random_successor(): State + is_terminal(): bool + reward(): float + hash(): int + eq(s: State): bool <<interface>> State + find_successors(): list[State] + find_random_successor(): State + is_terminal(): bool + reward(): float + hash(): int + eq(s: State): bool Transformations Solvers Figure 10: Monte Carlo conceptual framework architecture. 6 PROOF OF CONCEPTS This section illustrates the applicability of our proposal by providing an implementation of the MCTS conceptual framework 3 built on top of the Python framework for AAFMs proposed in [24]. Figure 10 overviews the core architecture which defines the two main interfaces ( State and Action ) to be implemented in order to model and solve a problem with Monte Carlo methods — i.e., the (𝑆, 𝑠0, 𝑡, 𝐴,𝜃, 𝜇) modeling concepts. The State interface specifies the necessary methods to explore the whole search space, so that from a given initial state 𝑠0 we can reach all states in 𝑆 . The State interface has to be implemented only once defining the state transition function 𝜃 ( find_successors() and find_random_successor() ), the is_terminal() condition 𝑡 , and the reward() function 𝜇 . The Action interface is defined for each applicable actions. Different Monte Carlo algorithms can be then applied. Each Monte Carlo algorithm can be configured with a stopping condition such as a time, memory, or iteration constraint, and with a selection criteria for the best action decision. For instance, to select the child with the highest reward, the most visited child, the child with both the highest visit count and the highest reward, or the child which maximizes a lower confidence bound [ 15 ]. At the time of writing this paper, the following Monte Carlo algorithms are available: •UCT Algorithm. An implementation of MCTS that builds a search tree and uses the upper confidence bound for trees (UCT) [ 38 ] selection strategy. This strategy favors actions with a higher 𝑄 - value but allows at the same time to explore those actions that have not yet been sufficiently explored. •Greedy MCTS. A best-first strategy that favors exploitation against exploration. •flat Monte Carlo. A basic Monte Carlo method with random action selection and no tree growth. To show the applicability of our Monte Carlo methods, we apply them for finding defective configurations in two real-world SPLs: the JHipster Web development stack [ 31 ], and the complete version of the Python framework for AAFMs [ 24 ]. On the one hand, we choose the jHipster SPL because its configuration space (26,256 configurations) has been fully evaluated in [ 31 ] (having 9,376 defective configurations, i.e., 35.70%) and can be used to verify the results obtained with our methods. On the other hand, the complete AAFMFramework product line presented in Section 3.1 has 53 features, 3https://github.com/diverso-lab/fm_montecarlo 0 1,000 2,000 3,000 4,000 5,000 0 500 1,000 1,500 2,000 Simulations Defective configurations UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (a) Solutions found. 0 1,000 2,000 3,000 4,000 5,000 0 1,000 2,000 3,000 4,000 5,000 Simulations Configurations evaluated UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (b) Evaluations. 0 1,000 2,000 3,000 4,000 5,000 0 0.2 0.4 0.6 0.8 1 Simulations % defective configurations UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (c) Efficiency. 0 1,000 2,000 3,000 4,000 5,000 0 10 20 30 Simulations Seconds UCT Algorithm Greedy MCTS flat Monte Carlo (d) Execution time. Figure 11: Finding defective configurations in jHipster. 0 1,000 2,000 3,000 4,000 5,000 0 1,000 2,000 3,000 4,000 5,000 Simulations Defective configurations UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (a) Solutions found. 0 1,000 2,000 3,000 4,000 5,000 0 1,000 2,000 3,000 4,000 5,000 Simulations Configurations evaluated UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (b) Evaluations. 0 1,000 2,000 3,000 4,000 5,000 0 0.2 0.4 0.6 0.8 1 Simulations % defective configurations UCT Algorithm Greedy MCTS flat Monte Carlo Random Sampling (c) Efficiency. 0 1,000 2,000 3,000 4,000 5,000 0 20 40 60 80 100 Simulations Seconds UCT Algorithm Greedy MCTS flat Monte Carlo (d) Execution time. Figure 12: Finding defective configurations in the complete configuration space of the AAFM Python framework. 26 relations, and 10 cross-tree constraints, leading to a total of 3 . 1264 · 10 9 configurations. It serves as a large-scale configuration space where we have already identified the specific features that cause the defective configurations using the MCTS method as we did in Section 4.1. The experiments were performed on a desktop computer with Intel Core i9-9900K CPU @ 3.60GHz x 8, 32 GB of memory, Linux Mint 20.1 Cinnamon, and Python 3.9.1. The results are summarized in Figure 11 and Figure 12 for the jHipster SPL and the AAFMs Python framework, respectively. We compare the three implemented Monte Carlo algorithms for different numbers of simulations wrt. a uniform random sampling strategy [ 32 ]. We present the number of configurations found with defects (a), the number of configurations evaluated (b), the efficiency as the percentage of defective configurations found wrt. the configurations evaluated (c), and the execution time (d). A first observation is a higher fluctuation in the MCTS (especially in the UCT Algorithm) because of the balance between exploitation and exploration [ 29 , 38 ]. This helps MCTS to get out of local optima when those solutions have been sufficiently explored, but demonstrates the evidence of Lopez-Herrejón [ 42 ] about techniques that rely on randomness, which are very sensitive to the various inputs and parameters, meaning that slightly changing a value (the number of simulations in this case) can totally change how you would infer the results. The number of solutions found (a) and evaluated (b) by MCTS will depend on the distribution of the configuration space [ 33 ]. In jHipster, defective configurations are localized in regions, making MCTS focuses on that area (same configurations may be found more than once, but are evaluated once) until the region is sufficiently explored (requiring MCTS more simulations). On the contrary, in the AAFM Python framework, defective configurations are scattered through the configuration space, and MCTS will evaluate and find more with the same number of simulations. A second observation is the efficiency of the Monte Carlo methods (c), being superior on average the UCT Algorithm (68% in jHipster and 98% in the AAFM Python framework) than the random sampling (36% and 77%, respectively), when comparing the amount of defective configurations found wrt. the configurations evaluated. This result is not surprising due to MCTS is a selective sampling approach, but it shows that MCTS can also be used as a searchbased optimization technique in SPL as a complement of existing approaches (e.g., genetic algorithms [ 42 ]). Finally, regarding the performance (d), Monte Carlo algorithms accomplish better results the longer they keep running. They are appropriate for problems that do not require achieving immediate results but require taking optimum decisions in the medium and long term. 7 RELATED WORK Over the last decade, MCTS has been adopted as part of the solution to many problems in a variety of domains beyond AI games [ 65 ]. For instance, MCTS has achieved great success with complex realworld problems, such as combinatorial optimization to evaluate system vulnerabilities [ 68 ], constraint satisfaction problems (CSP) [ 6 ], boolean satisfiability [ 60 ], model checking [ 59 ], scheduling problems [ 50 ], and feature selection problems in the field of machine learning [ 17 ], among others [ 12 ]. However, MCTS has not been already applied in the context of the AAFMs [ 25 ]. To the best of our knowledge, Monte Carlo methods have been mainly applied in SPL from an economic point of view [ 13 , 27 , 52 ]. For instance, to analyze the return on investment expectations of an SPL [ 52 ] and understanding the effort required for building reusable assets [ 13 ], to compare costs and benefits of different test strategies [ 27 ], or to estimate the payoff of an SPL [ 34 ]. Also, Monte Carlo simulations have been used for validation when there is a lack of available data [ 1 ], as for example, to check the stability of solutions in SPL optimization [ 37 , 45 ]. Regarding MCTS, our work is the first study that proposes applying it in SPLs. Several work have incorporated randomness into AAFMs. Czarnecki et al. [ 18 ] introduced the concept of probabilistic feature models (PFM) to automate the choice propagation of features according to the constraints, and apply an entropy measure to guide the configuration process. Martinez et al [ 46 ] also estimate the feature probabilities to provide feedback to the user. Both works [ 18 , 46 ] rely on historical data to extract probabilities. Heradio et al. [ 33 ] propose statistical analysis to reason on variability models. They can extract probability distributions from the whole configuration