Multi-Player Games: Introducing Assignments with Open-Ended Strategies in CS2

James Heliotis, Sean Strout, Ivona Bezáková
Rochester Institute of Technology, Rochester, NY, USA

Summary This is a term-long project for students in a CS2-level course. It involves developing a player module for a real board game. Students are given a rule-checking engine and all necessary graphics. The focus is on developing a winning strategy that can defeat a reference player that uses a simple strategy. The purpose of the project is for the students to apply the data structures (arrays, lists, trees, and graphs) and algorithms to an interesting and open-ended problem. Although at this point in their education, artificial intelligence techniques are not formally taught, most students refer to the assignment as "writing an AI", and some do research classic techniques from the field of AI.
Topics Search, min-max, decision trees, backtracking, pruning
Audience CS2 or second-year level, depending on the program
Difficulty Depending on the game chosen, the difficulty for representation and strategy are independently low to high. Approximately eight weeks are given to the students, during which time they also do several smaller lab assignments based on the weekly lecture topics. Many of the deliverables are done by teams of two students.
Strengths The open-ended nature of determining one's own strategy is a great way to increase interest, motivation, and confidence while still getting the students to apply the course concepts. (We have some evidence from a 2012-13 study validating these claims.) The ungraded competition at the end of the term adds to the enthusiasm.
Weaknesses Some games are a better match for the exact topics covered in class than others (e.g. finding the shortest path). Maintaining a variety of games means you don't always have a perfect match. (But other lab assignments make up for much of any mismatch.)
Dependencies Knowledge:
  • 2-dimensional array manipulation
  • graph- and array-based searching
  • search through a set of configurations (possible moves)
  • elementary abilities in custom data structure design
  • (other skills depend on the approach)
System requirements
  • Standard Python or Java run-time libraries and compiler
  • (Eclipse or other IDE recommended)
  • Standard web browser to access game engine server
Variants We have been developing new game engines for the past few years. We have two games, Quoridor (Gigamic) and Gobblet (Blue Orange Games), running under our current architecture. Two additional games, AMAZEing Labyrinth (Ravensburger) and Cable Car (Queen Games), have engines that run locally on the student's computer, using an earlier version of Python (2.6). We plan to switch them to the new architecture in the future.

The following link takes you to the overview web site from the spring of 2013. It describes the Python version of the Quoridor game. (The original site was organized differently; we created the page below by pasting all the content onto a single page - please forgive any peculiarities in the appearance.)

Main Project Web Site

Finally, below please find the handouts we give to the students in our problem-solving sessions for the project. We have taken the attitude that the students should not be working ahead, especially due to the fact that students work in teams of two most of the time. Therefore the documents below are originally handed out in class in hard copy form.

Project Part 1 Student Handout

Project Part 2 Student Handout

Project Part 3&4 Student Handout

Post-Term "Battle Royale" Student Handout