Problem Set 4: Memory Scramble

To get started,

1. Ask Didit to create a remote psets/ps4 repository for you on github.mit.edu.

2. Clone the repo. Find the git clone command at the top of your Didit assignment page, copy it entirely, paste it into your terminal, and run it.

3. 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.

Game board · Gameplay rules · Example game transcript · Playing on the web

Game board

BOARD_FILE ::= ROW "x" COLUMN NEWLINE (CARD NEWLINE)+

CARD ::= [^\s\n\r]+
ROW ::= INT
COLUMN ::= INT
INT ::= [0-9]+
NEWLINE ::= "\n" | "\r" "\n"?

3x3↵
🦄↵
🦄↵
🌈↵
🌈↵
🌈↵
🦄↵
🌈↵
🦄↵
🌈↵

Gameplay rules

Example game transcript

Playing on the web

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"?

3x3↵
up␣A↵
down↵
down↵
none↵
my␣B↵
none↵
down↵
down↵
up␣C↵

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 checkRep and toString; and safety from rep exposure arguments.

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:

• FileReader is the standard class for reading from a file. Wrapping the FileReader in a BufferedReader allows 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 Path (File provides a toPath() method). If you want to program in a functional style, Files.lines(..) returns a Stream<String>.

• Class Scanner is 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 Board.

• Each player might be represented using an ADT, e.g. Player. Some of the player’s state might be stored in the Player object, or the Board might 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 synchronized block. 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 Object methods wait() (to block) and notifyAll() (to wake up blocked threads). These calls must be inside a synchronized block. Calling wait relinquishes 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 java.util.concurrent package.

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:

• ConcurrentHashMap offers atomic operations like putIfAbsent.
• The java.util.concurrent.atomic package provides mutable references with atomic operations like compareAndSet.

Simulating a game

In 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.

To implement the web server, we will use the com.sun.net.httpserver HTTP server library provided as part of the JDK.

In WebServer.java we have provided skeleton code for a web game server:

• The WebServer constructor creates a HttpServer and sets it to handle concurrent requests by automatically creating and reusing multiple threads (Executors.newCachedThreadPool).
• The constructor has an example of attaching a handler for requests to paths that begin with the prefix /hello/. The handler receives a HttpExchange object 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 HttpExchange to examine the request and send a response. If handleHello were to block, the client would be blocked waiting to read the response.
• The constructor also adds a pair of filters to the /hello/ handler: log logs every request to stderr, and headers adds 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 WebServerTest.java file:

• testHelloValid tests the behavior of the provided server on the valid request GET /hello/w0rld.
• testHelloInvalid tests its behavior on invalid request GET /hello/world!.

To see the example code running, use ServerMain.java. 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.

8080 boards/perfect.txt

To run ServerMain on the command line, first cd to your ps4 directory. 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

The WebServer doesn’t use the game board yet, but we can try out the handler for /hello/. Browse to:

• http://localhost:8080/hello/world → valid request, Hello, world!

• 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 Ctrl-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 /look/player and /flip/player/row,column requests according to the HTTP game protocol.

In WebServer, the specifications of the constructor, port(), start(), and 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.

3.1 Threadsafe Board

3.2 Multi-player WebServer

/*
 * 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
 */

Play Memory Scramble

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

GET /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.

A 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.

While a 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.

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 /watch

• 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 equals() and hashCode() for all immutable types.

• Use @Override when you override toString(), equals(), and hashCode().

  Also use @Override when 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 WebProtocolTest test 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.