Problem Set 4: Memory Scramble

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. For example:

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 ::= "\r"? "\n"

In BOARD_FILE, 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↵
🦄↵
🦄↵
🌈↵
🌈↵
🌈↵
🦄↵
🌈↵
🦄↵
🌈↵

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:

1

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.

2

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.

3

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.

Complete rules

First card: a player tries to turn over a first card by identifying a space on the board…

1-A

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.

1-B

If the card is face down, it turns face up (all players can now see it) and the player controls that card.

1-C

If the card is already face up, but not controlled by another player, then it remains face up, and the player controls the card.

1-D

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…

2-A

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

2-B

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:

2-C

If it is face down, it turns face up.

2-D

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

2-E

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:

3-A

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.

3-B

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.

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 ::= "\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.

For example:

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

GET /look/player

The server responds with the current board.

GET /flip/player/row,column

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. They may send concurrent GET /look/... requests.

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 web.mit.edu server here: the web page is running JavaScript in your browser that talks directly with your game server.

(If your browser refuses to connect: make sure you have not removed the lines from WebServer.ts that set the Access-Control-Allow-Origin header, which declares to the browser that this is a legal cross-origin request.)

Revise Board to make it asynchronous, updating other ADTs as needed.

Consider using 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:

• the 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

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

Review your web server to make sure it is using the asynchronous Board properly, according to the rules.

Your server should not busy-wait or hang. While one request is blocked, other requests must be handled normally.

Notice as well that when a WebServer is constructed, the board may be shared with other clients of that same Board instance. If a 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 (for example, don’t give WebServer any rep invariants that external mutation of the Board could break).

Manual testing

Don’t rely on manual testing, or on using simulation.ts, to build a correct system. Each ADT should have a Mocha unit test suite constructed with a principled testing strategy; and careful design to ensure mutual exclusion for critical sections.

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 mocha test file — manual web server tests belong in WebServerTest.ts — 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:

1. 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).
2. Our game protocol violates the spec of HTTP ( ! ) by using GET for the /flip/... request: a GET operation should only be an observer, never a mutator! That requirement allows browsers to e.g. preload GET requests 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.
3. 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 curl. 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 curl.

But much better than manual testing is writing as many automated tests as possible, following the pattern of WebServerTest.ts.