| Summary | Simple but subtle dice game is a source for many Google-proof assignments. |
| Topics | Simple exercises leading to a nontrivial application for Prolog in a programming language course. Framework critique in an OOD/SE course. Novel and nontrivial loops, lists of sets, data structure reimplementations in CS1/2. |
| Audience | Various—see above. |
| Difficulty | Medium to hard. The algorithms and the framework are more intricate than they look. |
| Strengths | Students get hooked by the game and are then willing to deal with algorithmic and design challenges. |
| Weaknesses | This is not a cookbook project. You will need to spend some time to adapt it to your needs. |
| Dependencies | For the OOD/SE part, or to run the GUI, Java is required. |
| Variants | It is easy to come up with minor variations, making this topic reusable in multiple semesters. |
Flip is a deceptively simple game that you can explain in a few minutes. It can be adapted for a number of different classes. Gentle reader—even though you may only care about CS1/2, please keep an open mind and be inspired by what I did in other courses.
Here are the slides of my flippant presentation.
In my programming languages class at SJSU, I use Prolog as the “mind bending” language. However, minds are not easily bent here, and my students prefer to google before they think. An assignment filled with goodies such as “Write a Prolog predicate that yields the last element in a list” doesn't work in the age of Google.
Prolog lends itself to a whizbang demonstration of game theory. Students are impressed by the fact that a game solver can be as simple as the one-liner
win(X) :- move(X,Y), not win(Y).
As an example, I use the game of Nim, but it just doesn't have the appeal that it had in 1980. To make matters worse, it has a winning strategy involving powers of two, and only quiche-eaters could love that. Then I ran into the game of Flip. Published by Cheapass Games. Instant credibility. I bought bulk dice and let them play in the lab. The game has simple rules but is surprisingly subtle.
If you don't happen to have a partner, practice playing with a (very
stupid) opponent: 
Program doesn't start? Install the latest
version of Java: 
Read the Flip rules first. Pay particular attention to the concept of "playing". Click on your own die to flip, on the opponent's die to "play". If your die got "played", click in the middle to take back what you can before you flip or "play".
What is a state of the game? Your dice, the opponent's dice, and the middle dice. But wait. It's not that simple. The anti-stalemate rule says that you can't flip a die twice until you played, so you need to partition your dice (and the opponent's dice) into flippable and unflippable sets.
Then there is the complexity of the "play" action. If you "play" a die, your opponent gets to take some dice back. We want to carefully separate the decisions of each player. To achieve that, your turn ends immediately when you picked a die to "play", and the opponent's first action is to take dice from the middle. That is, the game state needs to remember the die that was "played".
In summary, the game state consists of
Now the Prolog code gets pretty interesting. First off, how do you represent these sets? With lists of numbers? Lists of symbols? Frequency tables? There are pros and cons to all of them. In Prolog, it can be far more tedious to work with a bad representation than in Java, so it is worth exploring these choices.
Let's pick a simple representation with lists of numbers.
Assignment #1: Implement the flip predicate, where
flip(BF, BN, AF, AN)
is true if your flippable/non-flippable die lists BF/BN are transformed into AF/AN by a flip. That's not too hard. One of the elements of BF must have made it into AN after being flipped.
flip(1,6). flip(2,5). flip(3,4). flip(4,3). flip(5,2). flip(6,1). flip(BF, BN, AF, AN) :- select(X, BF, AF), flip(X, Y), append(BN, [Y], AN).
Ignore all that if you don't know Prolog. The point is that this assignment is (a) interesting for the students and (b) googles incredibly poorly. Try it out—it is heartbreaking.
The students got into it, enumerated all winning positions for Flip with 6 dice, and experimented with various modifications of the rules. It was nifty.
Maybe you don't teach programming languages. But hopefully you have a course in OO design. (If you don't, you really should. Too many students rush through a couple of weeks of design patterns in a software engineering course, and that's not enough. But if that's what you do, this project will work splendidly in such a SE course.)
Most of my students were not all that keen on developing a winning strategy for Flip. Implementing yet another minimax solver and tinkering with alpha-beta pruning wasn't their thing. That's ok. We live in the age of frameworks, and there is much to be learned about OO design by critically examining the design and implementation of a framework. To have credibility with my students, it had to be someone else's framework code—not mine.
I used the game playing framework developed by Mark Cohen (paper | source code). The code is straightforward, and the “interface-based” design fits very well into an OOD course. There is an implementation for a minimax solver, and the framework supplies a text-based UI.
Adding Flip is fairly simple:
As students work with the framework, some questions naturally arise. For
example, is it really a good idea to design interfaces with lots of methods,
all of which have to be implemented by every client? Students will naturally
rediscover the pattern of interfaces and abstract convenience classes that
they encountered in the java.util library. My students only have
a vague recollection of java.util.AbstractList because it solved
someone else's problem, not theirs. (Maybe that is why they are so
disinterested in analyzing frameworks for data structures and streams.)
However, they are quite willing to explore a framework that they perceive as
useful.
After adding the text-based Flip, I was curious whether a GUI version is
possible without modifying the framework. It was straightforward (for me) to
implement the “get next move” functionality. Provide a window
that paints the game state. Implement the IPlayer interface and
make its takeTurn method block until the human player has
provided the necessary mouse clicks. (You will want to give this part to the
students.)
There was just one problem. When the game was over, the game driver used console I/O to announce the result, and to ask whether to play another round. The framework designer had not thought of the possibility of GUI input or network play. It is easy to adapt the framework, and there is a good lesson about the challenges of framework design.
In summary, use Flip as a hook for investigating a game framework. Cohen's game framework is very suitable for an undergraduate OOD course. Flip supplies the niftiness that the bundled TicTacToe inexplicably lacks.
You teach neither programming languages nor OOD? Have no fear. There is plenty of material for your CS1/2 course.
With a good choice of game state, the various methods are just a bit challenging and just a bit off the beaten track; perfect little exercises for the end of CS1 or the beginning of CS2.
If you use this Dice class, then you do not need any collection classes. Alternatively, use Set<Die>. Or do both and contrast them. I supply a simple text-based runner that is independent of the framework. You still want to start out using bulk dice and the GUI runner for motivation. Otherwise, the console interface is too hardcore.
There is a nice opportunity for introducing serious unit testing. Most introductions to unit testing, such as this one, use code that can be easily analyzed by hand, and my students resent the busywork of trivial unit tests. The Flip code is error-prone enough that you can sell unit testing on its merits. Seeing the code “just work” in the runner after it passed the unit tests is pretty nifty. And if that niftiness doesn't materialize, you can still show how failures become the source of new unit tests.
Extra info about this assignment: