key: cord-0046950-rol2kkwd
authors: Park, Kyungjin; Mott, Bradford; Min, Wookhee; Wiebe, Eric; Boyer, Kristy Elizabeth; Lester, James
title: Generating Game Levels to Develop Computer Science Competencies in Game-Based Learning Environments
date: 2020-06-10
journal: Artificial Intelligence in Education
DOI: 10.1007/978-3-030-52240-7_44
sha: 52240b6c2c21b4f9fa62963bb20241b2223f81c2
doc_id: 46950
cord_uid: rol2kkwd

Game-based learning environments hold significant potential for supporting K-12 computer science (CS) education by providing CS learning experiences embedded within engaging virtual worlds. However, many game-based learning environments do not adaptively support individual students based on their specific knowledge and skills. Often, this is because creating game levels is highly labor-intensive, which limits the number of levels created to support student learning. Procedural content generation (PCG) is a promising direction for addressing this challenge by dynamically creating game levels that address specific student needs without requiring extensive development effort. In this paper, we investigate a PCG framework driven by answer set programming (ASP), a variant of logic programming that utilizes well-formed logical rules to express constraints for valid game levels. We demonstrate how variations in CS learning objectives and game-playing skills can be incorporated into ASP-based rules to generate learner-adaptive levels in a middle-grades CS game-based learning environment. Evaluations of the generated levels suggest that the ASP-based level generator not only reliably generates desired CS educational game levels but also synthesizes a large set of diverse game levels. The findings suggest that the ASP-based PCG approach has considerable promise for creating highly engaging and adaptive game-based learning experiences for K-12 CS education.

Recent years have seen growing interest in game-based learning environments [1] [2] [3] [4] , which engage students in situated problem-solving challenges within rich virtual worlds [5] . In parallel, there is a growing recognition that computer science (CS) is a fundamental skill required by many career paths, which has intensified the need to develop K-12 students' CS competencies [6] [7] [8] [9] and highlighted the potential of gamebased learning environments to support CS education [10] [11] [12] . However, the conventional approach of utilizing a linear sequence of game levels is fundamentally non-adaptive and may not effectively address the needs of different students based on their level of concept and skill mastery. This lack of adaptivity may result in undesirable learning experiences (e.g., students adopting a trial-and-error approach without mastering concepts because a game-based learning environment is too difficult). Likewise, students have different levels of game-playing skills, which can affect their learning experiences [13] . Thus, adaptively generating challenges tailored to individual students' knowledge and game-playing skill is crucial for supporting mastery learning and engagement in game-based learning by addressing limitations with "one-size-fitsall" approaches.

Procedural content generation (PCG) automatically generates game content using a range of algorithms that require limited human intervention [14] . In contrast to problem generation in intelligent tutoring systems, in which problems are generated using templates [15, 16] , PCG explores the generation of game objects and their layout that collectively constitute a game level. However, level generation in game-based learning environments is challenging for PCG because game levels must exercise the desired learning objectives for individual students as well as target an appropriate level of difficulty for students based on their game-playing skill.

This paper presents a novel approach to generating game levels for game-based learning environments. Our work is the first to introduce a PCG framework that dynamically generates game levels to develop individual students' CS competencies using answer set programming (ASP) [17] . We evaluate our framework with respect to the diversity of generated game levels and the presence of the CS learning objectives as well as the game-playing skill specified as input for each generated level in the context of a game-based learning environment for middle school CS education.

ENGAGE is a game-based learning environment for middle school CS education, the curriculum of which is guided by the K-12 CS Framework [18] . In ENGAGE, students play the role of a protagonist who is sent to an undersea research station, where a rogue villain has severed communication with the facility. In this work, we focus on generating levels for a specific type of challenge shown in Fig. 1a which requires students in the game to connect their wrist computer with a quadcopter device using a pairing point, and program the quadcopter to navigate across a water-filled area while avoiding obstacles. Figure 1b shows a top-down view of the room, which serves as the basis of all the generated levels in this work.

Generated levels incorporate four key learning concepts, Loop, Conditional, Sequence (i.e., requiring minimum of two controls in an unnested structure), and Nested Control (i.e., requiring at least one nested control structure), based on the core computer science concepts delineated in the K-12 CS Framework [18] , and three gameplaying skills (Low, Medium, High) based on the required number of jumps and the width of the path the student's in-game avatar must navigate. To visualize the generated levels, we use a 2D tile-based level representation, as depicted in Fig. 1c .

Answer set programming (ASP) is a declarative programming paradigm, which has its roots in logic programming. In ASP-based PCG, a set of basic requirements and constraints needed for content generation is represented in logical terms (i.e., rules and ground facts) [19] . Then a solver (e.g., Clingo [20] ) produces all configurations of content (e.g., game levels) that satisfy the specified constraints. ASP utilizes two constructs: 1) Choice Rules to enable non-determinism in choosing ground facts, and 2) Integrity Constraints which explicitly define what must not be true in the logical world. Table 1 shows the specific constraints for the four CS learning objectives as well as the three different rulesets for the game-playing skill variations we are considering in ENGAGE.

Quantitative Evaluation. We measure the diversity among 100 levels created by the ASP-based level generator using the Clingo [20] solver for each of the 12 categories (four learning concepts combined with three game-playing skills) using a coordinate- based distance metric presented in previous works [21, 22] . The average diversity values of the ASP-generated levels within each category are shown in Table 2 . A diversity of 0 indicates that every matched pair of tile types between two levels is identical, while 1 indicates there are no tile types in common across the levels. The average diversity score across all 12 categories is 0.290, which indicates that 29% of tiles (i.e., 113 tiles out of 392 tiles) different between any pair of randomly chosen levels on average. This demonstrates that our model generates levels different to a certain degree consistently. While most categories achieved high diversity scores, Low game-playing skill levels across all CS concepts show comparatively lower scores because fewer variations are available within the walkable ground area in these levels.

Qualitative Evaluation. Two domain experts evaluated each level with respect to the presence of the CS learning objectives as well as the game-playing skill required for the level. The evaluators rated each level with game-playing skill (Low: 1, Medium: 2, High: 3) and one binary value for each of the four CS concepts, where 1 indicates the desired concept is present in the level, while 0 is not. The values reported in Table 3 are the averages of the two evaluators' ratings for 100 generated levels. Results for presence of CS concepts suggest that Sequence, Loop, and Conditional exhibit complete agreements between the human raters, while comparably less agreement occurs for the Nested Control. This phenomenon can be explained because some levels have a conditional barrier at the front or end of a path with a repetitive pattern that does not necessarily require use of nested blocks (e.g., it can be solved with a loop followed by a conditional block). Also, we found that there is a small degree of disagreement between Medium and High game-playing skill levels, while Low skill levels were consistently viewed as Low. 

Game-based learning environments show significant promise for creating engaging learning experiences for students. However, manually crafting a large number of game levels, which is typically required to adaptively support students' mastery learning, is labor-intensive. In this work, we presented an ASP-based PCG framework that automatically synthesizes game levels, and we investigated its generation capabilities for a middle-grade CS game-based learning environment. Evaluation results suggest that the ASP-based level generation framework creates diverse levels, while dynamically synthesizing levels that capture both the learning and game-playing skill-focused specifications. Together, our framework shows significant potential for offering adaptive CS learning experiences with enhanced replayability. In the future, it will be important to investigate robust student modeling techniques to inform the decisionmaking of the PCG framework to provide student competency-adaptive levels and effectiveness of personalized levels in terms of developing students' CS competencies.

Digital games, design, and learning: a systematic review and meta-analysis

Using tutors to improve educational games

Student agency and game-based learning: a study comparing low and high agency

Short and long term benefits of enjoyment and learning within a serious game

Problem solving and game-based learning: effects of middle grade students' hypothesis testing strategies on learning outcomes

What we can learn about student learning from open-ended programming projects in middle school computer science

Development of computational thinking, digital competence and 21st century skills when learning programming in K-9

K-8 learning trajectories derived from research literature: Sequence, repetition, conditionals

Bringing computer science into elementary school classrooms

BOTS: selecting next-steps from player traces in a puzzle game

Dragon architect: Open design problems for guided learning in a creative computational thinking sandbox game

Inducing stealth assessors from game interaction data

Integrating learning, problem solving, and engagement in narrative-centered learning environments

What is procedural content generation? Mario on the borderline

Automatically generating algebra problems

Using automatic item generation to create multiple-choice test items

Answer set programming for procedural content generation: a design space approach

The Art of Prolog: Advanced Programming Techniques

Clingo = ASP + control: Preliminary report

Generating educational game levels with multistep deep convolutional generative adversarial networks

Enhancements to constrained novelty search: two-population novelty search for generating game content

Acknowledgements. This research was supported by the National Science Foundation under Grant DRL-1640141. Any opinions, findings, and conclusions expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.