Semester Project

Updates

4/24, 6:20 PM	Slightly clarified the EnemyLocationResponse description. Here is code for non-blocking IO: (sock is a single socket) val descs = [OS.IO.pollIn(Socket.pollDesc(sock))] val ready:bool = OS.IO.poll(descs,SOME Time.zeroTime) <> [] (ready is now true if and only if there is data to be read on the socket. This data can of course be read with a regular recvVec (blocking call) )
4/24, 8:20 PM	project.zip has been changed slightly to prevent monsters from starting at the players' starting points. The class files for the client are also up. You can view the client options by running "java Client -?". Note that for the java client to work, the "graph" and "npc" files must be created as in the provided SML source code.
4/25, 2:00PM	The class files have been updated to mark the shrine nodes in yellow. A number of other small changes were made to the client. Also, a Java server is now included so you can test your client. The server can be run with "java Server". As with the client, "graph" and "npc" must be present.
4/26, 4:30PM	Fixed a bug in the class files above.
4/26, 5:00PM	You may now download a skeleton Client.sml file. It contains a little bit of code to connect to an ip and port. It also contains some basic graph code. In particular, the function `nexts` may be useful as it will tell you where to go next to get somewhere. Note that calling nexts over and over again with the same two arguments will always return the same result. Thus, a simple way to improve the efficiency of this function is to cache the results (perhaps in a `int list array array`). You may also find it useful to move this function to a separate file for organizational reasons (though you certainly don't have to). Note also that the entry point for your client is `Client.launch`. When this function is invoked, you should connect 6 sockets to the specified ip and port for your 6 agents. You should then send a StartRequest on each of these sockets with the player id provided, and with agent numbers 0..5.

Design and skeleton server implementation due 6PM Monday, May 1st.

Full server and client implementation due 11:59PM Saturday, May 13th.

Download partial Code.

For your final project, you will be implementing a game. As evidenced by Nethack, Final Fantasy (the earlier ones), and Dungeons and Dragons Advanced 2nd Edition, all enjoyable games have fantasy settings; so will yours. The game you are implementing is called Dungeons and Satisfiability, because instead of fighting dragons, you, uh, solve satisfiability problems. But, really, it's fun.

Overview

The general idea of the game is as follows: the king of your land has been slain, by your dastardly nemeses. Before you can wage brutal war against the fiends, the new king must be anointed at the sacred shrine of your native deity, which is deep in the dungeons below your land.

Luckily, your enemies are stalled, because the last act of your beloved, heroic leader was a successful assassination plot against his counterpart in the country of the enemy. They too must anoint the heir to their throne before he can lead them in battle.

The catch is this: the dungeon systems containing the two shrines are intertwined. Therefore, as you race to your respective shrines to anoint your heirs, you can divert resources to attempt to waylay your opponents.

Objective

The first team to move its heir to its shrine wins.

Pieces

Each player will control one heir and five expendable henchmen.

The Dungeon

The dungeon is a large undirected graph -- nodes are landmarks, edges are boobytrapped corridors. The dungeon has both a start node and a node containing the shrine for each of the two teams.

The server should generate the dungeon as follows: randomly generate 1000 points within the unit square. For every node, connect it to any nodes withing 0.06 units.

Choose the uppermost and lowermost points in the middle of the board horizontally (that is, between 0.45 and 0.55). One of these (the top one) will be the starting point of the first team, and one of them will be the shrine. The leftmost and rightmost points in the middle of the board will be the starting point and shrine for the second team.

No dungeon-crawl is complete without NPC monsters to kill. (An NPC is a monster not controlled by either of the two computer players. If you knew that already, and know what NPC stands for, you get a prize.) For every node, a monster will be added to the node with probability 1/20. If the node is within 0.2 units of a shrine, the probability increases to 1/10. If it is within 0.1 units, it increases to 0.25. Everyone knows that mindless monsters instinctively protect magical shrines.

Movement

Movement rules are rather complex, because, of course, this is no ordinary dungeon; it is thoroughly booby-trapped. Each corridor is blocked by a number of obstacles, each of which has a 1/8 chance of killing a passerby. Thankfully, these obstacles are controlled by switches on either side of the corridor; unfortunately, the controls are rather complex.

More formally, each boobytrap is controlled by a set of exactly 3 switches, and is turned off when at least one of those three switches is in the right position. Constraints are of the form S_i or -S_i, where S_i means "this boobytrap is turned off when switch i is activated," and -S_i means "this boobytrap is turned off when switch i is deactivated."

When a henchman or heir wishes to move from one vertex to another, the agent sends a message to the server indicating which node the agent wants to move to. The server then sends back the list of boobytraps in the corridor, and the conditions under which each boobytrap can be turned off. The player then tries to solve the puzzle -- that is, to find a certain alignment of the switches that deactivates all (or almost all) of the boobytraps. When the player finds a satisfactory solution, he sends it to the server. The server then calculates, based on the number of traps still active under the solution, whether or not the agent survives. (So, if the solution submitted deactivates all but 2 booby-traps, the agent would survive with probability 49/64.) If the agent survives, it traverses the corridor and is moved to the vertex on the other side. One way or the other, the server notifies the player of the outcome.

Technicality: A unique set of traps and switches is magically generated anytime an agent wishes to cross a corridor, even if another agent -- or even the same agent -- just crossed that corridor. Furthermore, when a player tells the server that an agent intends to move across a corridor, and receives the traps in reply, he is committed to that move, until he submits a trap solution, or until an enemy agent happens upon him and he diesuntil he submits a trap solution, or until an enemy agent happens upon him and he dies.

Combat

There are three factions: player 0, player 1, and the monsters. Whenever two pieces with opposing factions are on the same vertex, all pieces on that vertex die. NPCs that die never respawn. Through the wonder of large mook armies and enormous harems, however, both player have virtually unending supplies of henchmen and heirs, so any agent that dies respawns immediately at its starting point, ready to move.

Vision

At the beginning of play, each player is sent a full description of the graph, including both start points and shrines. Each player is aware of the location of the opponent's heir at all times; whenever a player's heir moves, the other player's agents receive a notice of which vertex he has moved to. Whenever an agent moves into a node adjacent to one occupied by an enemy or NPC, that agent, and the enemy agent (if it is not an NPC) receive notices.

Boobytrap/Switch Generation

A state is selected for the 25 switches as the solution state. Next, 50 boobytraps are generated. For each boobytrap, 3 of the 25 switches are chosen at random: i, j, and k. The way in which the boobytrap can be turned off by these three switches is then chosen at random. So, one of S_i or -S_i is chosen, along with one of S_j or -S_j and one of S_k or -S_k. If the generated boobytrap is not turned off by the chosen solution state, then this boobytrap is discarded and another one is generated until there are 50 total. (Note that since each switch in the solution state has a 50% chance of deactivating a boobytrap, only 1/8 of the generated boobytraps will need to be discarded.)

Warning

All of the number parameters for this game -- the numbers used in randomly generating the graphs, the number of henchmen, etc -- are subject to change. You are well advised not to hard-code them into your actual program, but instead to put them in a separate struct in a separate file so that updating your code for new values will be easier.

Your Job

For the first part of this assignment, you are responsible for creating the server-side of this game. You will create a server that is capable of processing player moves and changes in the game state, enforcing the game rules, and keeping players appraised of any changes in the game state that they should be aware of. This will involve work with concurrency, awareness of synchronization issues, and a good design for your representation of the game's current state. The second part of the assignment is to write a client that will go head to head with clients from other groups.

To make this job easier, you will be given some code to start with. First, you will be given code for generating the graph, as well as code for generating boobytraps. In addition, you will be given some of the code to perform the IO operations. More specifically, you will be given code to create a listener socket, and code to read and write requests and responses on established connections. Note that the socket connections will persist throughout the duration of the game. You will have to write the rest of the code yourself.

The file Listener.sml contains code to listen on a port. When a new connection is made, the listener will establish the connection, and give you a socket called newsock. It is your job to take this socket and do with it whatever you think is necessary so that you can keep track of it and read and write on it. Note that each client connects on its own socket. Thus when all the clients have connected, there will be 12 active sockets, one per agent per team.

Your server will read requests, and send responses on the sockets it establishes. The files Request.sml and Response.sml contain the requests and response, as well as code for sending them over the network. You may not change the requests or responses in any way that will result in a different protocol. The following table gives all the requests and resposes, and the circumstances under which they should be sent:

Start Request This request is sent exactly once by each agent on each team. It indicates which team the player is on (player is either 0 or 1) and which agent this particular agent is. Agent 0 is always the heir, while agents 1-5 are the henchmen. No responses of any type should be sent until 12 start requests have been received from the 12 agents (6 per team).

Move Request This request is sent by an agent who wants to move to a new location. The server must validate the move: it must ensure that there is an edge between the agents current location and new destination. The server must also ensure that the agent is not already committed to moving to some other location. Finally, no agent is allowed to move to the other teams start of shrine nodes. In the move is invalid in any way, an error message should be sent back to the client. Otherwise, a boobytrap problem should be sent back.

Sat Solution Request This request gives a solution to the boobytraps in a corridor. The server should first check that the agent who sent this request is currently trying to move. If the agent did not send a previous move request, then an error message should be returned. Also, it is possible that ever though the agent did send a previous move request, he was killed between the time that the server responded to the move request and the time that the server received this request.

Dungeon Response Once all 12 agents have connected, the dungeon (graph) should be sent to all of them. It contains the description of the graph, including the start and shrine positions.

Sat Response This is sent in response to a valid move request and gives the client a boobytrap problem to solve

Move Response This is probably the most important response. Whenever an agent moves for any reason, he must be sent a move response. A move response could sent in response to a sat solution request -- this is the most common case. However, it could also be the result of an enemy agent coming to the same location him. If it is the result of a boobytrap solution request, and the agent successfully makes it to the new node, then success should be true, otherwise it should be false. Is an agent tries to move, but one of the boobytraps kills him, then a move response should indicate that he has been sent back to start. If an agent sucessfully moves, or is moved into (attacked), he should also receive a move response, and killed should be a vector of all the enemies killed. For enemy agents, this vector gives their agent number. For NPCS, use Contants.NPC in this vector.

For example, consider the simplest scenario, where an agent moves to node 1 and doesn't encounter any enemies or get killed by a boobytrap:

The agent sends a move request with destination=1

The server sends back a sat solution response

The agent sends a sat solution request

The server sends a move response with location=1 and success=true

Note that (counterintuitively) a move response is never sent in response to a move request.
Enemy Location Response Whenever an agent sees an enemy (or NPC) this response must be sent. This means that whenever an agent moves (whether it be successfully or through death) that agent must be told who he sees in adjacent nodes. In addition, this response is also sent when an agent can no longer see an enemy. For example, if an agent moves and sees the enemy agent at node 3, he should be sent an enemy location response with location=3 and seen=true. If the agent runs away, so he is no longer adjacent to node 3, he should be sent an enemy location response with location=3 and seen=false. Since everyone knows where the enemy heir is, every time an heir moves to a new location, two enemy location response must be sent to the whole team: the first telling the individuals that he is no longer at his previous location (seen=false), the second telling the individuals that he is now at his new location (seen=true).

One way to think about this is that every time an agent is told that he can see someone, he should eventually be told that he cannot see that entity at that location. The only time this is not true is when the game ends, or if neither of the relevant agents ever moves (which would make them rather poor players).

Game Over Response Sent when one team wins. The field indicates which team won (0 or 1). This message should be sent to all agents on each team.

Error Message Response Sent whenever anyone submits an invalid request of any sort. Contains an error message

Things to think about

How will you represent the state of the world?
You will need to synchronize the sockets. While it is ok for one thread to read on a socket while another one writes, you will run into problems if multiple threads try to read on the same socket or if multiple threads try to write on the same socket at the same time.
When players move, they generate events that effect other players. How will you handle this?
It is important that moving be atomic, we wouldn't want to enemy players to end up at the same node without dieing. How will you ensure this?
It is not uncommon for an agent to send a move request and then die before solving the boobytraps. You need to make sure that such agents are told they have died, and that they can now move from the start.
In a fair game, all the requests will be responded to in a timely fashion. Does your design ensure this is true for the most part?

Notes on CML

When programming in CML, you will want to include cml.cm and cml-lib.cm in your sources.cm file. If calls to "print" aren't working for you, try TextIO.print.

If a thread causes an exception, you will not be aware of it unless you explicitly handle it and print out an error message. One way around this is to use the TraceCML structure. If, after thread creation, you execute TraceCML.watch("THREADNAME",thread_id), then any uncaught exceptions will be printed.

Finally, dealing with the end of the game is complicated, since you would like to shutdown cleanly and exit all threads. For the purposes of this problem, as long as you send game over response to everyone, we will not worry about what happens after that.

Testing

To facilitate testing your code, a Java client will be provided that allows visualization of the game as it progresses. The client will be available on Monday, the 24th.

Start Request	This request is sent exactly once by each agent on each team. It indicates which team the player is on (player is either 0 or 1) and which agent this particular agent is. Agent 0 is always the heir, while agents 1-5 are the henchmen. No responses of any type should be sent until 12 start requests have been received from the 12 agents (6 per team).
Move Request	This request is sent by an agent who wants to move to a new location. The server must validate the move: it must ensure that there is an edge between the agents current location and new destination. The server must also ensure that the agent is not already committed to moving to some other location. Finally, no agent is allowed to move to the other teams start of shrine nodes. In the move is invalid in any way, an error message should be sent back to the client. Otherwise, a boobytrap problem should be sent back.
Sat Solution Request	This request gives a solution to the boobytraps in a corridor. The server should first check that the agent who sent this request is currently trying to move. If the agent did not send a previous move request, then an error message should be returned. Also, it is possible that ever though the agent did send a previous move request, he was killed between the time that the server responded to the move request and the time that the server received this request.

Dungeon Response	Once all 12 agents have connected, the dungeon (graph) should be sent to all of them. It contains the description of the graph, including the start and shrine positions.
Sat Response	This is sent in response to a valid move request and gives the client a boobytrap problem to solve
Move Response	This is probably the most important response. Whenever an agent moves for any reason, he must be sent a move response. A move response could sent in response to a sat solution request -- this is the most common case. However, it could also be the result of an enemy agent coming to the same location him. If it is the result of a boobytrap solution request, and the agent successfully makes it to the new node, then success should be true, otherwise it should be false. Is an agent tries to move, but one of the boobytraps kills him, then a move response should indicate that he has been sent back to start. If an agent sucessfully moves, or is moved into (attacked), he should also receive a move response, and killed should be a vector of all the enemies killed. For enemy agents, this vector gives their agent number. For NPCS, use Contants.NPC in this vector. For example, consider the simplest scenario, where an agent moves to node 1 and doesn't encounter any enemies or get killed by a boobytrap: The agent sends a move request with destination=1 The server sends back a sat solution response The agent sends a sat solution request The server sends a move response with location=1 and success=true Note that (counterintuitively) a move response is never sent in response to a move request.
Enemy Location Response	Whenever an agent sees an enemy (or NPC) this response must be sent. This means that whenever an agent moves (whether it be successfully or through death) that agent must be told who he sees in adjacent nodes. In addition, this response is also sent when an agent can no longer see an enemy. For example, if an agent moves and sees the enemy agent at node 3, he should be sent an enemy location response with location=3 and seen=true. If the agent runs away, so he is no longer adjacent to node 3, he should be sent an enemy location response with location=3 and seen=false. Since everyone knows where the enemy heir is, every time an heir moves to a new location, two enemy location response must be sent to the whole team: the first telling the individuals that he is no longer at his previous location (seen=false), the second telling the individuals that he is now at his new location (seen=true). One way to think about this is that every time an agent is told that he can see someone, he should eventually be told that he cannot see that entity at that location. The only time this is not true is when the game ends, or if neither of the relevant agents ever moves (which would make them rather poor players).
Game Over Response	Sent when one team wins. The field indicates which team won (0 or 1). This message should be sent to all agents on each team.
Error Message Response	Sent whenever anyone submits an invalid request of any sort. Contains an error message