Board Games Suitable for Programming Projects

The board games listed below are all especially suitable for programming projects in CS 1, CS 2 and/or Discrete Math. They exhibit three key characteristics:

All the games listed below use conditionals and loops. Other key CS concepts are listed with each game. Any project can have a file I/O component by simply requiring that there be a mechanism to load and save the state of a game in progress.

Below is a list of Anticipated Reviewer Questions.


Igel Argern
Description:
Players race to move a set of tokens (hedgehogs) from left to right while avoiding obstacles. As the hedgehogs scramble across the board, they climb on top of each other preventing those at the bottom of the stack from moving.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/95
Key CS Concepts:
  • Two dimensional arrays
  • stacks
  • inheritance
Interesting pedagogical aspects:
From an instructor's perspective, the most compelling aspect of this game is that it provides an excellent opportunity for students to design a program that makes "non-trivial" use of inheritance and polymorphism. The rules list many possible behaviors for the "obstacle" squares on the board. (Two examples are concrete pillars and pits that trap the hedgehogs.) These different behaviors can be encoded in different subclasses. To further emphasize polymorphism each obstacle square can have a different behavior.


Blokus
Description:
Players compete to fit as many odd-shaped pieces as possible onto a board. A player's pieces may only connect diagonally; thus, the challenge is to block other players thereby saving room on the board for one's own pieces.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/2453
Key CS Concepts:
  • Two dimensional arrays
Interesting pedagogical aspects:
Each of a player's pieces is a different shape; students must devise (1) an object to describe a shape in general, and (2) an algorithm to determine if a shape fits legally on the board.


Can't Stop
Description:
In some sense, Can't Stop is a four-dice version of Pig Dice. A player's turn consists of multiple rounds of rolling the dice and moving markers. A player may roll and move until she chooses to pass her turn; however, if a dice roll results in no legal moves, the player has to go back to her position at the beginning of the turn. Thus, the key aspect of the game is knowing when to pass the dice and when to keep rolling.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/41
Key CS Concepts:
  • Two-dimensional arrays (with columns of different lengths)
  • Probability
Interesting pedagogical aspects:

Writing an algorithm to enumarate the unique ways to divide 4 dice into two pair should be an interesting and challenging problem for CS 1 students.

The optimal strategy for this game can be analyzed at many different levels of complexity. The simple analysis is "what is my expected change in position if I push my luck and roll the dice?"; however, this analysis doesn't account for the probability of another player winning before the current player gets another turn. Thus, this project provides a good opportunity for a friendly competition among students to program the best playing strategy. (See the Pig Dice web page for more details.)


Ricochet Robot
Description:
The game consists of a set of robots that move about on a rectangular grid. The grid contains some walls and some target squares. The goal of each round is to direct a specified robot to a specified target using as few changes of direction as possible. The challenge is that the robots can only stop and/or change direction when they hit something. Thus, finding an efficient route can be challenging.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/51
Key CS Concepts:
  • Two dimensional arrays
  • breadth-first/depth-first search
  • File I/O
Interesting pedagogical aspects:
  • Both CS 1 and some CS 2 students will be challenged by the algorithm to move a robot along a row or column until it hits a wall or another robot.
  • Writing a solver for this game would be an excellent breadth-first or depth-first search-based project.
  • The board game comes in four separate square pieces (the four quadrants of the board). Each piece has two sides, and the four pieces can be arranged in any order. Thus, there are 96 different boards. The process of reading in four of eight different boards from four separate files, then combining the four quadrants into a single board would be an interesting and challenging CS 2 exercise.


Metro
Description:
Players fill a grid with tiles representing subway tunnels. The goal is for players to take turns laying tunnel segments in a way that maximizes the lengths of the subway lines they control and minimizes the lengths of their opponents' lines.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/559
Key CS Concepts:
  • Two dimensional arrays
  • "link-chasing" in an array
Interesting pedagogical aspects:
The most interesting aspect of this game from a programming standpoint is to trace the paths of the tunnels around a two-dimensional array.
Notes:
According to the rules, each player can keep one tile secret for use when deemed appropriate; however, the game plays reasonably well even if the player must immediately play the tile drawn on his or her turn.


Ta Yu
Description:
Players fill a grid with tiles representing pipes. The goal is to lay the tiles so as to connect one's own pipes while blocking others' pipes.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/117
Key CS Concepts:
  • two dimensional arrays
  • "link-chasing" in an array
Interesting pedagogical aspects:
The most interesting aspect of this game from a programming standpoint is to verify that a tile to be laid legally connects with its neighbors. (In contrast, Metro tiles are designed so they always connect legally to their neighbors.)
Notes:
According to the rules, each player can keep one tile secret for use when deemed appropriate; however, the game should play reasonably well if the player must immediately play the tile drawn on his or her turn.


Rush Hour
Description:
This is technically a puzzle, not a game. The board consists of a 6x6 grid of squares filled with up to 16 vehicles. The vehicles are 1x2 or 1x3 and may only move forward or backward. The challenge is to find a sequence of moves that allows the red car to drive through an exit.
Key CS Concepts:
  • two dimensional arrays
  • breadth/depth-first search
Interesting pedagogical aspects:
A project based on Rush Hour would be primarily an exercise in array manipulation and GUI design. Finding the optimal solution to a given puzzle may make for a good algorithms project.


Chekov
Description:
The game is played on a 6x6 grid. Players roll 3 dice, then choose two dice to "claim" a space on the grid (e.g., if the player rolls 2, 3, and 3, he or she may choose to claim the squares labeled 23, 32, or 33). The goal is to acquire long sequences (rows, columns, diagonals) of "claims".
Board Game Geek URL:
http://boardgamegeek.com/boardgame/7465
Key CS Concepts:
  • two dimensional arrays
Interesting pedagogical aspects:
The main challenges are (1) presenting all the valid two-dice combinations from the roll, and (2) identifying a player's sequences of claims.


Carcassonne
Description:
Players lay randomly chosen tiles to build a medieval landscape. As they lay tiles, the players must allocate a limited number of followers to claim the land.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/822
Key CS Concepts:
  • two dimensional arrays
  • inheritance
Notes:
This appears to be one of the more complex games, and one of the most challenging to program. There are many expansions and spin-offs of this game.


Khet
Description:
Khet is a chess-like game where players move pieces containing mirrors around the board with the goal of deflecting a laser onto the opponent's king.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/16991
Key CS Concepts:
  • two dimensional arrays
  • walking through an array
Interesting pedagogical aspects:
The main programming challenges are (1) tracing the path of the laser, and (2) developing a design that effectively keeps track of which way the mirrors point. It may also be a good candidate for an "AI" challenge.


Kupferkessel Co. ("Copper Kettle")
Description:
In this game, the player's piece walks around the outside of a grid of cards, then chooses a card from the row or column on which it lands. Players attempt to collect complete sets of ingredient cards.
Board Game Geek URL:
http://boardgamegeek.com/boardgame/2533
Key CS Concepts:
  • two dimensional arrays
  • walking through an array
  • scoring cards into piles and identifying missing cards from each pile
Interesting pedagogical aspects:
  • writing ellegant, concise code to move the pieces around the edge
  • calculating the score at the end of the game.


Anticipated Reviewer Questions

Below is the complete list of questions I expect to receive from those who review my proposed SIGCSE workshop. Space constraints prevent me from addressing each question directly in the proposal.

There are already hundreds of fun programming projects. Why do we need a workshop to show us more?
Those of us who love teaching CS 1 and CS 2 can never have too many project ideas. (1) The bigger my "library" of ideas gets, the better I get at choosing projects that match both the course curriculum and my personal teaching style. (2) In order to reduce cheating, we at GVSU avoid re-using projects. Thus, we're always looking for new ideas.

How will this workshop differ from the Nifty Assignments panel?
The Nifty Assignments panel selects for presentation assignments that have "high-quality," prepared materials that are "tested and ready to go." In contrast, our goal is to bring some games that are not well known in America to the attention of instructors who can then go out and prepare new projects (possibly for presentation at future Nifty Assignment sessions).

Isn't this just a brainstoming session?
A significant part of this workshop will be brainstorming. That brainstorming will help us all learn how to better identify and avoid aspects of a game that would needlessly complicate a project.

What will we learn about CS pedagogy by taking this workshop?
This focus of this workshop is not pedagogy; it is helping instructors develop self-contained, engaging projects that will help the students exercise programming skills they have been recently taught.

Rigor-wise, isn't this a little lightweight for a workshop?
There will certainly be more rigorous workshops; however, I believe the opportunity to brainstorm modifications provides sufficient rigor. In addition, it is appropriate for people to take time and have fun at a conference --- especially if they can learn something useful in the process. I believe the element of fun is what will fill the workshop.

Have you used these games in your classes?
I have used Igel Argern and Metro as CS 2 projects.

How big are these projects?
I use these games as the bases of six-week CS 2 projects. However, instructors who desire smaller projects need only provide libraries for the code that is not relevant to the key topic. (For example, provide a library containing the GUI and have the students code the logic.) Some of the participants may suggest features that they think will make especially interesting two-week projects.

Can you really learn and play a new game in an hour?
Each of the games listed above can reasonably be learned and played in 75 minutes.

Do you have the students write "AI" for the programs?
I have not because I haven't made enough time in my course; but I think it's a great idea. For each of the games discussed, the obvious greedy algorithm would be a reasonable programming project and would also be moderately competitive. Motivated students could then compete to see who could produce the best computer player. (I have never formally studied AI, so I don't know if any of these games would make for a good AI course project.)