CSU 670 Spring 2009, Software Development Karl Lieberherr Out: January 27, 2009 Due: February 3, 2009 Topics for your current player ------------------------------ Get ready for the next T Ball competition February 3: Improve raw material construction. (To be discussed in class.) Improve the buying algorithm for maximizing profit (0/1 Knapsack: http://en.wikipedia.org/wiki/Knapsack_problem). Use outsourced software to compute maximum bias. (see below) Some of the functionality below will be useful for your current and future players. PART 1: 2+ points ======================================== TESTING Compare your player and the administrator against our requirements document. http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/project/csu670-sp09-reqs.pdf What to turn in: All discrepancies you find with a description how to repair the software. Your modified player that implements the requirements. Pay detailed attention to sets versus lists. PART 2: 5 points ======================================== Roadmap By now you have acquired significant knowledge about the Specker Derivative Game and you know the code base on which you build. Document your road map to the fast pitch softball stage of your algorithmic trader (multiple relations). This is a 1-2 page document, summarizing requirements, clarifying issues left open or left contradictory in the requirements document and enumerating the steps you intend to follow. Explicitly list what components will be changed and/or developed, their use and where they fit in the whole scheme of things. Make a plan for your fast pitch softball project. Estimate the time it will take you to finish each component given that you have already worked on several of the components. The development diaries should be helpful in doing the estimations. PART 3: 20 points ================================================= We implement simple functionality that you need for the project. All implementation is done in DemeterF because the programs look like designs and can easily be adapted to other structures. We use the following example using a short-hand notation (slightly different than our standard): CSP-Formula F: 5: 22 1 2 3 // 5 is weight, 22 the relation 4: 22 1 2 4 2: 2 1 2 4 PART A: 5 points =========================================================== (Note: you might already have this from the previous subproject) Compute the Shannon cofactors of a CSP-formula F for a literal z of variable x. Given F, we want to compute F_x and F_x' according to the formula: F = x and F_x or x' and F_x' Use Ahmed Abdelmeged's relation class you used for computing the quality of a finished product. The Shannon cofactors are useful for many algorithms. Flow based design to be implemented in DemeterF: Flow through the CSP-formula F and build the cofactor F_x by reducing each constraint by setting x to true in each constraint. For example, the constraint 5: 22 1 2 3, where 1 is set to true reduces to 5: ? 1 2 3 where ? is the relation number returned by Ahmed's Relation class. Reducing a constraint means to create a new one with the same weight, and a new relation number. The number of variables remains 3. The relation number will say which variables are don't care variables. Note that List.index(...) is useful in this context and of course the Relation.reduce(...) method. Computing a Shannon cofactor is a translation from the language CSP-formula onto itself and therefore calls for the use of the Bc class. How do you send the literal z? Use an update method. You need it when you find the new relation number. PART B: 2 points =========================================================== Compute the set of relations contained in CSP formula F. Predicate T(F) = (2,22) PART C: 4 points =========================================================== Compute the weighted fraction WF(F) of constraints of each occurring relation number in a CSP formula F. WF(F) = 2: 2/11 22: 9/11 11 is the total number of weighted constraints. Note for T Ball, this is not yet important. But it will become important for multiple independent relations (fast pitch softball). PART D: 7 points =========================================================== This part will be useful for improving your product finishing agent for SDG(CSP). We provide you with software written by an outsourcing team that provides you with an abstraction of CSP-formulas that is good enough to play the SDG(CSP) game optimally. The provided software helps you to translate a CSP-formula into a polynomial on one variable p. This variable is a probability which you use to generate a random assignment with bias p. A random assignment with bias p is an assignment where each variable is set to true with probability p. The maximum bias is the best probability. http://www.ccs.neu.edu/home/lieber/courses/csu670/f07/outsourced/guaraldi/satsolver-1.1/api/index.html The following link points to a good implementation: /home/lieber/.www/courses/csu670/sp09/source/Administrator/lib/willg-1.0.jar or http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/source/Administrator/lib/willg-1.0.jar Implement the following task: Input: CSP-formula F (several relations allowed!). Output: Coefficients and maximum bias of the polynomial. Test your program with various CSP-formulas including one where the type is T=(22). The maximum bias should be one 1/3 in this case. Is it? What should the maximum bias be for T=(X). Test your hypothesis with a CSP(X)-formula. Try X = 1, 60, 90, 102. Are the polynomials for 60,90,102 all different? For part D make a software development plan that you implement during the week. PART E: (3 points) ================== Design a class dictionary that accepts the following input. You define a cd for Boolean expressions and Linear Pseudo Boolean expressions. Note that a raw material consists of a set of weighted constraints followed by the relation definitions. Turn in your cd with multiple test inputs. 1: 1 v1 v2 v3 1: 2 v7 v8 v9 1: OneInThree v7 v8 v9 100: AtLeastTwoInThree v7 v8 v9 7: AtLeastTwoInThree2 v4 v5 v6 5: Or2 v4 v5 4: Neg v4 1: Pos v5 4: F15 v5 v6 relations // formulated with x1 x2 x3 pseudo OneInThree = 1*x1 + 1*x2 + 1*x3=1 pseudo AtLeastTwoInThree = 1*x1 + 1*x2 + 1*x3 >= 2 pseudo AtLeastTwoInThree2 = x1 + x2 + x3 >= 2 pseudo F11 = 2*x1 + 2*!x2 + 7*x3 >= 5 pseudo F12 = 2*x1 - 3*!x2 <= 3 pseudo F13 = 2*x1 + 2*!x2 <= 3 pseudo F14 = x1 = 1 pseudo F15 = 3*x1 - 2*!x2 <= 3 Pos = x1 Neg = !x1 Or2 = (or x1 x2) F1 = (or !x1 (and (or x2 x1) !x3)) F2 = (or ) F3 = (and) Turn in your robot to Blackboard as a jar file containing the source code. Also turn in the jar file for your player, but without source code, to /scratch/lieber/csu670-sp09-sdg/feb3 Make sure you name your robot after your team name followed by the subproject number. We use the same turn-in protocol from subproject 3. General guidelines for all submissions: Organize your submissions. If a project asks for part 1, part 2 with sub parts A and B, part 3, your submission must have the same structure: /part1 /part2 /partA /partB /part3 where partA is a subdirectory of part2, etc. Readme files are appreciated. They should contain information like: part 1 is in Y.java and part 2 in C.java and program.input. If the program runs, submit your tests written in JUnit 4.