James Heliotis, Sean Strout, Ivona Bezáková
Rochester Institute of Technology, Rochester, NY, USA
{jeh,sps,ib}@cs.rit.edu
| 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:
|
| 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.)
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