Problem Set 4: Memory Scramble
- Alpha due
- Wednesday, April 28, 2021, 10:00 pm US Eastern time
- Code reviews due
- Sunday, May 2, 2021, 2:00 pm US Eastern time
- Beta due
- Wednesday, May 5, 2021, 10:00 pm US Eastern time
The purpose of this problem set is to explore multithreaded programming with a shared mutable data type, which you will protect using different thread safety strategies; and to practice writing a client/server system.
On this problem set, you have substantial design freedom.
Pay attention to the PS4 instructions in the provided code.
You must satisfy the provided specifications for certain methods in
WebServer, and you should not change the code in
You may rewrite or delete any of the other provided code, add new classes and methods, etc.
Take care that the coordinate system of your game board matches the specifications: (row, column) coordinates start at (0, 0) in the top left corner, increasing vertically downwards and horizontally to the right.
Your code will be tested against the HTTP protocol specified below. It is your responsibility to examine Didit feedback and make sure your code compiles and runs for grading, but you must do your own testing to ensure correctness.
Get the code
Ask Didit to create a remote
psets/ps4repository for you on github.mit.edu.
Clone the repo. Find the
git clonecommand at the top of your Didit assignment page, copy it entirely, paste it into your terminal, and run it.
Import into Eclipse. See Problem Set 0 for if you need a refresher on how to create, clone, or import your repository.
On this problem set, you will build a networked multiplayer version of Memory, a.k.a. Concentration, the game in which you turn over face-down cards and try to find matching pairs. Our version will have players turning over cards simultaneously, rather than taking turns. We’ll call it Memory Scramble.
Problem 1: you will design and implement one or more ADTs for this game, without thread safety.
Problem 2: you will implement a game server that handles a single client at a time using HTTP.
Problem 3: you will revise your system to handle multiple simultaneous clients using a threadsafe game board.
When you’re done problems 1-3, you can play Memory Scramble in your browser.
Optional Problem 4: optionally, you can design and implement watching for changes to the board, which makes the Memory Scramble user interface more responsive. This part is completely optional – there is no grading attached to it at all.
Iterative Development Recommendation
Both automatic and manual grading for the alpha will focus more on your board and server without concurrency.
First, do problems 1 & 2 without considering concurrency: don’t make your
Board or other ADTs threadsafe, and don’t handle multiple concurrent players in your server.
Implement the gameplay rules specified below by writing tests, choosing data structures, and writing code.
Consider the abstraction functions and rep invariants of all your data types.
Then, revise your work in problem 3 to make your system safe for concurrency. Revise your choice of ADT operations based on the need for atomic actions, revise your implementation using threadsafe data structures and a technique for blocking calls, and write your thread safety arguments.
Game board · Gameplay rules · Example game transcript · Playing on the web
The Memory Scramble game board has a grid of spaces. Each space starts with a card. As cards are matched and removed, spaces become empty.
A card in our game is a non-empty string of non-whitespace non-newline characters.
This allows “pictures” like
Hello and pictures like 🌈 by using emoji characters.
All cards start face down. Players will turn them face up, and the cards will either turn face down again (if the player turned over cards that don’t match) or be removed from the board (if they do match).
Game boards are loaded from a file. Here is the formal grammar for board files:
BOARD_FILE ::= ROW "x" COLUMN NEWLINE (CARD NEWLINE)+ CARD ::= [^\s\n\r]+ ROW ::= INT COLUMN ::= INT INT ::= [0-9]+ NEWLINE ::= "\n" | "\r" "\n"?
ROW is the number of rows,
COLUMN is the number of columns, and the cards are listed reading across each row, starting with the top row.
… would be specified in a file as:
3x3↵ 🦄↵ 🦄↵ 🌈↵ 🌈↵ 🌈↵ 🦄↵ 🌈↵ 🦄↵ 🌈↵
In this example,
A valid board file must have exactly
Multiple players manipulate the cards on the board concurrently. They play the game by trying to turn over pairs of identical cards. In a competitive game, those matching pairs would be worth points, but score-keeping is not part of our game for this problem set.
Here’s an informal summary of the rules:
- When a player turns over a first card in a pair, they control that card. If someone else already controls it, they block until they can take control.
- When the player turns over a second card, if the cards match, the player keeps control of them; otherwise, the player gives up control. The cards stay face up for now.
- When the player makes their next move, if their previous cards matched, those cards are removed from the board; otherwise, if no one controls them, they turn face down.
Notice at least two differences from usual Memory game rules: you can “turn over” a card that is already face up, blocking until that card is available; and turned-over cards stay face up on the board until the player who turned them over makes another move.
First card: a player tries to turn over a first card by identifying a space on the board…
- If there is no card there (the player identified an empty space, perhaps because the card was just removed by another player), the operation fails.
- If the card is face down, it turns face up (all players can now see it) and the player controls that card.
- If the card is already face up, but not controlled by another player, then it remains face up, and the player controls the card.
- And if the card is face up and controlled by another player, the operation blocks. The player will contend with other players to take control of the card at the next opportunity.
Second card: once a player has turned over a first card, they can try to turn over a second card…
- If there is no card there, the operation fails. The player also relinquishes control of their first card (but it remains face up for now).
- If the card is face up and controlled by a player (another player or themselves), the operation fails. To avoid deadlocks, the operation does not block. The player also relinquishes control of their first card (but it remains face up for now).
- If the card is face down, or if the card is face up but not controlled by a player, then:
- If it is face down, it turns face up.
- If the two cards are the same, that’s a successful match! The player keeps control of both cards (and they remain face up on the board for now).
- If they are not the same, the player relinquishes control of both cards (again, they remain face up for now).
While one player is blocked turning over a first card, other players continue to play normally. They are not blocked, unless they also try to turn over a first card controlled by another player.
Failure in 1-A, 2-A, and 2-B only means that the player fails to control a card (and in 2-A/B, also relinquishes control). The player continues in the game.
After trying to turn over a second card, successfully or not, the player will try again to turn over a first card. When they do that, before following the rules above, they finish their previous play:
- If they had turned over a matching pair, they control both cards. Now, those cards are removed from the board, and they relinquish control of them. Score-keeping is not specified as part of the game.
- Otherwise, they had turned over one or two non-matching cards, and relinquished control but left them face up on the board. Now, for each of those card(s), if the card is still on the board, currently face up, and currently not controlled by another player, the card is turned face down.
If the player never tries to turn over a new first card, then the steps of 3-A/B never occur.
Example game transcript
Playing on the web
To support multiplayer Memory Scramble games over the network, we’ll define a HTTP protocol so the game can be played in a web browser.
The protocol uses standard HTTP, which means every communication is a client request with a server response.
All of our client requests will be
GET requests for a particular path, and all server responses will be plain text.
In the protocol, each player identifies themselves by an ID, a nonempty string of alphanumeric or underscore characters of their choice. All requests with the same player ID are the actions of a single player.
Here is the formal grammar for requests and responses:
REQUEST ::= "/look/" PLAYER | "/flip/" PLAYER "/" ROW "," COLUMN RESPONSE ::= BOARD BOARD ::= ROW "x" COLUMN NEWLINE (SPOT NEWLINE)+ PLAYER ::= [\w]+ SPOT ::= "none" | "down" | "up " CARD | "my " CARD CARD ::= [^\s\n\r]+ ROW ::= INT COLUMN ::= INT INT ::= [0-9]+ NEWLINE ::= "\n" | "\r" "\n"?
Rows and columns on the board are indexed starting from 0 at the top left.
For all requests, the server responds with
BOARD, the current board.
In the response,
ROW is the number of rows,
COLUMN is the number of columns, and the cards are listed reading across each row, starting with the top row.
none indicates no card in that location,
down is a face-down card,
up is a face-up card controlled by another player (or by no one), and
my is a face-up card controlled by the player who sent the request.
3x3↵ up␣A↵ down↵ down↵ none↵ my␣B↵ none↵ down↵ down↵ up␣C↵
In this example
There are no cards at (1,0) or (1,2).
The cards at (0,0), (1,1) and (2,2) are face up, and the player receiving this message controls the
The server responds with the current board.
The server tries to flip over the card at
(row, column) for the player, following the rules above, and responds with the current board after trying to flip.
Since the response is sent after the flip, this request may block waiting for another player to relinquish control of a card.
A player waiting for a blocked flip to complete may not send concurrent
GET /flip/... requests until the blocked flip has completed.
Problem 1: Game board
Specify, test, and implement a mutable
Board ADT to represent the Memory Scramble game board.
It may be useful to define other ADTs as well.
Board.java defines a static factory method for creating new boards that you must support:
parseFromFile(filename): creates a board by parsing a file in the format described above
Remember to include: a specification for every class and every method you write; abstraction functions and rep invariants, and
toString; and safety from rep exposure arguments.
Iterative development recommendation: implement a single-threaded board first, and connect it to a server in Problem 2. The alpha grading will focus more on using your server without concurrency. Then revise for thread safety and correct behavior with concurrent players in Problem 3.
For parsing board files, a parser generator (like ParserLib) is more complexity than you need. To read the board files, there are at least three Java APIs to consider:
FileReaderis the standard class for reading from a file. Wrapping the
BufferedReaderallows you to use the convenient
readLine()method to read whole lines at a time.
The utility function
Files.readAllLines(..)will read all the lines from a
toPath()method). If you want to program in a functional style,
Scanneris designed for breaking up input text into pieces. It provides many features and you’ll need to read its specs carefully.
To keep track of players and their state:
Each player might simply be identified by the ID it uses in the wire protocol. All of the game state would be stored in the
Each player might be represented using an ADT, e.g.
Player. Some of the player’s state might be stored in the
Playerobject, or the
Boardmight store all the state.
You decide which actions are atomic, since the rules do not specify. In rule 3-B, for example, turning the two cards back over might be a single action — where no other player can see or manipulate the intermediate board — or two separate actions. But the board must never reach an inconsistent state, such as two players controlling the same card, or having a face-down card that a player still controls.
To implement control of cards according to the gameplay rules,
synchronized blocks are not enough.
The player controlling a card can’t just be implemented by a thread holding a lock in a
You will need to track who controls which cards in a different (but still threadsafe) way.
To implement blocking according to the gameplay rules,
synchronized blocks alone are not enough:
Threads might wait for a message from a blocking queue.
You might use
wait()(to block) and
notifyAll()(to wake up blocked threads). These calls must be inside a
waitrelinquishes the lock before it blocks. When waiting threads wake up, only one will win the race for the lock, similar to how only one waiting consumer can take a single message from a blocking queue.
wait()must be used in a condition-checking loop. See, e.g., Guarded Blocks in The Java Tutorials for an example.
Or you might use another tool from the
When a player is waiting, the thread must be blocked waiting for an event, it must not be busy-waiting (see the Reordering example in Concurrency).
For keeping track of which players control cards, or matched (or mismatched) pairs that need to be removed (or turned face down), threadsafe data structures may be useful:
ConcurrentHashMapoffers atomic operations like
java.util.concurrent.atomicpackage provides mutable references with atomic operations like
Simulating a game
SimulationMain.java we have provided skeleton code for a program that simulates one player interacting with a board, randomly flipping over several cards.
You should be able to fill in the blanks in that
main() method and run simulated single-player Memory Scramble games.
Problem 2: Web server
To implement the web server, we will use the
com.sun.net.httpserver HTTP server library provided as part of the JDK.
WebServer.java we have provided skeleton code for a web game server:
WebServerconstructor creates a
HttpServerand sets it to handle concurrent requests by automatically creating and reusing multiple threads (
- The constructor has an example of attaching a handler for requests to paths that begin with the prefix
/hello/. The handler receives a
HttpExchangeobject that represents a single client/server request/response. The handler callback will run on a background thread, not the main thread. Since the server handles concurrent requests on multiple threads, multiple threads may be running various callbacks concurrently.
- The example handler calls the private method
handleHello(), which demonstrates how to use the
HttpExchangeto examine the request and send a response. If
handleHellowere to block, the client would be blocked waiting to read the response.
- The constructor also adds a pair of filters to the
loglogs every request to stderr, and
headersadds required HTTP headers. You should add those filters to all your handlers.
- Requests for
/hello/are not part of the game protocol, and you should replace the example code once you understand it.
In the provided
testHelloValidtests the behavior of the provided server on the valid request
testHelloInvalidtests its behavior on invalid request
To see the example code running, use
This provided class parses command-line arguments, calls one of the static
Board creators based on those arguments, and creates and starts a server.
You should not need to change any of this code.
ServerMain on the command line, first
cd to your
Then start a web server on port 8080 with our 3×3 board of rainbows and unicorns:
java -ea -cp bin memory.ServerMain 8080 boards/perfect.txt
WebServer doesn’t use the game board yet, but we can try out the handler for
http://localhost:8080/hello/world→ valid request,
http://localhost:8080/hello/%F0%9F%8C%8D→ invalid request,
Go away, 🌍.
Remember that the server keeps running until you terminate its process, and if you try to run a second server on the same port, it will fail with “address already in use”.
If you run the server on the command line, use
C in that terminal.
If you run the server in Eclipse, click the double-gray-X button to close consoles for terminated programs, then click the stop button.
Specify, test, and implement support for
/flip/player/row,column requests according to the HTTP game protocol.
WebServer, the specifications of the constructor,
stop() are required, but you are free to change any of the code in this class.
At this point, your
WebServer may not implement correct blocking behavior according to the rules or be able to handle concurrent players or concurrent requests from the same player, but it should be able to handle multiple clients that make moves in sequence.
Make sure your
WebServer has: complete specifications; abstraction function, rep invariant, and
checkRep; and safety from rep exposure argument.
Problem 3: Revise for concurrent players
Board to make it threadsafe, updating other ADTs as needed.
Make sure it has a clear, complete thread safety argument.
See How to make a thread safety argument, including with synchronization and with message passing.
SimulationMain.java, increase the value of
players to simulate multi-player Memory Scramble games.
By instrumenting your code, for example with
println statements or by keeping track of cards that different players flip over, you should observe correct control of cards, correct blocking when players try to flip over a first card, and correct removal of matching cards when players make a next move.
Notice that your simulation should not terminate if one player turns over matching cards in their last move (leaving two cards face up under that player’s control) and another player tries to flip one of them as their first card. In Eclipse, click the stop button to terminate the program.
WebServer so it can handle multiple concurrent players according to the rules.
While one request is blocked, other requests must be handled normally.
In the provided code,
handles each request on a separate thread to achieve this.
WebServer has a clear, complete thread safety argument.
WebServer does not need to be a threadsafe type (it may only be safe to call the public methods of a
WebServer instance from one thread).
But it must document why it is safe for
WebServer to call back its own request handlers from multiple internal threads handling concurrent HTTP requests.
Notice as well that when a
WebServer is constructed, the board may be shared with other clients of that same
Board is being served, for example, by two different web servers, players on those two servers are all playing together.
This sharing of a mutable
Board is a documented and desired part of the spec, and you must ensure it does not create rep exposure.
Don’t rely on manual testing, or on using
SimulationMain.java, to build a correct system.
Each ADT should have a JUnit test suite constructed with a principled testing strategy; and a clear, complete thread safety argument.
However, if there are specifications you are not sure how to test automatically, you can document manual tests that cover parts of some partitions.
Document these tests in the relevant JUnit test file — manual
WebServer tests belong in
WebServerTest.java — immediately below the testing strategy.
For each manual test: give it a descriptive name, list the parts covered, and briefly but precisely describe each step a human tester should follow, along with assertions about expected results at each step.
For example, imagine you are testing the MIT web site:
/* * Manual test: navigate to academic calendar * Covers: page=home, type=static, type=redirect, data-source=registrar * 1. browse to http://web.mit.edu => assert that header contains today's date * 2. click "education" * 3. click "academic calendar" => assert that page shows previous June through next June */
Follow the same guidelines as for automated tests: test first, design a small set of tests, keep each test short, and make sure the tests are testing the spec.
A few enormous caveats about manual testing of our game protocol in a web browser:
- Browsers cache pages you visit (so revisiting a URL doesn’t always fetch it again from the server) and they preload URLs you might visit (so a page might be fetched before you hit enter in the URL bar).
- Our game protocol violates the spec of HTTP ( ! ) by using
GEToperation should only be an observer, never a mutator! That requirement allows browsers to e.g. preload
GETrequests without worrying about mutating data on the server. Since we’ve violated HTTP spec (to keep things simple for this pset), beware that your browser may pre- or re-request
/flip/...URLs when you manually visit them. So your browser may make a flip request that you didn’t intend, or before you intended it.
- Chrome has been seen to behave in surprising ways when multiple tabs are blocking waiting for the same server to respond; some tabs never unblock, even when the server finally sends a response.
For these reasons, if you choose to do some manual testing, you may want to forgo your browser and instead use a command-line HTTP client like
You should already have
curl installed in the command prompt where you use
git, since the GitStream exercises you did at the start of the semester also use
But much better than manual testing is writing as many automated tests as possible, following the pattern of
Once your server is complete, you can play the game online! We’ve built a client web page that speaks the game protocol with your server:
Play Memory Scramble
Enter the address of your running server (the default is
localhost:8080), or connect to a friend’s server by IP address.
There is no code running on the
(optional) Problem 4: Board events
This part of the problem set is optional. It makes the Memory Scramble user interface more responsive to users, and allows you to explore another level of concurrency design. Didit will have autograding tests for this problem, but no points will be associated with them in the alpha or beta submission.
This problem adds one more request,
/watch, to the grammar for server requests:
REQUEST ::= "/look/" PLAYER | "/flip/" PLAYER "/" ROW "," COLUMN | "/watch/" PLAYER
The server does not immediately respond. Instead, this request blocks, and the server waits until the next time the board changes. At that point, it responds with the current board.
A change is defined as any cards turning face up or face down or being removed from the board.
GET /watch/player request must block until such a change occurs.
When there is no change in the state of the cards — for example, if a player tries to turn over an empty space, or if a player takes control or relinquishes control of a card but it does not turn face up or down — pending watch requests must continue to block.
GET /watch/player request is blocked, the player may send other requests, and they will be processed normally.
For example, a concurrent
GET /look/player request must not block.
Specify, test, and implement support for informing clients of the game board ADT about when it has changed. Your board ADT might implement notification of only a single change, or notification of all future changes:
- If the client receives only a single change, it might be a blocking method that returns when the board changes. (This is sufficient to implement the web server, so strongly consider starting with this simple design.)
- Listeners might implement a callback interface specified by
Board, and call a method to add themselves as a listener. The board will call them back on each change.
- Clients might be consumers of a threadsafe queue of events provided by the board. The board puts an event object on the queue for each change.
First try using your change notifications in
SimulationMain.java to watch the board from another thread during a simulated game.
Then use your change notifications to specify, test, and implement support for web server
/watch/player requests, notifying players when the board changes.
In that specification:
- A change is defined as any cards turning face up or face down or being removed from the board.
- When there is no change in the state of the cards — for example, if a player tries to turn over an empty space, or if a player takes control or relinquishes control of a card but it does not turn face up or down — it is not considered a change.
In your web server request handlers, you must call
sendResponseHeaders before the method returns.
If you implement board events with a callback, take care to send the response headers synchronously, not after the callback occurs.
You decide which changes are atomic. The “watch” request specification does not say whether, when a pair of matched (or mismatched) cards is removed (or turned face down), that is reported as a single change or two separate changes.
Make sure to update the internal documentation of
WebServer where needed.
Once you have added
/watch to your server, you can flip the switch in the Memory Scramble web user interface from “update by polling” to “update by watching”, and you should find that the UI is quicker to display board updates made by other clients.
The link below flips the switch automatically:
Play Memory Scramble with
Before you’re done
Make sure you have documented specifications, in the form of properly-formatted Javadoc comments, for all your types and operations.
The spec of every type should include whether it is threadsafe.
Make sure you have documented abstraction functions and representation invariants, in the form of a comment near the field declarations, for all your implementations.
With those comments, also say how the type prevents rep exposure.
Make sure every threadsafe type has a documented thread safety argument that explains why that type is threadsafe.
For every type that creates or uses multiple threads, its thread safety argument must explain why its use of multiple threads is safe.
When you implement blocking behavior, make sure the thread is blocked waiting for an event, not busy-waiting (see the Reordering example in Concurrency).
Make sure you specify, test, and implement
hashCode()for all immutable types.
@Overridewhen you override
@Overridewhen a class implements an interface method, to remind readers where they can find the spec.
Make sure you have a thorough, principled test suite for every type.
This is the last problem set in 6.031: your work should exemplify SFB, ETU, RFC software construction.
Make sure you commit AND push your work by 10:00pm US Eastern time on the deadline date.
⏳ This problem set can take much longer for Didit to process than previous psets, so push early.
Remember that Didit feedback is provided on a best-effort basis:
- There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
- If you commit and push right before the deadline, the Didit build does not have to complete in order for that commit to be graded.
- Passing the public
WebProtocolTesttest on Didit is no guarantee that you will pass the full battery of autograding tests, but failing it is sure to mean many lost points on the problem set.
Your overall ps4 grade will be computed as approximately:
~35% alpha autograde + ~5% alpha manual grade + ~45% beta autograde + ~15% beta manual grade
The autograder test cases will not change from the alpha to the beta, but their point values will. In order to encourage incremental development, alpha autograding will focus primarily on situations where clients make moves in series (separated by time), not concurrently. On the beta, autograding will look at a full range of concurrent situations.
Manual grading of the alpha will only examine internal documentation (AF, RI, testing strategy, etc.) and implementation that does not relate to concurrency. Manual grading of the beta may examine any part, including re-examining those docs or code, and how you addressed code review feedback.