Rock Paper Scissors Lizard Spock

Jim Huggins
Kettering University, Flint, MI
`jhuggins@kettering.edu`

Metadata

Summary	The common game of "rock-paper-scissors" is used as a basis for creating a networked client-server game in a Unix systems programming course.
Topics	Client-server interactions, Unix servers and sockets, basic algorithmic design.
Audience	Sophomore level systems-programming course, but could be easily adapted for a CS1/CS2 environment.
Difficulty	Two weeks (with textbook supplying examples of networking code).
Strengths	Provides a fun application while working on client/server interactions. Can be customized with different choices of gestures, to avoid problems of plagiarism. Can be scaled down to a CS1 or CS2 context. Can be offered in an open-ended context (e.g. determining the protocol to be used).
Weaknesses	The game itself is relatively simple; one might call it "simplistic". Networking code can be notoriously difficult to debug, depending on the environment in use.
Dependencies	Basic CS1 understanding of algorithmic development, strings, game state, and so on; networking knowledge (in whatever form).
Variants	Can be adopted to fewer (or more) gestures, or fewer (or more) throws per game. Problem can be simplified by supplying a functioning client (or server) and requiring students to write the other.

Background

In the childhood game of "rock-paper-scissors" (also known by a variety of other names), two participants select one of three different gestures (or "throws"). The selected gestures are then compared using the following rule set:

Rock defeats (or "breaks") Scissors.
Scissors defeats (or "cuts") Paper.
Paper defeats (or "covers") Rock.

Ties are broken by repeating the game as needed. The game can be played until the first winner is determined, or in repeated rounds (e.g. best two out of three).

Of course, with only three gestures to choose from, the possibility of a tie on any given throw is fairly high, and the possibility of repeated ties (while diminishing) is certainly non-trivial. When competing against an opponent whose tendencies may be known, the possibilities of ties may be even higher. In response, Sam Kass (with help from Karen Bryla) developed an extension of this game by adding two new gestures: "lizard" and "Spock". The full rule set may be expressed as follows:

Rock crushes Lizard and crushes Scissors
Paper disproves Spock and covers Rock
Scissors decapitates Lizard and cuts Paper
Lizard poisons Spock and eats Paper
Spock smashes Scissors and vaporizes Rock

Note that this rule set is a conservative extension of the classic rule set. The rule set still permits a fair game: every gesture defeats two other gestures and loses to two other gestures. And while the possibility of ties still exists, the probability of ties (and, in particular, repeated ties) is lower.

One can purchase T-shirts (from CafePress or ThinkGeek) with graphical depictions of the above rules. The game was also featured in an episode of CBS's The Big Bang Theory.

The Original Assignment

In Winter 2010, I used this assignment in a course in systems programming at Kettering University. The course is taken mostly by sophomores and juniors who have already taken two courses in object-oriented programming (using Java). The course begins with a "crash course" in C programming, and then spends most of the term learning to write programs that interact with the Unix operating system.

One of the last units of the course introduces students to TCP/IP networking and Unix streams. I was interested in providing a final assignment for the students to complete that would involve writing a genuinely networked application. Most of the assignments during the semester had been rather un-nifty (e.g. writing subsets of common Unix utilities); I was hoping to give an assignment that would be more interesting --- or at least more entertaining.

The assignment I gave to the students required students to implement a client-server application for playing Rock-Paper-Scissors-Lizard-Spock. Students were required to write a stand-along server application along with a companion client application. The server accepted requests from clients, pairing them up into two-player games, referee each game, and announce a winner. The server permitted multiple concurrent games. Students were given complete freedom in defining the network protocol used in exchanging information between server and clients, as well as the interface used by the clients to interact with the users.

The course textbook (Molay, Understanding Unix/Linux Programming contained extensive code examples for writing networked TCP/IP applications, which students were free to use in their assignments. This simplified matters greatly; many students simply constructed a library from the code provided by the textbook and accessed the library from their own code.

All students managed to complete the assignment. Many students went above and beyond the required scope of the assignment. One student used the Unix curses library to create an attractive ASCII-oriented client application. Others used innovative ideas for structuring both the client and server for future scalability.

Two student solutions are included for your perusal (with the full permission of the authors):

Why Is This Nifty?

Nifty

Playing games is nifty. Among other things, it makes debugging more entertaining than it might usually be. (And text-based games are nifty, too; they show how you can be entertaining even with the simplest of interfaces.)
T-shirts (from CafePress or ThinkGeek) are nifty.
YouTube videos from sitcoms are nifty. (Licensed videos are even more nifty.)

Topical

The assignment was given as part of a systems programming course, in order to give students an opportunity to construct a genuine networked application. The problem has just enough complexity to give the client and server some work to do (e.g. maintaining game state, forking new game instances) without being overbearing. The networking applications could be easily isolated for use in other platforms. But the assignment could easily be adapted for other courses, depending on need.

CS1: supply the students with a running server, along with a protocol definition, and have them write the client.
CS1: supply the students with a running client and the framework of the server, along with the protocol definition, and have them write the game decision engine (i.e. the part of the code that implements "paper covers rock") as a series of conditional statements.
CS1: have the students write a stand-alone application which pits the user against an automated opponent. (What kind of strategy should the automated opponent use?)
CS1: what happens when you add a third player? What kinds of tie-breaking strategies are needed in that case?
CS2: are there better ways to handle the decision engine? The rule set forms a complete graph, which is amenable to representation as a two-dimensional array. Some students noticed this. One used an array of booleans for representing wins and losses. Another used an array of strings to represent the full result (e.g. "crushes", "is crushed by").
Discrete Math: given five choices, and playing best two-out-of-three, what's the expected number of rounds needed to resolve a game? Or, given n choices and playing best k out of 2k-1, what's the expected number of rounds?
Discrete Math: how much further can the game be generalized? For example, David Lovelace has developed versions of this game with 7, 9, 11, 15, 25, and 101 gestures. Does a fair game exist for any odd number of gestures? If so, how can one be constructed? (I believe this reduces to the problem of finding an Eulerian circuit in the graph ...)

Adoptable

My original writeup and grading rubric are available for your use. Two student solutions (from Phil DeMonaco and Alex Thomson) are also available. Both utilize code from the course textbook (Molay, Understanding Unix/Linux Programming). At the same time, the large number of variations that have been developed (see David Lovelace's site) allow for instructors to select a subset of gestures that may not be easily findable in assignment files (or web searches).