Problem Set 4: Multiplayer Minesweeper
- Beta due
- Tuesday, April 12, 2015, 10:00 pm
- Code reviews due
- Thursday, April 14, 2015, 10:00 pm
- Final due
- Tuesday, April 19, 2015, 10:00 pm
The purpose of this problem set is to explore multithreaded programming with a shared mutable data type, which you should protect using one or more thread safety strategies.
Design Freedom and Restrictions
On this problem set, you have substantial design freedom.
Your solution must not change the name, signature, or specification of the MinesweeperÂServer
methods main()
or runMinesweeperServer()
; you also should not change the implementation of main()
.
You may change any of the other provided code in MinesweeperServer
.
Also note that the axis definition of your board must match what is defined in Protocol and specification. The (x, y) coordinates start at (0, 0) in the top-left corner, extend horizontally to the right in the x direction, and extend vertically downwards in the y direction.
Your code will be tested against the specification. Changing these interfaces or axes will cause the tests to fail, and you will receive 0 points for the submission. 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.
Beyond these requirements you have complete design freedom. For example, you can add new methods, classes, and packages; rewrite or delete other pieces of provided code; etc.
Get the code
To get started: create a remote psets/ps4
repository by visiting Didit, then pull the repo from Athena using Git:
git clone ssh://[username]@athena.dialup.mit.edu/mit/6.005/git/sp16/psets/ps4/[username].git ps4
If you need a refresher on how to create, clone, and import your repository, see Problem Set 0.
Overview
You will start with some minimal server code and implement a server and thread-safe data structure for playing a multiplayer variant of the classic computer game “Minesweeper.”
You can review the rules of traditional single-player Minesweeper on Wikipedia.
You can also play traditional single-player Minesweeper online.
(You may notice that the implementation in the latter link above does something subtle. It ensures that there’s never a bomb where you make your first click of the game. You should not implement this for the assignment. It would be in conflict with giving the option to pass in a pre-designed board, for example.)
Your final product will consist of a server and no client; it should be fully playable using the telnet
utility to send text commands directly over a network connection as described below.
Multiplayer Minesweeper server
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 for the other players.
In our version, when one player blows up a bomb, they still lose, and the game ends for them (the server ends their connection), but the other players may continue playing.
The square where the bomb was blown up is now a dug square with no bomb.
The player who lost may reconnect to the same game again via telnet
to start playing again.
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 user of Multiplayer Minesweeper must accept this kind of risk.
We are not specifically defining, or asking you to implement, any kind of “win condition” for the game.
Telnet client
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 oftelnet
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 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.
Protocol and specification
You must implement the following protocol for communication between the user and the server.
The messages in this protocol are described precisely and comprehensively using a pair of grammars. Your server must accept any incoming message that satisfies the user-to-server grammar, react appropriately, and generate only outgoing messages that satisfy the server-to-user grammar.
Messages from the user to the server
Formal grammar
Each message starts with a message type and arguments to the message are seperated 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
DIG message
FLAG message
DEFLAG message
HELP_REQ message
BYE message
Messages from the server to the user
Formal grammar
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
BOARD message
BOOM message
HELP message
Problem 1: set up the server to deal with multiple clients
In minesweeper.server.MinesweeperServer
, we have provided you with a single-threaded server which can accept connections with one client at a time, and which includes code to parse the input according to the client-server protocol above.
Modify the server so it can maintain multiple client connections simultaneously. Each client connection should be maintained by its own thread. You may wish to add another class to do this.
As always, all your code should be safe from bugs, easy to understand, and ready for change. Be sure the code to implement multiple concurrent clients is written clearly and commented if necessary.
You may continue to do nothing with the parsed user input for now.
When you write tests in MinesweeperServerTest.java
, you may write tests similar to the published test we provide, and you may also write tests using ByteArrayInput
/OutputStream
stubs as described in Sockets & Networking.
Problem 2: design a data structure for Minesweeper
In minesweeper.Board
, we have provided a starting file for this problem.
Specify, test, and implement a data structure for representing the Minesweeper board (as a Java type, without using sockets or threads).
Define the Board
ADT as well as any additional classes you might need to accomplish this.
You may ignore thread safety for now.
Your Board
class (and other classes) must have specifications for all methods; abstraction function, rep invariant, and safety from rep exposure written as comments; and the rep invariant implemented as a checkRep()
method called by your code.
Problem 3: make the entire system thread-safe
Come up with a strategy to make your system thread safe. As we’ve learned, there are multiple ways to make a system thread safe. For example, this can be done by:
- using immutable or thread-safe data structures
- using a queue to send messages that will be processed sequentially by a single thread
- using synchronized methods or the synchronized keyword at the right places
- or combination of these techniques
The specification for
Board
(and any other classes) should state whether that type is thead-safe.In addition to the other internal documentation,
Board
(and any other classes) must document their thread-safety argument. Depending on your design, the board (or other classes) may not be thread-safe. If so, document that.You will also document your system thread safety argument in
MinesweeperÂServer.java
in problem 5.SFB, ETU, RFC: be sure any code to implement thread safety is written clearly and commented if necessary.
Problem 4: initialize the board based on command-line options
We want our server to be able to accept some command-line options.
The exact specification is given in the Javadoc for MinesweeperServer.main()
, which is excerpted below:
Usage:
MinesweeperServer [--debug | --no-debug] [--port PORT] [--size SIZE_X,SIZE_Y | --file FILE]
The
--debug
argument means the server should run in debug mode. The server should disconnect a client after a BOOM message if and only if the--debug
flag was NOT given. Using--no-debug
is the same as using no flag at all.E.g.
MinesweeperServer --debug
starts the server in debug mode.
PORT
is an optional integer in the range 0 to 65535 inclusive, specifying the port the server should be listening on for incoming connections.E.g.
MinesweeperServer --port 1234
starts the server listening on port 1234.
SIZE_X
andSIZE_Y
are optional positive integer arguments specifying that a random board of size SIZE_X Ă— SIZE_Y should be generated.E.g.
MinesweeperServer --size 42,58
starts the server initialized with a random board of size 42 Ă— 58.
FILE
is an optional argument specifying a file pathname where a board has been stored. If this argument is given, the stored board should be loaded as the starting board.E.g.
MinesweeperServer --file boardfile.txt
starts the server initialized with the board stored inboardfile.txt
.
We provide you with the code required to parse these command-line arguments in the main()
method already existing in MinesweeperServer
. You should not change this method.
Instead, you should change runMinesweeperServer
to handle each of the two different ways a board can be initialized: either by random, or through input from a file.
(You’ll deal with the debug flag in Problem 5.)
For a --size
argument: if the passed-in size X,Y > 0, the server’s Board
instance should be randomly generated and should have size equal to X by Y.
To randomly generate your board, you should assign each square to contain a bomb with probability .25 and otherwise no bomb.
All squares’ states should be set to untouched.
For a --file
argument: If a file exists at the given path, read the the corresponding file, and if it is properly formatted, deterministically create the Board
instance.
The file format for input is:
In a properly formatted file matching the FILE grammar, the first line specifies the board size, and it must be followed by exactly Y lines, where each line must contain exactly X values.
If the file is properly formatted, the Board
should be instantiated such that square i,j has a bomb if and only if the i’th VAL in LINE j of the input is 1.
If the file is improperly formatted, your program should throw an unchecked exception (either RuntimeException
or define your own).
The following example file describes a board with 4 columns and 3 rows with a single bomb at the location x=2, y=1.
If neither --file
nor --size
is given, generate a random board of size 10 Ă— 10.
Note that --file
and --size
may not be specified simultaneously.
Reading from a file: see tips for reading and writing below.
Implement the runMinesweeperServer
method so that it handles the two possible ways to initialize a board (randomly or by loading a file).
Running the server on the command line: this is easiest to do from the bin
directory where your code is compiled.
Open a command prompt, cd
to your ps4
directory, then cd bin
.
Here are some examples:
cd bin
java minesweeper.server.MinesweeperServer --debug
java minesweeper.server.MinesweeperServer --port 1234
java minesweeper.server.MinesweeperServer --size 123,234
java minesweeper.server.MinesweeperServer --file ../testBoard
java minesweeper.server.MinesweeperServer --debug --port 1234 --size 20,14
You can specify command-line arguments in Eclipse by clicking on the drop-down arrow next to “run,” clicking on “Run Configurations…”, and selecting the “Arguments” tab. Type your arguments into the text box.
Problem 5: putting it all together
Modify your server so that it implements our protocols and specifications, using a single instance of
Board
.Note that when we send a BOOM message to the user, we should terminate their connection if and only if the debug flag (see Problem 4) is missing.
The tips for reading and writing below may be useful for reading from and writing to socket streams.
Near the top of
MinesweeperServer
, include a substantial comment with an argument for why your system is thread-safe.SFB, ETU, RFC: be sure the code to implement thread safety is written clearly and commented if necessary.
Commit to Git. Pushing your code to your Git repository on Athena will cause Didit to run a single staff-provided test. You can read and download the source code for the published test.
You are strongly encouraged to download and run the published test on your own machine.
Do not attempt to debug failures on Didit before you can run and pass the published test locally on your own machine.
Tips for reading and writing
BufferedReader.readLine()
reads a line of text from an input stream, where line is considered to be terminated by any one of a line feed (\n
), a carriage return (\r
), or a carriage return followed immediately by a linefeed. This behavior matches the NEWLINE productions in our grammars.You can wrap a
BufferedReader
around bothInputStreamReader
andFileReader
objects.PrintWriter.println()
prints formatted text to an output stream, and terminates the current line by writing the line separator string. It always writes a line separator, even if the input string already ends with one. The line separator is defined by the system propertyline.separator
; you can obtain it usingSystem.lineSeparator()
. It is\n
on *nix systems and\r\n
on Windows. Both of these line endings are allowed by the NEWLINE productions in our grammars.You can wrap a
PrintWriter
around aWriter
orOutputStream
objects.
Beyond telnet
You are now done with the problem set, but you could imagine not having to use telnet
to play Minesweeper.
A GUI would do a lot to bring your program to life.
Here is GUI client from past student Robin Cheng that you can use to play your Minesweeper game: Minesweeper GUI.
This GUI waits until you do a LOOK or other operation before updating the view.
It has UI for spawning clients, so you can actually just run the jar once and then use the UI to spawn a number of clients.
It also displays a printout of all the protocol I/O which is going on, making it particularly helpful for debugging.
You should have your server running before trying to start a client connection from this GUI.
Note: This GUI is entirely unofficial! You may find bugs or incorrect behavior. Do not consider it sufficient for testing your code.
If you want practice writing GUIs, we encourage you to write your own Minesweeper GUI and email the source to the staff.
Submitting
Make sure you commit AND push your work by 10:00pm on the deadline date.
This problem set takes longer for Didit to process than previous psets, so push early. Remember that 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 published 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.