Programming Board Game Strategies in CS2* James Heliotis, Ivona Bezáková, Sean Strout Department of Computer Science Rochester Institute of Technology Rochester, NY, USA {jeh,ib,sps}@cs.rit.edu Abstract—This workshop presents freshman-level projects based on designing and programming player strategies for wellestablished board games. Unlike modern computerized games, board games are typically discrete, where the game state can be stored in basic data structures, and a variety of search techniques can be used to evaluate possible player moves. Such board games provide a natural context for many introductory Computer Science topics. The strategy component makes the project openended, motivating the students to keep improving their code. After appropriate background information is presented, to better understand how the project works from the students' perspective, participants will act as students, brainstorm through a variety of data structures, and develop a small part of a player module. Keywords—data structures; software design; algorithms; introductory computer science curriculum
I.
INTRODUCTION
Well-established board games such as Quoridor [3], The aMAZEing Labyrinth [2], and San Francisco Cable Cars [1] provide excellent opportunities to teach data structure and algorithm design to students in computer science. Because of the discrete turn-taking nature of the games and the simple organizations of the game board environments, a variety of search techniques can be used to evaluate possible player moves. We have developed game engines that graphically display the current game state as they cyclically call the individual player modules to make their moves. Every student team designs and implements its own player strategy in one of these player modules. Our latest engine, for the Quoridor game, runs remotely via a web service, which has given us the opportunity to provide client-side support code for player modules written in multiple languages, currently Java and Python. We provide, in each language, a player module template into which the students put their strategy implementation. We tested the framework at the Rochester Institute of Technology as part of the Computer Science 2 course taken by over 400 students from a variety of majors. The participants at the workshop will gain practice developing a simple path-determining algorithm for the Quoridor game. They will also experience testing a student code in the environment of a real game engine. The participants will receive the supporting project documentation and all necessary code modules so that they will be able to utilize the games in their own classes. Work supported by the NSF via the TUES grant program, award 1044721
978-1-4673-5261-1/13/$31.00 ©2013 IEEE
II.
THE TRUE TERM PROJECT
A. Design Through a small package on the student’s computer, the student’s code accesses a web-based “engine” service that displays the current state of the game back inside the student’s web browser. It cyclically calls functions in the student’s player module code. The student implements three functions: one that is called by the engine at the beginning of the game to initialize the player module’s data structures; one that is called by the engine whenever it is that module’s turn to move and that returns the chosen move of their player; and one that is called after every move, informing the module of the move so that it can update its data structures accordingly. B. Assignment Logistics The project is split into four separate parts to guide the students in implementing their strategies. In the first part, the students implement a function useful to the game, for example searching for the shortest path through a maze. In the second part, their software needs to be able to play as a single player in the game, computing moves that follow the rules of the game and updating data structures accordingly. The third part has them play against other players – without the need to win. The fourth part consists of designing and experimenting with a player strategy, requiring minimally that the students consistently beat an unsophisticated or random player. Many students go well beyond this base line and develop very clever strategies. At the end of the term, the students’ players compete in a not-for-credit tournament. At RIT there are problem-solving sessions scheduled at the time each new part of the project is assigned. The instructions for these sessions are part of the workshop’s documentation package. Instructors use these sessions in their classes to stimulate discussions about the project among small groups of students. The groups develop rough designs on paper before they proceed to their implementations. In other courses it may be more appropriate to dictate, or at least strongly suggest, specific approaches instead. It could also be an option whether students develop and submit their coded solutions individually or in teams. In our experience many students go well beyond what is required to pass the course. They seek out advanced computing concepts or come up with advanced approaches on their own in order to give their players an edge over other players.
III.
TABLE I.
WORKSHOP SCHEDULE
The goal of the workshop is to offer the project materials to the attending educators for use in their own courses. One of the best ways to assess the applicability of the materials to their own classes is to get faculty to go beyond just learning about the project by experiencing the work for themselves.
Topic Introduction
In brief, the workshop will introduce the projects and discuss their relevance to typical CS2 topics, demonstrate the "engine" software and the functions the students are asked to implement, describe the four project parts in detail for the Quoridor game, present several student-implemented strategies competing against each other, and finally give the participants a chance to develop their own strategies for the chosen game. A more detailed schedule follows in Error! Reference source not found.. The total time for this workshop is 3 hours.
Time Needed (min.) 5
Objectives and rationale for the board game projects
20
Brief description of individual board games used in our projects, and a short discussion of the underlying data structures and algorithms
15
Detailed description of the rules of one board game
10
Demonstration of the corresponding engine
10
Description of the individual project parts
10
Demonstration of student-implemented strategies
After the workshop the participants will be familiar with the described CS2-level project, which is open-ended enough to accommodate the beginning programmer with the achievable goal of beating a random player. They should also have a fair idea of what it takes to build an engine for new games, including ones that are simpler or more advanced than the ones shown. IV.
WORKSHOP SCHEDULE
5
Break
15
Hands-on session: participants act as students
75
Discussion
15
MATERIALS PROVIDED
Participants will be provided with both the software and documentation for the project. The software includes access to a web-based engine that runs games for students, and personal copies of client support software that is easily adapted to many languages. (Currently we support Java and Python versions.) Participants also get the full set of materials for the project, including individual project part descriptions and the related "problem solving" documents. The problem solving documents are to be used in a course to stimulate discussions about the project among small groups of students. The rough designs so generated are used as starting points for the lab work. The participants will bring home hard copies of the documents and will be given a URL where the documents, supporting software libraries, and the game engine service will be made available.
REFERENCES [1] [2] [3]
Dirk Henn, San Francisco Cable Car, published by Queen Games, 2009. Max J. Kobbert, The aMAZEing Labyrinth, published by Ravensburger, 1986. Mirko Marchesi, Quoridor, published by Gigamic, 1997.
