Homework #1 is over. See the scoreboard for information on the ranking of submissions.
Homework #1 - Pipe dream
(Adapted from the original Japanese arcade game in 1990)
For this homework, you will implement a game playing agent to play the solitaire game, Pipe Dream. In Pipe Dream, the goal is to lay pipe to divert ooze from a gushing sewer main break into a system of pipes to keep it from leaking out as long as possible. Your score is the final determiner of whether your agent does well or not.
The board is a 7x7 grid in which a pipe tile can be placed in a square. The pipe tiles can be placed anywhere on the grid and come in seven different configurations: a vertical pipe, a horizontal pipe, a cross (a vertical and horizontal pipe stacked together) and four elbow pipes. Pipe tiles are provided one at a time, in some order. In addition to knowing the current piece to be placed, the agent has access to the queue of the next 4 tiles to be placed. The source of the ooze originates from the center tile, going towards the top.
The initial layout at time 0.
At time t=0 through t=6, no ooze emerges from the center source tile. Subsequently, after 3 units of time, the ooze will go through a single pipe tile. Ooze can be directed through cross pipe in both directions. The grid's edge is the boundary; any pipe ends facing edges can not be connected to additional pipe.
The ooze is starting to flow, at time 6. If there is no suitable tile above the source tile by t=9, the game is over.
At each time unit, the agent can do one of the following actions, all of which take a unit of time to perform:
- Place the current tile at a empty x,y coordinate
- Destroy an occupied tile at a filled x,y coordinate (only possible if ooze has not started to flow through the tile yet)
- Do nothing
At time 18, this agent has laid some pipe, and waited at some time units.
Note: You cannot directly discard a pipe tile; you must place in on an available spot on the grid and then destroy it. If your module specifies to do an action which is invalid, a unit time will also elapse.
The game ends when the ooze spills out of the pipe (because your agent didn't lay an appropriate at the outflow coordinate, or because the flow ran off the edge of the grid, or because the entire grid is filled with pipe. The agent's goal is the maximize its final score (the score is the agent's utility).
Your agent's score can be calculated by the following:
- Each tile where the ooze flows through: +2
- Bonus for each cross tile where the ooze flows through both ways: +5 (a total of (2x2)+5 = 9)
- Each destroyed tile: -3
Note that tiles laid but un-oozed through do not factor into the agent's score whatsoever.
Implementation
Your agent will play this game by way of a single Java class which
will extend the abstract class, Player. Most
significantly, the Player class has the public method,
play(). play() takes a single argument
Driver d, an instance of the Driver class,
which will enable you to get the state of the game components: the
queue, the board and information about the next ooze.
play() will return an Action object, that
encodes the agent's action and, when applicable, its coordinates.
The class Action, has the following methods:
- setAction (char action): sets the action of the agent for this unit t to one of the three actions: 'p' place current tile, 'd' destroy tile, 'w' wait. The default value of action is 'w' wait.
- setX (int x): sets the x coordinate for the action's location. Valid values will be between 0 and 6.
- setY (int y): sets the y coordinate for the action's location. Valid values will be between 0 and 6.
- constructor Action (char action, int x, int y): the obvious constructor. Will take the values provided and install it in the appropriate fields.
Note that the valid values for the X and Y coordinates will not
check whether the action would actually be valid. It is your
responsibility to generate an agent that constructs a valid
Action object.
Queue pieces are represented by tiles which take on character values: one of the following characters seven characters: '+' <cross piece>, '|' <vertical pipe>, '-' <horizontal pipe>, or 'q' <tile with left and up outlets>, 'e' <pipe with up and right outlets>,'c' <right and down outlets>, or 'z' <down and left outlets> (it may be helpful to visualize this on a QWERTY keyboard with 's' in the center).
The Board will have two additional types of pieces that can appear: ' ' <empty space>, '\'' <starting tile, with ooze coming out northwards>.
For convenience, in implementing the agent class, you may also call
the following accessor methods to get the state of the game, through
the Driver class instance:
-
int getTimeToNextOoze (): returns the number of turns left before the ooze moves forward another square. -
int getTime (): returns the number of turns elapsed since the start of the game -
int getScore (): returns the agent's score so far -
int getNextOozeSpotX (): returns the X coordinate of the next spot where the ooze will move to. -
int getNextOozeSpotY (): returns the Y coordinate of the next spot where the ooze will move to. -
char[] getQueue (): returns a 5 element array containing the pieces in the queue to be placed. The 0th indexed piece is the current piece to be placed. -
char[][] getMap (): returns a 7 by 7 element array containing the pieces on the map.
Additional accessor and print methods are available to you in this
assignment. The full documentation for the java
package is available. Examine the contents carefully. Also available
to you is a sample class, MyPlayer.java, that also shows
how to compile your agent into an actual game execution.
Getting a feel for the assignment
Well, by all means you have to play the game a bit to get an idea of what type of heuristics and search might be useful. You can try my implementation of the Strategic Pipe Dreams Framework. It'll probably one of the few times you can tell your parents that you must play games in order to do your homework!
Compiling and submitting the assignment
When the pipedream package is released, you'll have to do the following things to compile and run the package.
To compile, you'll need the pipedream.jar (Version 1.1, updated Mon Jan 26 18:38:21 GMT-8 2004) and the directory where you have your implementation of the MyPlayer class in your classpath. Assuming MyPlayer.java is in the current directory:
javac -classpath .:pipedream.jar MyPlayer.java
To execute the game you have to do something similar:
java -cp .:pipedream.jar MyPlayer
You should submit your working version of the agent by the midnight
on the due date, 4 Feb. The IVLE workbin will accept late submissions. Late
submissions are subject the the late
submission policy (read carefully). Your class should be named
MyPlayer and should present in a file named
MyPlayer.java. Your work should be done independently;
see our classes' section on Academic
Honesty Policy if you have questions about what that entails.
Min-Yen Kan <kanmy@comp.nus.edu.sg> Created on: Mon Dec 1 19:36:22 2003 | Version: 1.0 | Last modified: Sat Feb 14 13:11:02 2004