CSU 670 Fall 2008, Software Development Karl Lieberherr Out: October 3, 2008 Due: October 10, 2008 PART 1: 3 points ======================================== TESTING Thorougly test the generic player against our requirement document: http://www.ccs.neu.edu/home/lieber/courses/csu670/f08/requirements/sdg-f08.pdf http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/requirements/SDG2.doc Create a specific player/administrator for CSP that must use the communication language we selected. But your specific player is otherwise like the generic player: it is dumb. It is very important to keep the generic player clean. Use the include option for .cd files as shown in: /home/lieber/.www/courses/csu670/f08/project/genericSDG/ClassicProject Separate your code for the generic player and the CSP specialization. ---------------------- general.cd ... only contains generic structure; nothing about Constraints ---------------------- classic.cd //cd for generic version include "general.cd"; RawMaterialInstance =String. ... If you note discrepancies report them to the class mailing list asap. /home/lieber/.www/courses/csu670/f08/bhavna/ClassicProject/history.input and history1.input shows sample output from the generic player produced by Bhavna Balani. What to turn in: All discrepancies you find with a description how to repair the software. Your modified player and your modified administrator that implement the requirements. We will run the first whole class competition with your tested generic players with the new communication language. PART 2: 5 points ======================================== Roadmap By now you have acquired significant knowledge about the Specker Derivative Game and you know the code base (the generic player that only knows about predicates, raw materials, and finished products without the details) on which you build. Document your road map to the final stage of your algorithmic trader to be ready in 3 or 4 weeks with ample time to improve its performance in the artificial market until December. 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 developed, their use and where they fit in the whole scheme of things. Make a plan for your project. Estimate the time it will take you to finish each component given that you have already worked on several of the components. 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. Use our standard notation: /home/lieber/.www/courses/csu670/f08/project/project3/rawmat 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 =========================================================== 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 in http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/project/project4/IR-2.0/doc/ Source code: /home/lieber/.www/courses/csg110/sp08/project/project4/IR-2.0 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 quality(F,J) of assignment J for CSP-formula F. J = (1,!2,!3,4) // !2 is 2 negated. quality(F,J) = (5+2/11)=5/11 Flow through the CSP-formula and use the reduce function from Ahmed's class for each constraint. Looks like a good use of TUCombiner? The fold is summation. The leaves are the constraints which reduce to a number. PART C: 2 points =========================================================== Compute the set of relations contained in CSP formula F. Type T(F) = (2,22) This is PART D: 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 PART E: 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 implementations http://www.ccs.neu.edu/home/lieber/courses/csu670/f07/outsourced/guaraldi/ It is recommended to use Daniel's or Will's implementation. Implement the following task: Input: CSP-formula F. 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 E make a software development plan that you implement during the week.