Problem Set 4: Multiplayer Minesweeper

We will refer to the board as a grid of squares. Each square is either flagged, dug, or untouched. Each square also either contains a bomb, or does not contain a bomb.

Our variant works very similarly to standard Minesweeper, but with multiple players simultaneously playing on a single board. In both versions, players lose when they try to dig an untouched square that happens to contain a bomb. Whereas a standard Minesweeper game would end at this point, in our version, the game keeps going. The player who dug that square sees a frightening message, but then both they and the other players may continue playing. The square where the bomb was blown up is now a dug square with no bomb.

Note that there are some tricky cases of user-level concurrency. For example, say user A has just modified the game state (i.e. by digging in one or more squares) such that square i,j obviously has a bomb. Meanwhile, user B has not observed the board state since this update has taken place, so user B goes ahead and digs in square i,j. Your program should allow the user to dig in that square — a player of Multiplayer Minesweeper must accept this kind of risk.

We are not defining, or asking you to implement, any kind of “win condition” for the game.

telnet is a utility that allows you to make a direct network connection to a listening server and communicate with it via a terminal interface. Before starting this problem set, please ensure that you have telnet installed. *nix operating systems (including Mac OS X) should have telnet installed by default.

Windows users should first check if telnet is installed by running the command telnet on the command line.

• If you do not have telnet, you can install it via Control Panel → Programs and Features → Turn Windows features on/off → Telnet client. However, this version of telnet may be very hard to use. If it does not show you what you’re typing, you will need to turn on the localecho option.

• A better alternative is PuTTY: download putty.exe. To connect using PuTTY, enter a hostname and port, select Connection type: Raw, and Close window on exit: Never. The last option will prevent the window from disappearing as soon as the server closes its end of the connection.

You can have telnet connect to a host and port (for example, web.mit.edu:80) from the command line with:

telnet web.mit.edu 80 

Since port 80 is usually used for HTTP, we can now make HTTP requests through telnet. If you now type (where ↵ indicates a newline):

GET /↵

telnet should retrieve the HTML for the webpage at web.mit.edu. If you want to connect to your own machine, you can use localhost as the hostname and whatever port your server is listening on. With the default port of 4444 in this problem set, you can connect to your running Minesweeper server with:

telnet localhost 4444

The server may close the network connection at any time, at which point telnet will exit. To close a connection from the client, note the first output printed by telnet when it connects:

Trying 18.9.22.69...
Connected to web.mit.edu.
Escape character is '^]'.

^] means Ctrl-], so press that. Then enter quit to close the connection and exit telnet.

Formal grammar

MESSAGE ::= ( LOOK | DIG | FLAG | DEFLAG | HELP_REQ | BYE ) NEWLINE
LOOK ::= "look"
DIG ::= "dig" SPACE X SPACE Y
FLAG ::= "flag" SPACE X SPACE Y
DEFLAG ::= "deflag" SPACE X SPACE Y
HELP_REQ ::= "help"
BYE ::= "bye"
NEWLINE ::= "\n" | "\r" "\n"?
X ::= INT
Y ::= INT
SPACE ::= " "
INT ::= [0-9]+

Each message starts with a message type and arguments to the message are separated by a single SPACE character and the message ends with a NEWLINE. The NEWLINE can be a single character "\n" or "\r" or the two-character sequence "\r\n", the same definition used by BufferedReader.readLine().

The user can send the following messages to the server:

LOOK message

The message type is the word “look” and there are no arguments.

Example:

l

o

o

k

\n

Returns a BOARD message, a string representation of the board’s state. Does not mutate anything on the server. See the section below on messages from the server to the user for the exact required format of the BOARD message.

DIG message

The message is the word “dig” followed by two arguments, the X and Y coordinates. The type and the two arguments are separated by a single SPACE.

Example:

d

i

g

3

1

0

\r

\n

The dig message has the following properties:

1. If x,y is not a valid coordinate, or square x,y is not in the untouched state, do nothing and return a BOARD message.
2. If square x,y’s state is untouched, change square x,y’s state to dug.
3. If square x,y contains a bomb, change it so that it contains no bomb and send a BOOM message to the user. See again the section below for the exact required format of the BOOM message. Note: When modifying a square from containing a bomb to no longer containing a bomb, make sure that subsequent BOARD messages show updated bomb counts in the adjacent squares. After removing the bomb continue to the next step.
4. If the square x,y has no neighbor squares with bombs, then for each of x,y’s untouched neighbor squares, change said square to dug and repeat this step (not the entire DIG procedure) recursively for said neighbor square unless said neighbor square was already dug before said change.
5. For any DIG message where a BOOM message is not returned, return a BOARD message.

FLAG message

The message type is the word “flag” followed by two arguments the X and Y coordinates. The type and the two arguments are separated by a single SPACE.

Example:

f

l

a

g

1

1

8

\n

The flag message has the following properties:

1. If x,y is a valid coordinate and square x,y is in the untouched state, change it to be in the flagged state.
2. Otherwise, do not mutate any state on the server.
3. For any FLAG message, return a BOARD message.

DEFLAG message

The message type is the word “deflag” followed by two arguments the X and Y coordinates. The type and the two arguments are separated by a single SPACE.

Example:

d

e

f

l

a

g

9

9

\n

The flag message has the following properties:

1. If x,y is a valid coordinate and square x,y is in the flagged state, change it to be in the untouched state.
2. Otherwise, do not mutate any state on the server.
3. For any DEFLAG message, return a BOARD message.

HELP_REQ message

The message type is the word “help” and there are no arguments.

Example:

h

e

l

p

\r

\n

Returns a HELP message (see below). Does not mutate anything on the server.

BYE message

The message type is the word “bye” and there are no arguments.

Example:

b

y

e

\r

\n

Terminates the connection with this client.

Formal grammar

MESSAGE ::= BOARD | BOOM | HELP | HELLO
BOARD ::= LINE+
LINE ::= (SQUARE SPACE)* SQUARE NEWLINE
SQUARE ::= "-" | "F" | COUNT | SPACE
SPACE ::= " "
NEWLINE ::= "\n" | "\r" "\n"?
COUNT ::= [1-8]
BOOM ::= "BOOM!" NEWLINE
HELP ::= [^\r\n]+ NEWLINE
HELLO ::= "Welcome to Minesweeper. Players: " N " including you. Board: "
          X " columns by " Y " rows. Type 'help' for help." NEWLINE
N ::= INT
X ::= INT
Y ::= INT
INT ::= [0-9]+

There are no message types in the messages sent by the server to the user. The server sends the HELLO message as soon as it establishes a connection to the user. After that, for any message it receives that matches the user-to-server message format, other than a BYE message, the server should always return either a BOARD message, a BOOM message, or a HELP message.

For any message from the user which does not match the user-to-server message format, discard the incoming message and send a HELP message as the reply to the user.

The action to take for each different kind of message is as follows:

HELLO message

In this message:

• N is the number of users currently connected to the server, and
• the board is X × Y.

This message should be sent to the user exactly as defined and only once, immediately after the server connects to the user. Again the message should end with a NEWLINE.

Example:

W

e

l

c

o

m

e

t

o

M

i

n

e

s

w

e

e

p

e

r

.

P

l

a

y

e

r

s

:

1

2

i

n

c

l

u

d

i

n

g

y

o

u

.

B

o

a

r

d

:

8

c

o

l

u

m

n

s

b

y

8

r

o

w

s

.

T

y

p

e

'

h

e

l

p

'

f

o

r

h

e

l

p

.

\r

\n

BOARD message

The message consists of a series of newline-separated rows of space-separated characters, giving a grid representation of the board’s state with exactly one character for each square. The mapping of characters is as follows:

• “-” for squares with state untouched.
• “F” for squares with state flagged.
• “ ” (space) for squares with state dug and 0 neighbors that have a bomb.
• integer COUNT in range [1-8] for squares with state dug and COUNT neighbors that have a bomb.

Here is an example board message with 3 rows and 8 columns:

										2		-		-	\r	\n
1		1						1		F		-		-	\n
F		1						1		-		-		-	\n

Notice that in this representation we reveal every square’s state of untouched, flagged, or dug, and we indirectly reveal limited information about whether some squares have bombs or not.

In the printed BOARD output, the (x,y) coordinates start at (0,0) in the top-left corner, extend horizontally to the right in the X direction, and vertically downwards in the Y direction. (While different from the standard geometric convention for IV quadrant, this happens to be the protocol specification.) So the following output would represent a flagged square at (x=1,y=2) and the rest of the squares being untouched:

- - - - - - -
- - - - - - -
- F - - - - -
- - - - - - -
- - - - - - -
- - - - - - -
- - - - - - -

In order to conform to the protocol specification, you’ll need to preserve this arrangement of cells in board while writing the board messages. If you change this order in either writing the board message or reading the board from a file (Problem 4) your implementation does not satisfy the spec.

BOOM message

The message is the word BOOM! followed by a NEWLINE.

Example:

B

O

O

M

!

\r

\n

The frightening message a client will receive from the server if they dig up a bomb.

HELP message

The message is a sequence of non-NEWLINE characters (your help message) followed by NEWLINE.

Example:

R

T

F

M

!

\n

Unlike the above example, the HELP message should print out a message which indicates all the commands the user can send to the server. The exact content of this message is up to you – but it is important that this message not contain multiple NEWLINEs.