Learning Binary Search Trees through Serious Games Alberto Rojas-Salazar1[0000-0002-0097-3772], Paula Ramírez-Alfaro2 [0000-0002-0097-3772] and Mads Haahr1[0000-0002-9273-6458] 1 Trinity College Dublin, Dublin, Ireland {rojassaa,mads.haahr}@tcd.ie 2 University of Costa Rica, Alajuela, Costa Rica paula.ramirez@ucr.ac.cr Abstract. Data structures and algorithms are core topics in Computer Science, but they are difficult topics to grasp. Data structures and algorithmic concepts are abstract and difficult to relate to previous knowledge. To facilitate the learn- ing process of these topics, learning tools that link new information with previ- ous knowledge in an active way may be a useful approach to teach data struc- tures and their algorithms. Furthermore, serious games have the potential to serve as a learning tool that accomplishes both objectives: to link new infor- mation with previous knowledge and to facilitate active learning. To tackle these issues, we developed DS-Hacker, an action-adventure serious game that utilizes the game elements to represent the BST properties and structure. In this paper, we report the results of a pilot experiment that compares the learning gains after completing two learning activities: (1) playing a serious game for learning Binary Search Trees, and (2) reading a summary and watching two video tutorials. Additionally, we report the results from a qualitative survey that evaluated the game usability, player satisfaction and the participants’ perception about the means used by the game to deliver the BST concepts. Keywords: Binary Search Tree, Data Structures, Serious Games. 1 Introduction Data structures and algorithms are core topics in Computer Science, and they are essential for the development of efficient software [10]. Due to the relevance of these topics, data structures and algorithms are included in the guidelines for undergraduate degree programs developed by the Association for Computing Machinery (ACM) [7]. Typically, universities teach the first introductory data structure course in the second year of their undergraduate Computer Science programs [8]. While a deep understanding of data structures is fundamental knowledge for com- puter scientists, advanced data structures and their algorithms are difficult topics to grasp [2]. Data structures and algorithmic concepts are abstract and difficult to relate to previous knowledge. From a constructivist point of view, it is important that new experiences and information link to previous knowledge in order to create new knowledge [6]. Educators should provide experiences and environments where the 2 students can construct knowledge through reflection, critical thinking and their previ- ous knowledge [6]. Therefore, learning tools that complement classes by linking new information with previous knowledge in an active way may be a useful approach to teaching data structures and their algorithms. In view of the above, serious games have the potential to serve as a learning tool that accomplishes both objectives: to link new information with previous knowledge and to facilitate active learning. Many game genres are popular among teenagers and young adults, and well-crafted video games promote active learning [5]. Usually, video games offer challenges that require active engagement of the player. Therefore, serious games may take advantage of these characteristics in order to facilitate the association of new information with previous knowledge and active learning. In this paper, we present a serious game for teaching Binary Search Trees (BSTs) called DS-Hacker (Data Structure Hacker). DS-Hacker aims to introduce BST con- cepts to college students by means of relating well-known game elements with BST concepts. These relations are presented to the learner through analogies embedded in the game. We also report the results of a pilot experiment that compares the learning gains after completing two learning activities: (1) playing DS-Hacker, and (2) reading a summary and watching two video tutorials. Finally, we report the results from a qualitative survey that evaluated the game usability, player satisfaction and the partic- ipants’ perception about the means used by the game to deliver the BST concepts. Results show that both learning approaches produces a learning effect and that there is no statistically significant difference between both activities. The qualitative survey suggests that participants perceived that they learned while playing the game, and that they could relate the BST concepts and structure with the DS-Hacker game elements. 2 DS-Hacker DS-Hacker is a PC game developed with Unity 3D, and its target population are uni- versity students from Computer Science and Engineering Schools. The game is a third person 3D action-adventure game, a well-known genre. The aesthetics are sci-fi style, and its story takes place in a distant future where a corrupt corporation is harming the balance of society. In the game, the player takes the role of the robotic hacker that must traverse a maze composed of chambers and extract the information stored in the maze. A video file of the gameplay of the English version is available through the following link: https://www.dropbox.com/s/8vavy0e7b9uywx6/DS- Hacker_Level1%26Level2.mp4?dl=1 To achieve learning of the BST structure, DS-Hacker uses an analogy between the BST structure and the environment structure. According to the game plot, corpora- tions hide and protect their information in places called “Data Systems” (our game environment). Data systems are mazes organized as well-known data structures, and to achieve our teaching objective, the Data System reflects the structure of a BST. Therefore, many elements of the game environment represent the most important elements of the data structure. For instance, in DS-Hacker, the maze’s rooms repre- 3 sent the nodes; the portals of each room represent the links that points to other nodes; the room ID represents the comparable key; and the information stored in each room represents the associated values of each node. Furthermore, the chambers of the maze are organized following the BST property. The game story serves a major function because it delivers the conceptual knowledge. The game story is delivered through a non-player character (NPC) named Anonymous who always appears at the beginning and at the end of each level. Anon- ymous introduces the missions and the necessary BST concept to accomplish them. In order to facilitate the understanding of the BST concepts, Anonymous takes ad- vantage of analogies between the game elements and the BST elements. For instanc- es, in the first two levels, Anonymous informs the player about the relation between the game environment structure and the BST structure. In the last three levels, Anon- ymous presents the relation between the game challenges and the search algorithm. Currently, DS-Hacker possesses five levels, and each level focuses on different concepts of the BST data structure. Level one and two cover topics related to the basic structure of the BST, its properties, and the structure of its nodes. Level three, four and five cover topics related to the search algorithm such as the sequence of the algorithm’s steps and its outcomes. Furthermore, each level has a mission, and each mission possesses one or more challenges. Missions provide opportunities to apply and solve problems using the concepts given by Anonymous and to experience the structure of the BST in a concrete manner. 3 Method Our pilot experiment follows a “switching replications” experimental design. In the study, participants are randomly divided into two groups, G1 and G2. Both groups must complete two activities (the treatment and the control activity) and answer three tests (pre-test, mid-test and post-test). The study is organized as follows: First, all participants take a pre-test; then G1 performs the treatment, and G2 performs the control activity; then, all participants answer the mid-test; then, G1 and G2 switch and perform the other activity; finally, all participants respond the post-test. Switching replications design may decrease social threats to validity, since it allows all partici- pants equal access to the treatment activity [4]. However, the learning effect due to the overexposure to the test may lead to a testing threat [4]. The experiment was carried out as a workshop during a class of the 2020 Summer Term in University of Costa Rica. Participants were randomly divided into two groups and assigned to a computer with the game already installed. Participants of the G1 played the Spanish version of DS-Hacker (the treatment); meanwhile, participants of the G2 completed the control activity. Then, G1 performed the control activity, and G2 played the game. The control activity included two popular teaching methods: a written summary of the BST concepts and three video tutorials. The summary was a Spanish translation of 4 the book Algorithms by Sedgewick and Wayne [10]. The first video tutorial1 was about BST structure and characteristics, and the second2 was about the search and insert operations (the insert operation was not evaluated). The third video tutorial3 was a general summary about the BST basic concepts and operations. The pre-test, mid-test and post-tests were designed to assess the learning gains. The tests have 23 questions and cover the first four levels (remember, understand, apply, and analyze) of the revised version of the Bloom’s taxonomy [1]. The questions were multiple-choice, and their construction followed the guidelines suggested in [9]. Fur- thermore, the questions verify factual, conceptual and procedural knowledge. Besides the tests, participants took a demographic survey at the beginning of the experiment and a qualitative survey to evaluate game at the end of the experiment. All surveys (and tests) were performed using Google Forms. Initially, 32 students participated in the experiment; however, we excluded 5 par- ticipants from the analysis because they did not complete one of the tests. Therefore, we only take in consideration the 27 participants who completed all the evaluations. Group 1 (the experimental) had 13 participants, and Group 2 (the control) had 14. In terms of background, 11 students were from the Computer Science School; 10 stu- dents were from the Industrial Engineering School; and 5 students from the Electrical Engineering School and the Mathematics School. 4 Results and Discussion Figure 2 shows the average of the scores obtained during the pre-test, mid-test and post-test of the G1 and the G2. The chart presents a learning effect for both activities. After the first round of activities, G2’s participants performed better in the mid-test than G1’s participants. On average, G1’s participants (who played the game) in- creased 2 points. Meanwhile, G2’s participants (who watched the video tutorials) increased 3.79 points. After switching and completing the second round of activities, G1’s participants performed better in the post-test than G2’s participants. G1’s partic- ipants increased 1.69 points; G2’s participants decreased 0.36 points. After both activ- ities, G1’s participants increased 3.69 points, and G2’s participants increased 3.43. Table 1 presents the mean and the standard deviation of each test. Additionally, we performed a t-test analysis to verify whether the difference be- tween the means of the pre-test, mid-test, and post-test were statistically significant. Table 2 presents the results, showing no significant difference. We also verified whether the difference between mid-test and pre-test and post-test and pre-test of G1 and G2 were statistically significant. To achieve this, we performed a series of two- tailed paired t-tests with an alpha of 0.05. In addition, to verify the magnitude of the difference, we calculated the Cohen’s d that quantifies the effect size. In our case, it determines the magnitude of change in scores. Cohen’s d result larger than 0.80 is 1 https://youtu.be/Bh61AvHAf90 2 https://youtu.be/DVKDQcJOqy8 3 https://youtu.be/mTMrszfrNtI 5 considered a large size effect; a result around 0.50 is considered a medium size effect, and around 0.20 a small size effect [3]. Table 3 shows the results of the calculations. Pre-test, Mid-test and Post-Test Mean - G1 and G2 17 16 15 14 13 12 11 10 PRE-TEST MID-TEST POST-TEST G1 G2 Fig. 1. Mean of the pre-test, mid-test and post-test of G1 and G2. Table 1. G1 and G2 Pre-test, Mid-test and Post-test means and standard deviation. G1 G1 G1 G2 G2 G2 Pre-test Mid-test Post-test Pre-test Mid-test Post-test Mean 12.231 14.231 15.9230 11.286 15.071 14.714 StDev 3.395 2.948 2.6914 3.832 3.452 3.730 Table 2. Mean, p-value and t statistic of the difference of scores N Pre-test Mid-test Post-test Group 1 - Mean 13 12.231 14.231 15.923 Group 2 - Mean 14 11.286 15.071 14.714 Difference P-Value 0.503 0.502 0.341 T Statistic 0.679 -0.682 0.971 Table 3. T Statistic, p-value, and effect size of the difference between Mid-test and Pre-test, and Post-test and Pre-test. P Value T Statistic Effect Size Difference: Pre-Test and Mid-test of Group 1 0.0218 -2.6331 0.63 Difference: Pre-Test and Mid-test of Group 2 0.000009 -5.7303 1.04 Difference: Pre-Test and Post-test of Group 1 0.000095 0.7012 1.21 Difference: Pre-Test and Post-test of Group 2 0.000094 -5.5511 0.91 The previous results indicate that both learning activities were effective. The dif- ferences between pre-test and mid-test of G1 and G2 are statistically significant. However, the results show that the control activity (reading and watching video tuto- rials) was more efficient than playing DS-Hacker. For instance, the effect size of the 6 difference between the mid-test and pre-test of G2 is higher than the size effect of G1. Additionally, the average score of the mid-test of the G2 is almost the same as the average score of the post-test of G1. Even though, the difference between mid-test and post-test averages are not statistically significant. Another interesting finding is that G2 slightly decreased its performance during the post-test (after playing the game) and that G1 increased the scores in the mid-test and post-tests. This discovery suggests that the order of the treatment may affect the learn- ing gains. More studies regarding the order of the learning activities may lead to promising results. The qualitative survey has 19 four-point Likert-scale questions divide into three categories. The first category (Q1-Q6) assesses the participant’s perception about learning and the means used by the game (environment, story and challenges) to de- liver the BST concepts. The second category (Q7-Q15) assesses the usability. The third category (Q16-Q19) assesses the enjoyability. We only present the answers of the 27 participants who completed all the tests. Table 4 presents the percentage of the positive answers (“Strongly agree” and “Moderately agree”) of the qualitative survey. Table 4. Distribution of the positive answers of the qualitative survey. Questions Agree Questions Agree % % Q1. The game help me to understand 77.78 Q11. The game tutorial was useful and 81.48 BST structures. clear. Q2. The game help me to understand 81.48 Q12. The voice and way of talking of 81.48 the nodes’ structure. the NPC ware clear. Q3. The game help me to understand 59.26 Q13. Game missions were clear. 81.48 the search algorithm. Q4. I could relate concepts presented in 88.89 Q14. The game GUI was easy to un- 85.19 the game story with the BST concepts. derstand and intuitive. Q5. I could relate the game environ- 85.19 Q15. The game menu has useful op- 81.48 ment with the BST structure. tions. Q6. The game allows me to practice 85.19 Q16. I enjoyed playing DS-Hacker 70.37 the previously learned BST concepts. Q7. The game was easy to learn. 85.19 Q17. I like the way that BST concepts 81.48 were presented during the game. Q8. The game controls were easy to 66.67 Q18. I think that video games increase 85.19 learn. my motivation towards computer science topics. Q9. The game controls respond 48.15 Q19. I would like more serious games 81.48 smoothly. to be used to teach data structures. Q10. The map was easy to understand. 77.78 Most of the answers of the qualitative survey were positive. However, three ques- tions received a considerable number of negative responses, indicating that the game has some problems. Q3 responses indicate that half of the participants could not un- derstand the search algorithm principles while playing the game. This is an indication that we should improve the content and levels that cover the topic. Second, Q8 and Q9 answers suggest that participants had trouble dealing with the game controls. The cause of this problem was the low performance of the computers utilized during the 7 experiment. We should consider this factor, and we should optimize the game to make it appropriate for low performance computers. Regarding the learning approach of the game, participants reported that they could relate the BST concepts with the game environment and the story. Additionally, re- sults indicate that participants think that the game provides an environment that al- lows them to practice the BST concepts. Finally, participants reported that they felt that they were learning while playing the game, and that in general, they enjoyed the game. 5 Conclusion and Future Work The article also presented the results of a pilot experiment and a qualitative evaluation of DS-Hacker which aims to facilitate learning of the BST data structure and associat- ed algorithms by linking new information with previous knowledge and facilitating active learning. The results of the pilot experiment show that the treatment (playing the game) and the control activity (reading a summary and watching video tutorials) produced learning gains on the participants. Differences between the scores obtained by the treatment group and the control group were not statistically significant. How- ever, results from the mid-test suggest that the control activity is slightly more effi- cient than playing the game. Our qualitative evaluation showed that the participants could relate game elements (game story, environment and challenges) with the BST concepts. This finding sug- gests that these game elements may be used to delivery educational information. Ad- ditionally, participants felt that they learned while playing the game. Regarding the usability of the game, we must optimize the game to run on low performance comput- ers. In general, participants reported that they enjoyed playing the game. In the future, we plan to redesign the levels that cover the search algorithm and add more level covering other BST operations such as the tree traversal algorithms and the insert algorithm. References 1. Anderson, L.W., Krathwohl, D.R.: A taxonomy for learning, teaching, and assessing: a revision of Bloom’s taxonomy of educational objectives. Longman, New York (2001). 2. Becker, K., Beacham, M.: A Tool for Teaching Advanced Data Structures to Computer Science Students: An Overview of the BDP System. In: Proceedings of the Second Annu- al CCSC on Computing in Small Colleges Northwestern Conference. pp. 65–71 Consorti- um for Computing Sciences in Colleges, USA (2000). 3. Dicheva, D., Hodge, A.: Active Learning Through Game Play in a Data Structures Course. In: Proceedings of the 49th ACM Technical Symposium on Computer Science Education. pp. 834–839 ACM, New York, NY, USA (2018). https://doi.org/10.1145/3159450.3159605. 4. Eagle, M., Barnes, T.: Experimental Evaluation of an Educational Game for Improved Learning in Introductory Computing. In: Proceedings of the 40th ACM Technical Sympo- 8 sium on Computer Science Education. pp. 321–325 ACM, New York, NY, USA (2009). https://doi.org/10.1145/1508865.1508980. 5. Gee, J.P.: What Video Games Have to Teach Us about Learning and Literacy. Palgrave Macmillan, New York (2007). 6. Gogus, A.: Constructivist Learning. In: Seel, N.M. (ed.) Encyclopedia of the Sciences of Learning. pp. 783–786 Springer US, Boston, MA (2012). https://doi.org/10.1007/978-1- 4419-1428-6_4049. 7. Joint Task Force on Computing Curricula, A. for C.M. (ACM), Society, I.C.: Computer Science Curricula 2013: Curriculum Guidelines for Undergraduate Degree Programs in Computer Science. ACM, New York, NY, USA (2013). 8. Lawrence, R.: Teaching data structures using competitive games. IEEE Transactions on Education. 47, 4, 459–466 (2004). https://doi.org/10.1109/TE.2004.825053. 9. Moreno, R. et al.: Directrices para la construcción de ítems de elección múltiple. Psico- thema. 16, 3, 490–497 (2004). 10. Sedgewick, R., Wayne, K.: Algorithms. Addison-Wesley (2014).