CSCI-4150 - Homework 1 - Due: Mon, Feb 11, 11:59:59 PM

• The homework must be done individually.
• Please utilize the discussion board on WebCT to submit your questions. This would allow others to benefit from your answers. We will periodically check the board and answer your questions.
• This homework constitutes 10% of the total grade.
• Do not cheat -- we will analyze codes manually and also pairwise-compare all codes using automated software.
  

Homework Description:

Before starting this homework, you may want to play around with the Yahoo! Arrows game to help you understand it better. Here are some slides with snapshots from the game.

You will implement two search algorithms capable of finding a goal state (aka board configuration) with the maximum reward to the Yahoo! Arrows game. A Java framework will be given to you which will represent the arrow board, the rules for moving the pieces and a function to check to see if it's a valid solution. You are responsible for extending this framework and implementing various search algorithms so that given a particular configuration, you program will be able to find the desired solution in a timely manner. Your program is also required to return the intermediate states between the initial configuration and the final state.

Board: The board consists of three types of objects: red arrows, blue arrows and spaces. The standard yahoo game starts out with all of the red arrows on the left side, all of the blue arrows on the right side and a space in the middle. However, your program should be able to start from any input state. The goal of the game is to move all of the blue arrows to the left side and all of the red arrows to the right side while following certain rules. The board will be represented in the code as char's with red arrows = 'r', blue arrows = 'b' and spaces = 's'. The initial configuration is a string consisted of these characters. Example: the Yahoo! Arrows game is "rrrrsbbbb" and the solution is "bbbbsrrrr"

Moving: Red arrows can only move to the right and blue arrows can only move to the left and they must move into a space. An arrow can only move into a space if that space is right next to the arrow or if a single arrow of the opposite color is between it and a space. See the Yahoo! game.

Rewards: A constant rewards is given to each valid move. If you reach the goal/solution state, you receive an infinite reward. The objective of the game is to maximize the total reward.

Code:

You will be given the code to several Java classes to help you get started: Provided Source Code. A link to the Java Collections Framework is provided (bottom of page). This framework contains a lot of classes which you will find useful. Using them is very much like using the STL libraries in C++. Note that using the framework is optional. It is provided for your convenience.

Classes:

• Main.java This class will contain the main function which starts the application. It is responsible for getting the input for the starting state, checking to see that is is valid and creating the objects which starts the arrow game. It is also the class which will call the solution function and print out the results. You can change this file to help you debug but we will not be using your version so make sure your final submission works with the one that we give you. You can also create your own entry point by copying the main function into any other class and setting that as the main class for your project.
• ArrowBoard.java This class represents an arrow board configuration or state. The board will take in a char array which will represent the configuration of the board. You are free to alter and change the code as you see fit or completely write your own class, as long as the interface remains the same -- i.e. name still stays the same, it still contains the public char[] getBoard() function and the constructor still stays the same, ArrowBoard(char[] board). The Main and ArrowBoardSolver classes must work with your implementation. This class is given to you because it contains functions that will allow it to work with the Java Collections Framework (HashMap, HashSet, ArrayList.....) implementations so that different ArrowBoard objects with identical configurations will be treated as the same object. You are not required to use the Java Collections Framework by any means but it might be useful.
• ArrowBoardSolver.java This class represents the object that will be responsible for solving the game and should be where the majority of your search tree building code should go. There are two solve functions which will each be given an ArrowBoard object and should solve that arrow board object. The heuristics solve function will also be given a max number of nodes variable. The path from the initial configuration to the solution or state with the max reward must be stored in the internal ArrowBoard[] path variables for each of the search algorithms. There are also public variables called numNodes where you must set to the total number of nodes visited at the end of your solve function. Your class must still contain the same functions and public variables as the version that we provide because these functions and variables will be used to in the Main class to test your solution. Other than this, feel free to add whatever you want.
• Utilities.java This class contains utilities functions for the game. These functions include moving an arrow, checking to see if the solution is valid, printing, etc. These functions were designed for the ArrowBoard where the actual board configuration is stored as an char array but you are free to use this class or copy the code from this class into your own separate class. Since the ArrowBoard class is required to return a char array, regardless of your ArrowBoard implementation, we will use this Utilities class to test your solution. Do not change this file. If you need to add your own function, place it in another class.
• Node.java This class is given to you as a basis for you to create your own nodes. You do not have to use it if you prefer to implement your own.

Goals:

We will be testing your search algorithm on various inputs such as "rrsbbsr", "rsbsrsbs" and other arbitrary configurations. Therefore, just hard coding a solution to a problem similar to the Yahoo! games one will not work. The path that you program should produce will be consisted of an array of ArrowBoard objects with the first object in the array representing the initial state and the last one representing the final state. This path must be stored in the public variables within the ArrowBoardSolver class for the two search algorithms. You also must set the numNodes variables to the number of total nodes that you visit in your searches. You algorithm must also produce a result within a reasonable time of 3-4 minutes per run.

1. Find a path to a state with the maximum reward given an arrow board state through an exhaustive search by trying all possibilities for the search path. Fill in the function solveExhaustive(ArrowBoard board) and place the resulting path in pathExhaustive and the number of nodes in numNodesExhaustive. For this part, implement Iterative Deepening search technique.
   
2. Find a path to a state with the maximum reward using A*. Design your heuristics so that it outputs a solution on a large input configurations (e.g. input of length 15-30). We will impose a restriction on the number of nodes that can be generated. Fill in the function solveHeuristics(ArrowBoard board, int maxNodes) and place the resulting path in pathHeuristics and the number of nodes in numNodesHeuristics. You should increment a counter every time a node is visited and must terminate when maxNodes is reached (outputting the best solution found so far).
   

Grading:

50% will be automatically taken off from submissions that do not compile. Therefore, make absolutely sure that your code will work with the code that we provide, specifically the Main and Utilities class. We will be testing the solution paths that you will provide by running your array of ArrowBoard objects through the isValidPath(ArrowBoard[] board) function in the Utilities class. This function is provided for you to test your solutions before submission. We will also be checking the numNodes variables. If your program takes more than a reasonable time (> 5 mins) to run, 10% of your grade will be taken off.

Submitting:

Submit the following items in a zip file.

1. ArrowBoardSolver.java, ArrowBoard.java and any other classes that your program needs. You should not be submitting your own versions of Main.java or Utilities.java because we will be using the ones that we provide and will overwrite yours.
2. A readme describing what files you are submitting, any problems that you encountered and anything else that you need to explain or feel that we should know.
3. A pdf file that contains both of your algorithms in pseudo-code and an explanation + justification of your heuristic in plain English.

Links:

• When using the Java Collections Framework, be sure to specify the class that the Collections object will be holding. This is a new feature in Java 1.5 known as Generics. Previous to 1.5, whenever you extract something from a Collections object, you had to cast it into it's proper class. Now you can specify which class of objects will be held and no longer need to cast back and forth.
  Example: To create an ArrayList to hold strings, use: ArrayList<String> al = new ArrayList<String>(); instead of ArrayList al = new ArrayList();
• If you use the Collections Framework and need to convert an ArrayList or a similar object into a standard array, use the following code:
  String[] stringArray = (String[])arrayList.toArray(new String[arrayList.size()]);
  Here, an array of String objects is created from an ArrayList object holding Strings.