A goal of many Artificial Intelligence (AI) courses is to teach properties of synthesis and analysis tasks such as configuration and diagnosis. Configuration is a special case of design activity where the major goal is to identify configurations that satisfy the user requirements and are consistent with the configuration knowledge base. If the requirements are inconsistent with the knowledge base, changes (repairs) for the current requirements have to be identified. In this paper we present games that can, for example, be used within the scope of Artificial Intelligence courses to easier understand configuration and diagnosis concepts. We first present the CONFIGURATIONGAME and then continue with two further games (COLORSHOOTER and EATIT) that support the learning of modelbased diagnosis concepts.
Theoretical problems of combinatorial games have long been studied
[
Bayer et al. [
In the line of previous work, we present the CONFIGURATION
GAME which is based on conventional CSP representations [
The remainder of this paper is organized as follows. In Section 2 we introduce definitions of a configuration and a corresponding diagnosis task. The subsequently presented games are discussed on the basis of these definitions. In Section 3 we introduce the CONFIGURATIONGAME Android app and present the results of a corresponding user study. In Section 4 we introduce the COLORSHOOTER diagnosis game and also present results of a user study. In Section 5 we introduce a new diagnosis game embedded in the domain of healthy eating. In Section 6 we discuss issues for future work. With Section 7 we conclude the paper. 2
Knowledge-based Configuration is one of the most successful
technologies of Artificial Intelligence [
Definition 1 (Configuration Task and Solution). A configuration task can be defined as a constraint satisfaction problem (V; D; C) where V = fv1; v2; :::; vng is a set of variables, D = [dom(vi) represents the corresponding domain definitions, and C = fc1; c2; :::; cmg is a set of constraints. Additionally, user requirements are represented by a set of constraints CREQ = fr1; r2; :::; rkg. A solution for a configuration task is an assignment S = finst(v1); inst(v2); :::; inst(vn)g where inst(vi) 2 dom(vi) which is consistent with the constraints in C [ CREQ.
Example (Configuration Task and Solution). An example of a very simple configuration task (and a corresponding solution S) represented as a constraint satisfaction problem is the following. Such configuration tasks have to be solved by players of the CONFIGURATION GAME (see Section 3). This example represents a simple Map Coloring Problem were variables (V = fv1; v2; v3g) represent, for example, countries on a map and the constraints (C = fc1; c2g) restrict solutions to colorings were neighborhood countries must be represented by different colors. In our example we assume that the neighborhood countries are fv1; v2g and fv2; v3g and the user requirements are CREQ = fr1 : v1 = 1g. A player of the CONFIGURATIONGAME has successfully solved a configuration task (found a solution S) if consistent(S [ CREQ [ C).
V = fv1; v2; v3g dom(v1) = dom(v2) = dom(v3) = f1; 2g C = fc1 : v1 6= v2; c2 : v2 6= v3g CREQ = fr1 : v1 = 1g S = fv1 = 1; v2 = 2; v3 = 1g
In configuration scenarios it is often the case that no solution can
be found for a given set of user requirements (CREQ [ C is
inconsistent). In this context, users are in the need of additional support in
order to be able to identify reasonable changes to the current set of
requirements more efficiently. Model-based diagnosis [
Definition 2 (Diagnosis Task and Diagnosis). A diagnosis task can be defined by a tuple (C; CREQ) where C represents a set of constraints and CREQ represents a set of customer requirements. If the requirements in CREQ are inconsistent with the constraints in C, a diagnosis ( CREQ) represents a set of requirements such that CREQ [ C is consistent (in this context we assume that the constraints in C are consistent). is minimal if :9 0 : 0 .
Example (Diagnosis Task and Diagnosis). An example of a simple diagnosis task and a corresponding diagnosis is the following. Similar diagnosis tasks have to be solved by players of the the COLORSHOOTER and the EATIT game (see Sections 4 and 5). The following example represents a diagnosis task were the set of customer requirements (CREQ) is inconsistent with the constraints in C. A player of COLORSHOOTER and EATIT has successfully solved a diagnosis task (found a diagnosis ) if CREQ [ C is consistent.
V = fv1; v2; v3g dom(v1) = dom(v2) = dom(v3) = f0; 1g C = fc1 : :(v1 = 1) _ :(v2 = 1), c2 : :(v1 = 1) _ :(v3 = 1), c3 : :(v2 = 1) _ :(v3 = 1)g CREQ = fr1 : v1 = 1; r2 : v2 = 1; r3 : v3 = 1g
= fr1; r2g
A wide-spread approach to determine diagnoses for a given
diagnosis task is to identify minimal conflict sets [
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 9CS0 with CS0 CS.
On the basis of a set of identified minimal conflict sets [
User Interface. With this game (see Figure 2), one should be able
to gain first insights into the basic concepts of knowledge-based
configuration. Constraints of the underlying CSP are depicted in the
upper left corner. Constraints represent incompatible combinations of
values, i.e., combinations that must not be positioned on adjacent
vertices of the grid depicted in Figure 2. This way, tasks such as the
map coloring problem [
Each individual task to be solved by a player can be interpreted as a configuration task (V,D,C) (see Definition 1). In the setting shown in Figure 2, V = fv1; v2; :::; v14g represents a set of 14 interconnected hexagons (in the center of the user interface). Furthermore, it is assumed that each variable has the same domain (in Figure 3, dom(vi)=f1,2,3,4g) and possible variable instantiations are represented by the values (hexagons) in the lower right corner. Constraints C = fc1; c2; :::; c16g represent incompatible colorings of adjacent vertices, for example, c1 : :(v1 = 1 ^ v2 = 1) ^ :(v1 = 2 ^ v2 = 2) ^ :(v1 = 3 ^ v2 = 3) ^ :(v1 = 4 ^ v2 = 4) ^ :(v1 = 4 ^ v2 = 3)^:(v1 = 3^v2 = 4)^:(v1 = 1^v2 = 2)^:(v1 = 2^v2 = 1). Incompatibilities are defined by red lines between individual values (left upper corner of Figure 2). A self-referring red line expresses an incompatibility on the same value, i.e., two adjacent vertices must not have to the same value. A proprietary constraint solver is used to generate individual tasks with increasing complexity in terms of the grid size (vertices and arcs) and the number of possible values and also to check proposed solutions for consistency.
The task of a player is to move values (hexagons) from the
bottom to corresponding (empty) hexagons depicted in the middle of
Figure 2. A player has found a solution if the grid instantiation S is
consistent with the constraints in C.2 A screenshot of an
intermediate state of the CONFIGURATIONGAME is shown in Figure 4. The
CONFIGURATIONGAME allows to define constraints that go beyond
typical patterns of map coloring problems [
Empirical Study. N=28 subjects of a usability study evaluated the
CONFIGURATIONGAME. A first prototype of the game was made
available to the subjects in the Google Play Store. The questionnaire
was based on the system usability scale (SUS) [
User Interface. The COLORSHOOTER game (see Figure 5)
focuses on providing first insights into the concepts of model-based
diagnosis [
Empirical Study. After two lecture units on model-based
diagnosis [
Participants of the first setting used the COLORSHOOTER game directly before solving two diagnosis tasks. Participants of the second setting interacted with COLORSHOOTER one day before completing the two diagnosis tasks. Finally, participants of the third setting never interacted with COLORSHOOTER but only solved the two diagnosis 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 diagnoses. 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 performance difference between users who applied COLORSHOOTER and those who did not.
setting played directly before played one day before did not play before
all minimal diagnoses found (C1)
EATIT (see Figure 6) is an application currently under development,
i.e., no related user studies have been conducted up to now. The major
ideas of the game are the following: (1) similar to COLORSHOOTER,
students should be able to more easily understand the concepts of
model-based diagnosis. (2) there is a serious game [
In the CONFIGURATIONGAME our major goal for future work is to extend the expressiveness of constraints that can be defined for configuration tasks. A higher degree of expressiveness will allow the inclusion of further tasks such as scheduling and resource balancing. Furthermore, EATIT will be extended with functionalities that help to include user preferences and menu quality. In the current version of EATIT such aspects are not taken into account. In our future research we will also analyze in more detail which specific game types better help to increase understandability. Furthermore, we will analyze to which extent the games can be exploited to develop better configurator user interfaces and interaction schemes. 7
The overall goal of the (serious) games presented in this paper is to help to better understand the concepts of configuration and modelbased diagnosis. Results of empirical studies are promising in the sense that the apps are applicable and can have a positive impact on the learning performance. Two of the presented games are already available: COLORSHOOTER in the Apple App Store and the CONFIGURATIONGAME in the Google Play Store.