=Paper=
{{Paper
|id=Vol-1453/17_FelfernigJeranRuprechterZillerReitererStettinger_LearningGamesForConfiguration_Confws-15_p111
|storemode=property
|title=Learning games for configuration and diagnosis tasks
|pdfUrl=https://ceur-ws.org/Vol-1453/17_FelfernigJeranRuprechterZillerReitererStettinger_LearningGamesForConfiguration_Confws-15_p111.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/FelfernigJRZRS15
}}
==Learning games for configuration and diagnosis tasks==
https://ceur-ws.org/Vol-1453/17_FelfernigJeranRuprechterZillerReitererStettinger_LearningGamesForConfiguration_Confws-15_p111.pdf
Short paper
Learning Games for Configuration and Diagnosis Tasks
Alexander Felfernig1 and Michael Jeran1 and Thorsten Ruprechter1 and
Alexander Ziller1 and Stefan Reiterer1 and Martin Stettinger 1
Abstract. A goal of many Artificial Intelligence (AI) courses is was implemented with the goal to support the learning of basic con-
to teach properties of synthesis and analysis tasks such as configu- cepts of knowledge-based configuration [6, 15]. Furthermore, we in-
ration and diagnosis. Configuration is a special case of design ac- troduce two games which focus on analysis in terms of model-based
tivity where the major goal is to identify configurations that sat- diagnosis [13]. C OLOR S HOOTER and E AT I T are based on the ideas
isfy the user requirements and are consistent with the configuration of model-based diagnosis and were developed to support students in
knowledge base. If the requirements are inconsistent with the knowl- the understanding of the principles of hitting set determination [13].
edge base, changes (repairs) for the current requirements have to be To the best of our knowledge these are new types of games based
identified. In this paper we present games that can, for example, be on conflict detection [10] and model-based diagnosis [7, 13]. All the
used within the scope of Artificial Intelligence courses to easier un- presented games are serious games [11] with the purpose of teaching
derstand configuration and diagnosis concepts. We first present the AI knowledge and also domain knowledge (E AT I T).
C ONFIGURATION G AME and then continue with two further games The remainder of this paper is organized as follows. In Section 2
(C OLOR S HOOTER and E AT I T) that support the learning of model- we introduce definitions of a configuration and a corresponding di-
based diagnosis concepts. agnosis task. The subsequently presented games are discussed on the
basis of these definitions. In Section 3 we introduce the C ONFIGU -
RATION G AME Android app and present the results of a correspond-
1 Introduction ing user study. In Section 4 we introduce the C OLOR S HOOTER diag-
Theoretical problems of combinatorial games have long been studied nosis game and also present results of a user study. In Section 5 we
[8]. For example, Bodlaender [4] analyzes the properties of coloring introduce a new diagnosis game embedded in the domain of healthy
games were players have to color vertices of a graphs in such a way eating. In Section 6 we discuss issues for future work. With Section
that never two adjacent vertices have the same color. The player who 7 we conclude the paper.
was last able to color a vertex in a consistent fashion wins the game.
Börner et al. [5] analyze complexity properties of different variants
of two-person constraint satisfaction [12] games were, for example,
2 Configuration and Diagnosis Task
two players alternately make moves and the first player tries to find Knowledge-based Configuration is one of the most successful tech-
a solution whereas the second player tries to make the constraint sat- nologies of Artificial Intelligence [6, 15]. Configurators determine
isfaction problem (CSP) inconsistent. Different complexity classes configurations for a given set of user requirements, for example, on
of such games are analyzed which primarily depend on the allowed the basis of constraint technologies. In terms of a CSP, a configura-
quantifiers – quantified constraint satisfaction problems (QCSPs) are tion task and a corresponding solution can be defined as follows.
constraint satisfaction problems were some of the variables are uni- Definition 1 (Configuration Task and Solution). A configura-
versally quantified [9]. tion task can be defined as a constraint satisfaction problem
Bayer et al. [2] present an application that models Minesweeper (V, D, C) where V = {v1 , v2 , ..., vn } is a set of variables, D =
puzzles as a CSP [12]; the game supports players in finding a solution ∪dom(vi ) represents the corresponding domain definitions, and
and is primarily used as means to support students in understanding C = {c1 , c2 , ..., cm } is a set of constraints. Additionally, user
the mechanisms of constraint-based reasoning. In a similar fashion, requirements are represented by a set of constraints CREQ =
Simonis [14] shows how to solve Sudoku puzzles on the basis of {r1 , r2 , ..., rk }. A solution for a configuration task is an assignment
constraint technologies. In addition to problem solving approaches, S = {inst(v1 ), inst(v2 ), ..., inst(vn )} where inst(vi ) ∈ dom(vi )
the authors also focus on mechanisms for puzzle generation and pro- which is consistent with the constraints in C ∪ CREQ.
pose measures for evaluating puzzle complexity. Finally, we want to Example (Configuration Task and Solution). An example of a very
mention the application of constraint technologies in the context of simple configuration task (and a corresponding solution S) repre-
the generation of crossword puzzles. In crossword puzzle generation sented as a constraint satisfaction problem is the following. Such
[3], a crossword puzzle grid has to be filled with words from a dictio- configuration tasks have to be solved by players of the C ONFIGU -
nary in such a way that none of the words in the dictionary is included RATION G AME (see Section 3). This example represents a simple
more than once in the grid. Map Coloring Problem were variables (V = {v1 , v2 , v3 }) represent,
In the line of previous work, we present the C ONFIGURATION for example, countries on a map and the constraints (C = {c1 , c2 })
G AME which is based on conventional CSP representations [12] and restrict solutions to colorings were neighborhood countries must be
1 Graz University of Technology, Institute for Software Technol-
represented by different colors. In our example we assume that the
ogy, Austria, email: {felfernig, jeran, reiterer, stettinger}@ist.tugraz.at neighborhood countries are {v1 , v2 } and {v2 , v3 } and the user re-
{thorsten.ruprechter, alexander.ziller}@student.tugraz.at quirements are CREQ = {r1 : v1 = 1}. A player of the C ONFIG -
111 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
URATION G AME has successfully solved a configuration task (found
a solution S) if consistent(S ∪ CREQ ∪ C).
• V = {v1 , v2 , v3 }
• dom(v1 ) = dom(v2 ) = dom(v3 ) = {1, 2}
• C = {c1 : v1 6= v2 , c2 : v2 6= v3 }
• CREQ = {r1 : v1 = 1}
• S = {v1 = 1, v2 = 2, v3 = 1}
Figure 1. Example hitting set directed acyclic graph derived from the
In configuration scenarios it is often the case that no solution can conflict sets CS1 , CS2 , and CS3 .
be found for a given set of user requirements (CREQ ∪ C is incon-
sistent). In this context, users are in the need of additional support in figuration. Constraints of the underlying CSP are depicted in the up-
order to be able to identify reasonable changes to the current set of per left corner. Constraints represent incompatible combinations of
requirements more efficiently. Model-based diagnosis [13] can help values, i.e., combinations that must not be positioned on adjacent
to automatically identify minimal sets of requirements that have to vertices of the grid depicted in Figure 2. This way, tasks such as the
be deleted (or adapted) such that a solution can be identified. A diag- map coloring problem [4] can be defined as a simple configuration
nosis task related to the identification of faulty requirements can be problem (similar examples can also be found in [6]).
defined as follows (see Definition 2). Each individual task to be solved by a player can be interpreted as
Definition 2 (Diagnosis Task and Diagnosis). A diagnosis task can a configuration task (V,D,C) (see Definition 1). In the setting shown
be defined by a tuple (C, CREQ) where C represents a set of con- in Figure 2, V = {v1 , v2 , ..., v14 } represents a set of 14 intercon-
straints and CREQ represents a set of customer requirements. If the nected hexagons (in the center of the user interface). Furthermore,
requirements in CREQ are inconsistent with the constraints in C, it is assumed that each variable has the same domain (in Figure 3,
a diagnosis ∆ (∆ ⊆ CREQ) represents a set of requirements such dom(vi )={1,2,3,4}) and possible variable instantiations are repre-
that CREQ−∆∪C is consistent (in this context we assume that the sented by the values (hexagons) in the lower right corner. Constraints
constraints in C are consistent). ∆ is minimal if ¬∃∆0 : ∆0 ⊂ ∆. C = {c1 , c2 , ..., c16 } represent incompatible colorings of adjacent
Example (Diagnosis Task and Diagnosis). An example of a sim- vertices, for example, c1 : ¬(v1 = 1 ∧ v2 = 1) ∧ ¬(v1 = 2 ∧ v2 =
ple diagnosis task and a corresponding diagnosis ∆ is the following. 2) ∧ ¬(v1 = 3 ∧ v2 = 3) ∧ ¬(v1 = 4 ∧ v2 = 4) ∧ ¬(v1 = 4 ∧ v2 =
Similar diagnosis tasks have to be solved by players of the the C OL - 3)∧¬(v1 = 3∧v2 = 4)∧¬(v1 = 1∧v2 = 2)∧¬(v1 = 2∧v2 = 1).
OR S HOOTER and the E AT I T game (see Sections 4 and 5). The fol-
Incompatibilities are defined by red lines between individual values
lowing example represents a diagnosis task were the set of customer (left upper corner of Figure 2). A self-referring red line expresses an
requirements (CREQ) is inconsistent with the constraints in C. A incompatibility on the same value, i.e., two adjacent vertices must
player of C OLOR S HOOTER and E AT I T has successfully solved a di- not have to the same value. A proprietary constraint solver is used to
agnosis task (found a diagnosis ∆) if CREQ − ∆ ∪ C is consistent. generate individual tasks with increasing complexity in terms of the
grid size (vertices and arcs) and the number of possible values and
• V = {v1 , v2 , v3 }
also to check proposed solutions for consistency.
• dom(v1 ) = dom(v2 ) = dom(v3 ) = {0, 1}
• C = {c1 : ¬(v1 = 1) ∨ ¬(v2 = 1), c2 : ¬(v1 = 1) ∨ ¬(v3 =
1), c3 : ¬(v2 = 1) ∨ ¬(v3 = 1)}
• CREQ = {r1 : v1 = 1, r2 : v2 = 1, r3 : v3 = 1}
• ∆ = {r1 , r2 }
A wide-spread approach to determine diagnoses for a given diag-
nosis task is to identify minimal conflict sets [10] in CREQ and to
resolve these conflicts on the basis of a hitting set directed acyclic
graph (HSDAG) approach [13]. A (minimal) conflict set can be de-
fined as follows (see Definition 3).
Definition 3 (Conflict Set). A set CS ⊆ CREQ is a conflict set
if CS ∪ C is inconsistent (C is assumed to be consistent). CS is
minimal if 6 ∃CS 0 with CS 0 ⊂ CS.
On the basis of a set of identified minimal conflict sets [10] we
are able to automatically determine the corresponding minimal diag-
noses (see Figure 1). In our example, the minimal conflict sets are
CS1 : {r1 : v1 = 1, r2 : v2 = 1}, CS2 : {r2 : v2 = 1, r3 : v3 =
1}, and CS3 : {r1 : v1 = 1, r3 : v3 = 1}. The corresponding min-
imal diagnoses are ∆1 : {r1 , r2 }, ∆2 : {r1 , r3 }, and ∆3 : {r2 , r3 }.
Exactly this example pattern is implemented in the diagnosis games
presented in Section 4 and Section 5.
Figure 2. C ONFIGURATION G AME user interface.
3 C ONFIGURATION G AME
The task of a player is to move values (hexagons) from the bot-
User Interface. With this game (see Figure 2), one should be able tom to corresponding (empty) hexagons depicted in the middle of
to gain first insights into the basic concepts of knowledge-based con- Figure 2. A player has found a solution if the grid instantiation S is
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 112
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Figure 3. Results of a usability analysis of the C ONFIGURATION G AME on the basis of the system usability scale (SUS) [1].
consistent with the constraints in C.2 A screenshot of an intermedi- system was considered as easy to understand and well integrated.
ate state of the C ONFIGURATION G AME is shown in Figure 4. The Results of the study are summarized in Figure 3.
C ONFIGURATION G AME allows to define constraints that go beyond
typical patterns of map coloring problems [4] since different types of 4 C OLOR S HOOTER
incompatible adjacent vertices can be defined (in contrast to the map
coloring problem where only incompatibilities regarding the same User Interface. The C OLOR S HOOTER game (see Figure 5) fo-
value (color) are defined). Instances of the configuration game are cuses on providing first insights into the concepts of model-based
generated automatically. diagnosis [13]. The game is available online in the Apple App Store
(as an iOS application). The columns of the game represent mini-
mal conflict sets (see Definition 3) – related diagnoses (see Defini-
tion 2) are represented by minimal color3 sets such that at least one
color from each row is included. The game consists of twenty dif-
ferent levels and inside each level of 30 different individual C OLOR -
S HOOTER tasks. Individual tasks are pre-generated in an automated
fashion where the #colums, #rows, # of different colors, and diagno-
sis cardinality are major impact factors for determining the complex-
ity of one C OLOR S HOOTER instance. Correct solutions (diagnoses)
are pre-generated on the basis of a HSDAG [13].
Figure 4. C ONFIGURATION G AME user interface (after the completion of
some configuration steps).
Empirical Study. N=28 subjects of a usability study evaluated the Figure 5. Example of a C OLOR S HOOTER diagnosis task.
C ONFIGURATION G AME. A first prototype of the game was made
available to the subjects in the Google Play Store. The questionnaire Empirical Study. After two lecture units on model-based diag-
was based on the system usability scale (SUS) [1] and thus focused nosis [13], we investigated in which way C OLOR S HOOTER type
on analyzing usability aspects of the system under investigation. The games can actively support a better understanding of the principles
2 In the C ONFIGURATION G AME we assume that CREQ = {}. 3 For readability purposes we annotated the colored circles with numbers.
113 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
of model-based diagnosis. N=60 subjects (students) participated in a
user study where each participant was assigned to one of three dif-
ferent settings (see Table 1).
Participants of the first setting used the C OLOR S HOOTER game di-
rectly before solving two diagnosis tasks. Participants of the second
setting interacted with C OLOR S HOOTER one day before complet-
ing the two diagnosis tasks. Finally, participants of the third setting
never interacted with C OLOR S HOOTER but only solved the two di-
agnosis tasks. The two diagnosis tasks where designed in such a way
that a participant had to figure out all minimal diagnoses for each of
two predefined inconsistent constraint sets (C1 and C2 ). C1 included
4 constraints, 4 variables of domain size [1..3], and 3 related diag-
noses. C2 included 5 constraints, 4 variables of domain size [1..3]
and 6 related diagnoses. Preliminary results in terms of the number
of successfully completed diagnosis tasks are depicted in Table 1. In
the case of the more complex constraint set C2 we can observe a per-
formance difference between users who applied C OLORSHOOTER
and those who did not. Figure 6. Screenshot of E AT I T. Each shelf represents food that contains a
specific vitamin (e.g., A, B1, ...). A solution (diagnosis) is found if the
all minimal all minimal
selected food on the plate covers all vitamins.
setting diagnoses found diagnoses found
(C1 ) (C2 )
played directly before 33% 20% sense that the apps are applicable and can have a positive impact on
played one day before 20% 20%
the learning performance. Two of the presented games are already
did not play before 23% 10%
available: C OLOR S HOOTER in the Apple App Store and the C ON -
FIGURATION G AME in the Google Play Store.
Table 1. User study with three different settings: subjects played directly
before solving two diagnosis tasks, subjects played one day before, and
subjects did not use C OLOR S HOOTER. REFERENCES
[1] A. Bangor, P. Kortum, and J. Miller, ‘An Empirical Evaluation of
5 E AT I T the System Usability Scale (SUS)’, International Journal of Human-
Computer Interaction, 24(6), 574–594, (2008).
E AT I T (see Figure 6) is an application currently under development, [2] K. Bayer, J. Snyder, and B. Choueiry, ‘An Interactive Constraint-Based
i.e., no related user studies have been conducted up to now. The major Approach to Minesweeper’, in AAAI 2006, pp. 1933–1934, (2006).
ideas of the game are the following: (1) similar to C OLOR S HOOTER, [3] A. Beacham, X. Chen, J. Sillito, and P. vanBeek, ‘Constraint Program-
students should be able to more easily understand the concepts of ming Lessons Learned from Crossword Puzzles’, in AI 2001, LNAI, pp.
78–87. Springer, (2001).
model-based diagnosis. (2) there is a serious game [11] line of learn- [4] H. Bodlaender, ‘On the Complexity of Some Coloring Games’, LNCS,
ing which is directly related to the underlying application domain: 484, 30–40, (1991).
users of the system should learn about, for example, which vitamins [5] F. Börner, A. Bulatow, H. Chen, P. Jeavons, and A. Krokhin, ‘The Com-
are contained in which food. In E AT I T, ”conflicts” are represented by plexity of Constraint Satisfaction Games and QCSP’, Information and
Computation, 207(9), 923–944, (2009).
food items assigned to the same shelf (each food item contains the [6] A. Felfernig, L. Hotz, C. Bagley, and J. Tiihonen, Knowledge-based
vitamin represented by the shelf) and diagnoses represent minimal Configuration: From Research to Business Cases, Elsevier/Morgan
sets of food items that are needed to cover all vitamins. Kaufmann Publishers, 1st edn., 2014.
[7] A. Felfernig, M. Schubert, and C. Zehentner, ‘An efficient diagnosis al-
gorithm for inconsistent constraint sets’, Artificial Intelligence for En-
6 Future Work gineering Design, Analysis and Manufacturing (AI EDAM), 26(1), 53–
62, (2012).
In the C ONFIGURATION G AME our major goal for future work is to [8] A. Fraenkel, ‘Complexity, Appeal and Challenges of Combinatorial
extend the expressiveness of constraints that can be defined for con- Games’, Theoretical Computer Science, 313(3), 393–415, (2004).
figuration tasks. A higher degree of expressiveness will allow the [9] I. Gent, P. Nightingale, and K. Stergiou, ‘A Solver for Quantified Con-
inclusion of further tasks such as scheduling and resource balancing. straint Satisfaction Problems’, in IJCAI 2005, pp. 138–142, (2005).
[10] Ulrich Junker, ‘QUICKXPLAIN: preferred explanations and relax-
Furthermore, E AT I T will be extended with functionalities that help ations for over-constrained problems’, in 19th Intl. Conference on Artif-
to include user preferences and menu quality. In the current version ical Intelligence (AAAI’04), eds., Deborah L. McGuinness and George
of E AT I T such aspects are not taken into account. In our future re- Ferguson, pp. 167–172. AAAI Press, (2004).
search we will also analyze in more detail which specific game types [11] H. Kelly, K. Howell, E. Glinert, L. Holding, C. Swain, A. Burrow-
better help to increase understandability. Furthermore, we will an- bridge, and M. Roper, ‘How to build Serious Games’, Communications
of the ACM, 50(7), 44–49, (2007).
alyze to which extent the games can be exploited to develop better [12] A. Mackworth, ‘Consistency in Networks of Relations’, Artificial Intel-
configurator user interfaces and interaction schemes. ligence, 8(1), 99–118, (1977).
[13] R. Reiter, ‘A theory of diagnosis from first principles’, Artificial Intel-
ligence, 32(1), 57–95, (1987).
7 Conclusions [14] H. Simonis, ‘ Sudoku as a constraint problem’, in CP Workshop on
Modeling and Reformulating Constraint Satisfaction Problems, pp. 13–
The overall goal of the (serious) games presented in this paper is to
27, (2005).
help to better understand the concepts of configuration and model- [15] M. Stumptner, ‘An Overview of Knowledge-based Configuration’, AI
based diagnosis. Results of empirical studies are promising in the Communications, 10(2), 111–126, (1997).
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 114
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria