Tetris Project -- Instructor's Guide

This is the meta description of the Stanford tetris project from the instructor point of view.

This tetris project was presented as the Nifty Assignments Panel at SIG-CSE 2001, and the project materials now live at http://cslibrary.stanford.edu/112/. The project is made of Piece and Board classes that implement the core of the tetris game, a JTetris class (provided) that manages the game and does the animation, and Brain classes that add in game playing AI.

Assignment Niche

Tetris is an advanced CS2 assignment. Putting the Piece, Board, and Brain systems all together creates something larger than the typical CS2 assignment, and some of the algorithms are tricky to get right. The complexity makes for a more convincing demonstration of the benefits of a modular OOP design. From a teaching point of view, the main theme of the assignment is using OOP decomposition to divide a complex system into more manageable pieces.

We require the students to have separate test code for both Piece and Board before the two are used in the full tetris. Partly this is just an excuse to teach them about modular test code, and partly because it really is the best way to get the whole thing to work. The project is too big to debug all at once.

Engineering issues aside, tetris is at its heart a fun and visually engaging project. The brain and adversary features add novelty and further ways to play with the system. It's the sort of assignment that the students play with for hours after the required functionality has been done. (Unless their Board doesn't quite work -- nothing sucks the fun out of game of tetris quicker than a board that, say, doesn't do row clearing right.)

I see tetris being used in a CS2 course or later to show off OOP decomposition on a large project. Programming maturity is required to code and debug the algorithms. The students probably should get 2 or 3 weeks to complete the project, and it should be due in stages, which fits well with its modular theme.

Strengths and Weaknesses

The best feature of the assignment is that it attacks some real complexity with OOP decomposition. It also builds something visual and fun that the students really enjoy playing with. The bad part of the assignment is that it is large, and some of the algorithms are tricky. This can be very frustrating for the students if they don't have the skills to deal with that scale of program yet. It also means that it's going to take 2 or 3 weeks out of the term.

Alternative

As an alternative to the full tetris project, the students can just work on their own brain code and load it in to the off-the-shelf JTetris program to try it out. This makes a fun little assignment. Brain code is surprisingly easy to write -- it requires only a basic understanding of Java and OOP. The problem itself is creative and open-ended. There is no right answer; intead the students can code up their heuristic ideas pretty easily and see what they do. The readme has some suggested brain strategies. The LameBrain that ships with the project is extremely simple -- I found that when I shipped a better brain, it seemed to inhibit the students from trying their own. With the LameBrain, it's obvious to the students that they could easily write a better one (or perhaps watching it play poorly is just too offensive to allow to pass without improvement!).

Implementation Variants

The assignment can be given as a non-OOP ADT assignment. There's not really any inheritance going on -- I've given a verison of this assignment in Pascal with Piece and Board ADTs.
The undo algorithm and interface could be simplified without compromising the assignment by relaxing the constraint that the Board and its undo system be so efficient. In particular, implement undo just by copying the whole board instead of the efficient/stingy strategy. In this way, the client can just copy the board before making changes. This is slower since it copies more, and in Java, it will tend to introduce memory churn in the algorithm, where the stingy strategy never calls new after the initial allocation.
The undo algorithm could work without any copying, but instead by remembering the piece and location of the last play, and then backing it out block by block. Row clearing would have to be handled separately.
The board could use something other than a 2-d array as its internal representation. I suspect storing each column as a single 32 bit int and using a bit to represent a block would run faster. Another idea is to store the booleans in a 1-d array and do the offset arithmetic explicitly intead of using a 2-d array.