Problem Set 4: Memory Scramble
The deadlines for this problem set are shown on the course calendar.
Pay attention to the PS4 instructions in the provided code.
You must satisfy the provided specifications for certain functions in
You may rewrite or delete any of the other provided code, add new classes and methods, etc.
On this problem set, unlike previous problem sets, we will not be running your tests against any other implementations.
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.
Ask Didit to create a remote
psets/ps4repository for you on github.mit.edu.
npm install, then open in Visual Studio Code. See Problem Set 0 for if you need a refresher on how to create, clone, or set up 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.
When you’re done with problems 1-2, you can play Memory Scramble in your browser.
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: make your
Board or other ADTs use synchronous methods, and don’t worry about 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.
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).
BOARD_FILE ::= ROW "x" COLUMN NEWLINE (CARD NEWLINE)+ CARD ::= [^\s\n\r]+ ROW ::= INT COLUMN ::= INT INT ::= [0-9]+ NEWLINE ::= "\r"? "\n"
3x3↵ 🦄↵ 🦄↵ 🌈↵ 🌈↵ 🌈↵ 🦄↵ 🌈↵ 🦄↵ 🌈↵
- When a player turns over a first card in a pair, they control that card; but if someone else already controls it, the player blocks 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.
- 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.
- 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).
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.
To support multiplayer Memory Scramble games over the network, we define a HTTP protocol so the game can be played in a web browser.
Code for the web server is already provided (in
server.ts), but it relies on these provided function specifications in the code for this problem set, which you will have to implement:
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.
BOARD_STATE ::= ROW "x" COLUMN NEWLINE (SPOT NEWLINE)+ SPOT ::= "none" | "down" | "up " CARD | "my " CARD CARD ::= [^\s\n\r]+ ROW ::= INT COLUMN ::= INT INT ::= [0-9]+ NEWLINE ::= "\r"? "\n"
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↵
Iterative development recommendation: implement a synchronous board first (i.e. with no
async methods other than
parseFromFile), and connect it to a server in Problem 2.
The alpha grading will focus more on playing the game without concurrency.
Then revise for correct behavior with concurrent players in Problem 3.
fs.promises.readFile()reads a file asynchronously. Be sure to use the promise-based version of this function (indicated by
.promises.), rather than the older callback-function-based API.
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.
In order to connect your
Board type to the provided web server, and also to the Didit autograder, you need to implement the functions in
commands.ts so that they use operations of
Board. Start with these two functions, which are sufficient to play the game:
At this point, your
flip may not yet implement correct blocking behavior according to the rules or be able to handle concurrent players, but they should be able to handle multiple clients that make moves in sequence.
In general, keep all the functions in
commands.ts extremely simple.
They should be no more than glue code, calling at most a couple of your
Board operations, without any additional logic.
- The body of each function should be at most 3 lines long, consisting of at most a couple simple function calls, possibly using local variables, plus a
- All of the functions that they call should be already well-tested, either by your
Boardtest suite or by TypeScript itself.
If any of your
commands functions is more complex than that — for example, with control flow statements like
while, or string-processing operations — then you will need to create
test/commandsTest.ts and design a test suite for it.
Before you do that, stop!
First discuss your design with course staff, because this is a sign that the operations you chose for your
Board type are not powerful enough.
The specs for
flipare given, but you may strengthen them if you want.
- Test. Keep these operations extremely simple so you don’t have to test them separately.
flipas simply as possible.
To start the server, use
npm start, which runs
This code parses command-line arguments, calls the
Board parsing function based on those arguments, and creates and starts a server.
You should not need to change
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 to stop it.
In the textbox on the client page, 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
await on a promise returned by the board to implement blocking according to the rules.
Refer to “making and keeping a promise” in Mutual Exclusion for discussion of:
new Promise(..)constructor, which is most useful for transforming callbacks into promises
- the specification and implementation of
Deferred, which is most useful for storing promises to be resolved later
simulation.ts, increase the value of
players to simulate multi-player Memory Scramble games.
By instrumenting your code, for example with
console.log() 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.
Consider revising your testing strategy to test different interleavings of concurrent player actions.
You may find the
timeout() function useful for forcing short waits.
Very short timeouts (1 or even 0 milliseconds) give up control long enough for concurrent actions to run to completion.
Avoid waiting for hundreds of milliseonds, because this may cause your tests to timeout on Didit.
Do not put
timeout() calls in your implementation code; this is a sign that your design has a race condition.
commands.ts file to make sure it is using the asynchronous
Board properly, according to the rules.
Your commands should not busy-wait or hang.
While one request is blocked, other requests must be handled normally.
This problem adds one more command to the protocol,
map command is independent of other state of the game.
So it doesn’t matter whether a card is face up or face down, or whether it is controlled by another player, it can still be replaced, and its face-up/face-down and control state is unaffected by the replacement.
The transformer function
f is asynchronous (returning a promise), so it might be implemented in a variety of ways (e.g. doing a database lookup, accessing a language translation web API, even asking a human user what the replacement card should be).
This means that
map may have to wait for its calls to
f to complete.
map must not block other commands on the board from interleaving with it while it is running (including other commands issued by the same player).
Other operations may see partially-transformed boards (with some cards replaced but not others), but the board must remain consistent to players in the sense that if two cards on the board match each other before
map is called, then it must not be possible to observe a board state in which that pair of cards do not match.
Specify, test, and implement support in your board ADT that will enable you to implement the
map() function in
commands.ts as simple glue code that requires no testing of its own.
This problem adds one more command to the protocol,
watch() call 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.
watch(board, player) request is blocked, the player may use other commands on the same board, and they will be processed normally.
For example, a concurrent
look(board, player) request must not block.
Specify, test, and implement support in your board ADT that will enable you to implement watching the board for changes. 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 an asynchronous method whose promise fulfills when the board changes.
- Listeners might provide a callback function to
Board. The board will call them back on each change.
Then use your change notifications to specify, test, and implement the
watch() function in
commands.ts as simple glue code that requires no testing of its own.
Note that you decide which changes are atomic.
For example, the
watch 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.
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:
@inheritdocwhen a class implements an interface method, to remind readers where they can find the spec.
- 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, it’s okay if the Didit build finishes after the deadline, because the commit-and-push was on time.
- Passing the public 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.
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.