Game—The Game of Thrones Quest for Optimality: A Role Playing Game for Teaching the Art of Linear Programming

1. Introduction

Mathematical modeling is one of the most important skills of any professional active in operations research (OR) or management science (MS). At the same time, it is one of the most difficult skills to teach. Modeling can be seen as an art: There is no “formula” or “exact scheme” one can follow, and as such, it requires sustained practice in order to master this skill. Becoming a good modeler not only requires insight and knowledge but also creativity and passion. It demands regular effort from students through numerous exercises that gradually increase in complexity and ambiguity. To this end, it is crucial that students get sufficient opportunities to develop models all by themselves. For this reason, OR textbooks contain plenty of modeling exercises. An example of a classic linear programming (LP) exercise on developing a blending model can be found in Winston (2004, section 3.8, problems group A, exercise 6, p. 93):

“Bullco blends silicon and nitrogen to produce two types of fertilizers. Fertilizer 1 must be at least 40% nitrogen and sells for $70/lb. Fertilizer 2 must be at least 70% silicon and sells for $40/lb. Bullco can purchase up to 80 lb of nitrogen at $15/lb and up to 100 lb of silicon at $10/lb. Assuming that all fertilizer produced can be sold, formulate an LP to help Bullco maximize profits.”

Although this kind of classic textbook assignment certainly provides opportunities for practice, one cannot say they are highly attractive. In our experience, with the exception of some intrinsically highly motivated students, it is hard to stimulate students to practice modeling with these kind of exercises. However, there do exist several good alternatives to trigger students to practice modeling. As argued by Cochran (2004), one possibility is to use applications that relate more to the free time or hobbies of students. Trick (2004) introduced the use of sports scheduling for teaching integer programming (IP), an idea adopted by Chlond (2011) and further developed and integrated within a real-life context by Goossens and Beliën (2023), who use the yearly process of developing a new schedule for the Jupiler Pro League, Belgian’s highest national soccer league, in their IP modeling courses. Another recent example of using sports in the OR classroom is provided by Chan et al. (2023), who present a case study on the lineup optimization in wheelchair rugby that covers descriptive, predictive, and prescriptive analytics.

Besides applications related to hobbies or sports for teaching modeling, students can also be engaged more actively by introducing some competition through a game setting. This paper combines the free time application context and the game approach by presenting an educational game built entirely around the popular HBO series Game of Thrones for teaching LP modeling. The game entitled “Game of Thrones: The Quest for Optimality” (GoTOpt) provides an alternative to traditional applications in business and challenges students with optimization problems in a totally different context. The game runs in Microsoft Excel and has been developed using Visual Basic for Applications (VBA). Since 2016, this game has been successful in increasing the students’ commitment and motivation for finding correct formulations and optimal solutions for various LP modeling exercises. GoTOpt has the following specific goals while aiming at improving the students’ modeling skills:

• arousing interest in operations research;

• implementing a small degree of competition to keep students excited;

• offering repetition exercises for an introductory LP course that focuses on modeling;

• enhancing the students’ problem modeling and problem solving skills.

Many introductory OR courses start with LP: modeling basic LPs, the simplex algorithm, sensitivity analysis, and duality theory. However, the majority of educational puzzles and game papers for teaching modeling (Section 2) focus on teaching IP modeling and particularly on the modeling of logical constraints that require the use of binary variables. Our paper advances the OR education literature by presenting an educational game that focuses on the basics of LP modeling (which need to be mastered before tackling IP). Indeed, GoTOpt can be used as an exercise to get students familiar with a new type of problem or as an additional practice or repetition exercise in an introductory OR course that mainly focuses on LP modeling. It can also be used to refresh students’ knowledge on LP modeling at the start of a subsequent IP/OR course. If GoTOpt is used as a repetition or refresher exercise, students should already have been instructed on the different types of problems that are presented in the encounters: blending, production process, transportation, work scheduling, and multiperiod production planning problems, as well as sensitivity analysis. If GoTOpt is used as an exercise to get familiar with a new type of problem, then no prior knowledge of these problem types is required; however, a general introduction to optimization modeling is, of course, a prerequisite.

This paper proceeds as follows. Section 2 gives an overview of the related literature. Section 3 presents GoTOpt. Section 4 describes our and our students’ experience with using GoTOpt for teaching and learning. Section 5 concludes this paper.

2. Literature Review

Classroom games have been used successfully for teaching modeling. Beliën et al. (2011) present the use of a cycling fantasy game in the classroom, where students are challenged with finding an initial optimal team of 30 riders and optimal replacements of up to 5 riders for each of the five transfer moments. The game entails features of stock markets, multiple period modeling, and logical if-then constraints. The whole optimization problem is subdivided into three stages with increasing complexity, which makes the game particularly suitable for teaching IP modeling in a gradual manner. Arenas-Vasco et al. (2024) propose a modeling exercise around the popular online game “Among Us.” Participants need to find the fastest route to finish a given set of tasks at different areas in a spaceship without encountering the “Imposter.” The game is used to teach both heuristics and exact (IP) modeling in an introductory OR course. Beliën et al. (2013) present the use of an online energy supply game, in which students take the role of an energy expert who advises a city on its energy supply. The challenge is to find a feasible combination of energy sources. Although the online game is inherently a constraint satisfaction problem, the game is turned into an optimization challenge for teaching by considering several scenarios in which each time one of the constraints is turned into an optimization objective (e.g., minimizing CO₂ emission, minimizing the number of nuclear energy plants, minimizing costs, etc.). Although integer decision variables are used to represent the number of power plants of each type, this game can also be used to teach basic LP because fractional solutions can be interpreted, and no logical constraints (that require the introduction of binary variables) are included.

Logical puzzles have also been used successfully for teaching modeling. These puzzles all focus on teaching the modeling of logical constraints using binary variables. DePuy and Taylor (2007) provide four examples of the use of puzzles (the Cracker Barrel Peg Board puzzle, the Tower of Hannoi, Peg Solitaire, and Rush Hour) as pedagogical tools in teaching operations research. All four puzzles can be solved by linear IP models. More recently, Hartmann (2018, 2019) presents how IP modeling can be taught using six smartphone puzzle apps. Iranpoor (2021) uses the Knight Exchange puzzle to teach students the value of strong formulations by demonstrating how a minimum cost network flow formulation largely outperforms a general binary formulation for solving the puzzle. Barlow (2023) presents a spreadsheet for solving Sudoku puzzles and a generalization called “n-doku” puzzles using the LibreOffice Calc built-in solver. Also, Rasmussen and Weiss (2007) and Weiss and Rasmussen (2007) use the Sudoku puzzle to teach IP modeling using a spreadsheet implementation. Lakhani et al. (2023) demonstrate how the Wordle game, a popular single-user word guessing puzzle, can be (partly) solved using IP. More specifically, the puzzle is solved by first discovering which letters appear in the target (which is optimized using IP) and then guessing the target by rearranging the discovered letters (which is left to the puzzler). Harris and Forbes (2023) use the Snake Eggs puzzle not only for teaching 0-1 IP modeling but also to introduce students to Benders decomposition. Also, in Pearce and Forbes (2017), more advanced mathematical modeling concepts such as lazy constraints and composite variables are illustrated using the Fillomino puzzle.

Games and puzzles are a perfect way to introduce some competition among students in the classroom. Competition brings many benefits like increasing active participation, stimulating teamwork, and encouraging students to find alternative solutions to problems (Thrasher 2008). Colajanni et al. (2024) report competitive learning as one of the key features of Ricerca Operativa Applicazioni Reali (ROAR; in English, Real Applications of Operations Research), a three-year project for higher secondary schools in Italy. They introduce competition through a vehicle routing problem by using a shared results sheet and awarding a small symbolic prize to the best team.

3. GoTOpt Game

3.1. Game Overview

In GoTOpt, the player (a player can be a single student or a team of students that work together) takes on the role of a young miner’s son, who encounters five important leading characters from the HBO television series Game of Thrones (Figure 1). More details on the storyline and the five encounters are given in Appendix A. Every encounter involves formulating and solving an LP problem correctly in order to move on to the next one (although students can choose to skip the next encounter when they are stuck by pressing the skip button). This provides the student with clear short-term goals, which enhances the game play and thus the interest for the game. The time in which a student finishes the game is recorded and eventually used to calculate the rank out of five possible positions in the king’s small council. Every player follows the same storyline and is challenged with five standard LP modeling problems that are included in many introductory LP handbooks (Winston 2004):

• a blending problem;

• a production process problem;

• a transportation problem;

• a work scheduling problem;

• a multiperiod production planning problem.

Additionally, one of the characters related to the production process problem presents a question that boils down to a sensitivity analysis exercise.

The only difference with more traditional LP formulation exercises is that the in-game problems have the Game of Thrones theme. For instance, the blending problem involves producing poison vials to kill enemies instead of the classic oil production problems. One needs to optimize the movement of troops on the battlefield instead of the classic transportation problems that minimize the cost of distributing goods to customers.

On completion of the last encounter, the student is guided to a final worksheet containing only one active element, which is a button that will calculate the player’s score based on the time needed to complete the game (Figure 2). When clicking the button, the student’s position in the small council will light up in the throne. The better the student performed, the higher his/her rank in the small council. Performance is calculated based on the time to complete all encounters and the number of encounters skipped, in which every skip decreases the rank by one position. Regarding total completion time, based on our classroom experience (Section 4), we determined the ranks as follows:

• hand of the king (under two hours of playing time);

• master of coin (under three hours of playing time);

• master of whisperers (under four hours of playing time);

• master of ships (under five hours of playing time);

• lord commander of the Kingsguard (otherwise).

Be aware that the playing time to work through all encounters may be quite extensive; we consider less than two hours to complete the game an excellent score. However, there is the possibility to save the progress in the game (by saving the Excel file) and resume at a later time. When the file is not saved, the game will start at the point where the file was last saved. However, when the file was saved while an encounter was already started, resuming at a later time will immediately rank you on the lowest level (Lord commander of the Kingsguard). On the other hand, when the file was saved before starting another encounter, the calculation of the playing time will not take into account the inactive period. The skip button can also be used to navigate to a particular encounter; however, it is not possible to return to a previous encounter once the game has been (auto-)saved in a later stage.

3.2. Data Format and Solvers

The student’s assignment file (Game of Thrones-Quest for Optimality.xlsm) (not password protected, except for accessing the VBA code in this file), the solution Excel file (GameOfThronesQuestForOptimalitySolutions.xlsm) as well as LINDO files, and IBM CPLEX .mod and .dat files for all encounters in the game, are provided as supplementary material to this publication. Although the assignment Excel file will be available for download for all readers, the solution files will only be available for registered and verified instructors. Registered and verified instructors are also the only ones with access to the teaching note, which provides the storyline of all game encounters and related problems, their LP formulations and solutions, and the password required to access the VBA code in the student’s assignment file.

Because all data are provided in Excel, the Excel solver tool is the most natural approach for finding optimal solutions. All problems can be solved using the standard Excel solver, so there is no need to install an advanced spreadsheet solver like Premium solver, OpenSolver, or SolverStudio. Although data are given in Excel, other solvers could be used as well. For instance, IBM ILOG CPLEX Optimization Studio can easily read spreadsheet data using the SheetConnection and SheetRead command. Excel data can also be imported in Python using the Pandas module after which they can be used as input to an optimization model that can be solved by CPLEX, Gurobi, or PuLP. As such, the game can also serve as a tool to gain insights into how spreadsheet models translate to algebraic models and vice versa.

4. Classroom Experience

GoTOpt has been used for teaching LP modeling in an introductory course of LP for undergraduate business engineering (a program at the interface of business management and engineering) students at KU Leuven (Belgium) since 2016. This course requires a thorough mathematical basis and assumes knowledge of linear algebra (system of equations, matrix calculations, etc.). However, no prior knowledge of LP is assumed. The course covers LP modeling including all standard problems as presented in Winston (2004), the simplex algorithm, duality theory, and sensitivity analysis. In 2016, GoTOpt was used as a repetition exercise during a two-hour session (PC laboratory) in the last class of the semester. We opted for an in-class exercise as this stimulates competition among students. Our students, however, needed more time than two hours to successfully complete all five challenges. We gave the students an after-class homework assignment to finish the encounters they did not complete during class time. If other instructors opt to use the full game in a classroom session (PC laboratory), we recommend to anticipate a duration of at least four hours. Because the contact hours for our LP course are limited, we decided to use the game from 2017 onward as a homework assignment, enabling all students to experience the adventure at their own pace at the cost of losing the competitive aspect of playing simultaneously against other students or student teams. In the homework assignment, students have been asked to develop either spreadsheet models (to be solved with the standard Excel solver) or algebraic models (to be solved using LINDO or CPLEX Optimization Studio), or both, for each in-game optimization problem.

In 2016, the game was assessed by 12 bachelor students through a formal questionnaire consisting of five statements. These statements mainly reflect the main goals of the game, which were (1) arousing interest in operations research, (2) focusing on a fictional theme as opposed to a modern-day business theme, (3) implementing a small degree of competition to keep students excited, (4) designing the game in a way it can be used as a repetition exercise to prepare students for upcoming exams in an introductory LP course that focuses on modeling, and (5) enhancing the students’ problem modeling and problem-solving skills.

Table 1 shows that 8 of 12 students (strongly) agree that the game increased their interest in operations research. Furthermore, although only 2 of the 12 students watch Game of Thrones, which was asked before the test, 8 of 12 students liked the fictional theme. The answers also revealed that most students were not fully convinced by the competitive aspect of the game, although only two students did not like it. From our experience in monitoring the game during the PC laboratory session in 2016, we noticed a strong need for cooperation, given that neighboring students were already working together on the problems. Although Microsoft Excel was not the main software used in these LP classes, 8 of 12 students stated that the game improved their modeling skills with Microsoft Excel and the use of the Excel solver function. Although presented in Excel, some of the students opted to model and solve the problems in LINDO, as they were more familiar with this software. Finally, all 12 students agreed that the game provided a good repetition of the problems taught in class, with 8 of them strongly agreeing with this statement.

Table 1. Questions and Results of a Survey Filled Out by 12 Students After Having Played GoTOpt as a Two-Hour PC Room Session in 2016

At the end of the 2016 survey, we also gave the students the opportunity for open feedback. We received the following individual comments:

• “The problems were not always well readable because of the font face of the text on the scrolls.”

• “I give it an 8 out of 10.”

• “It was very original. One of the best games I’ve ever had.”

• “Very fun revision game.”

The first comment concerns the font face (Monotype Corsiva) of the text on the scrolls in the encounters. We chose this font because it fits well within the theme due to the handwritten feel it provides. We decided to keep this font because students can always increase the zoom in Excel if they have difficulties reading the scrolls.

A second survey was performed in 2023 after having used the game as homework for the same course. The answers (Table 2) are largely in line with those from 2016, with two notable differences. First, the competitive aspect of the game was not appreciated as much (four students did not fill in this question because they deemed this question not applicable). The fact that we split the game over two separate homework assignments and the fact that there was no direct comparison with other students possible explain this result. Second, a bit more than half of the students claim that the game did not improve their modeling skills with Excel (solver). This can be explained by the fact that we gave the students free choice on which solver to use. Because, more than in 2016, classes had focused on using LINDO, most students opted to use the more familiar package for the homework and hence did not improve their skills with the Excel solver.

Table 2. Questions and Results of a Survey Filled Out by 22 Students After Having Played GoTOpt as Homework in 2023

5. Conclusion

This paper has presented an educational role-playing game built entirely around the popular HBO series Game of Thrones. The game is entirely embedded in Excel, and the optimization challenges can be solved either directly by using the Excel solver or indirectly by an algebraic optimization model developed outside Excel. The use of Excel makes the game accessible for all types of students, whereas the flexibility in solving the challenges by either spreadsheet models or algebraic models makes the game suitable for business students as well as engineering students. Besides increasing the students’ motivation, the main contribution of GoTOpt is providing a fun competitive exercise for learning basic LP modeling, whereas earlier published educational games or puzzles have mainly focused on modeling logical relations using binary variables.

Since 2016, GoTOpt has been used successfully in an introductory bachelor course on LP at KU Leuven (Belgium). Starting in 2024, the game will also be used at University Linköping (Sweden) in a similar course. Survey results reveal that the game increased the students’ motivation and suggest a strong added value for the LP course. Future research could focus on a more in-depth analysis of the teaching effectiveness of an educational game such as GoTOpt, for example, by comparing students’ modeling skills before and after playing the game or by comparing subjects who play the game with subjects who are presented an alternative teaching format (e.g., traditional exercises). Another promising avenue for future research is the use of artificial intelligence (AI) and machine learning (ML) to further improve the teaching power of games such as GoTOpt. The current version of GoTOpt gives a hint each time a student submits a solution value that corresponds to a typical modeling error. Obviously, the checking of solution values alone cannot catch all modeling mistakes nor link all possible solution values unambiguously to modeling mistakes. A direct feedback method that relies on pattern recognition using AI/ML methods that “scan” models and provide immediate feedback would definitively improve the teaching power of this game.