CSU 670 Spring 2009 Out: January 20, 2009 Due: January 27, 2009 Karl Lieberherr Subproject 3 INTRODUCTION This subproject will already result in our first robot competition (for the simpler game: Classic SDG CSP Slowpitch Softball) thanks to the functioning robot "babies" that the teaching staff has prepared for you. Section 3.3 in http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/project/csu670-sp09-reqs.pdf explain the different versions of the Classic SDG CSP game. The robots can read and write in a mutually understandable way and they can walk through the store and find out what is for sale. What they cannot do well yet is to recognize good buys and to put derivatives on the market at a price that will give them life energy. However in class we did an experiment: to perform a requirements analysis of the "make money with derivative d" requirement, we played with a suitably bent coin. We determined that the average satisfaction ratio among all assignments generated with the suitably bent coin is a certain number in [0,1], called break-even(d). We use the definition: fsat(r,J) is the fraction of satisfied constraints in raw material r and assignment J. Our robot can exploit this result in three ways: If the robot sees the derivative d on sale at a price p < break-even(d), the robot should buy it in the hope that it quickly can find for any given raw material r for d an assignment J with fsat(r, J) >= break-even(d). The robot knows such a good assignment must exist. The robot will look for the assignment by flipping a suitably bent coin. The second way to use the result is to never offer a derivative d below the price break-even(d) because we know that for all raw materials r of derivative d there is an assignment J that satisfies fsat(r,J) >= break-even(d). The third way to use the result is to finish a given raw material using an optimally biased coin. All Boolean relations used are arity 3. There are 256 such relations numbered 0..255. Important hint: Use Ahmed's Relation class: http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/source/IR-2.0/doc/ (documentation) http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/source/IR-2.0/src/edu/neu/ccs/evergreen/ir/ (implementation) Important methods: reduce: to compute the quality of a finsihed product q: to compute the polynomials that need to be maximized. The Relation class will greatly simplify your work. An important detail: 22(a b c) is encoded as: cba 000 001 1 010 1 011 100 1 101 110 111 PART 1: 15 points ======================================== Compute an upper bound on the price of the derivative d in Classic SDG CSP Slowpitch Softball at which you would buy the derivative. You would buy if the price is below this upper bound because you know there exists an assignment that will make a profit for you. More formally, we define break-even(d) for a derivative d to be the largest real number in [0,1] for which we can prove that for all raw materials r of derivative d there exists an assignment J satisfying fsat(r,J) >= break-even(d). Solution: Map d to a polynomial f[d] in b. b is the bias of a bent coin used to assign the variables. f[d](b) = expected fraction of satisfied constraints when assignments are generated randomly using a bent coin with bias b. break-even(d) = f[d](b_max), where b_max is the value where f[d](b) is maximum in [0,1]. PART 2: Buying Agent: 3 points ========================================== Add a buying agent to your baby robot that buys all derivatives d with a price p < break-even(d), provided there is enough life energy available. Part 3: Offering Agent: 3 points ========================================== Add an offering agent to your baby robot that only offers derivatives d at a price p > break-even(d). The hope is that once such a derivative is sold, the robot will find a raw material in which less than break-even(d) can be satisfied. We will focus on this task in later subprojects. But some of you might already have an idea of what should be done. Part 4: Finishing Agent: 4 points ========================================= Add a finishing agent to your robot that uses an optimally biased coin to generate the assignments. Generate a few assignments and take the best one. Part 5: Raw Material Delivery Agent: 4 points ========================================= The raw material delivery agent needs to create a raw material. If you don't have a better idea, use this raw material: R(v1 v2 v3) R(v1 v2 v4) R(v1 v2 v5) R(v1 v3 v4) R(v1 v3 v5) R(v1 v4 v5) R( v2 v3 v4) R( v2 v3 v5) R( v2 v4 v5) All constraints have weight 1. ======================================== Our expectation is that if you add this knowledge to your robot, it will perform better than the baby robot. We will include a plain baby robot in the competition for comparison. ======================================== 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/jan27 Make sure you name your robot after your team name followed by the subproject number. If your team name is SilverSnakes, call your jar on Blackboard SilverSnakes3_Source.jar and the other one: /scratch/lieber/csu670-sp09-sdg/jan27/SilverSnakes3.jar for this subproject 3. Remember that your source code will be made available to the class at a later time. The submitted robots are made available to the entire class so that you can check the competition results and observe the behaviors of all robots and learn from them. The Scrum masters need to decide which of those parts they have time to implement with their team by the deadline. The subproject will be evaluated based on how many subprojects you implement and based on the performance of your player in the competition. Besides your two jars and the diary, you must submit your sprint backlog for this week by Thursday, Jan. 22 to Blackboard/ Scrum Sprint Backlog 1. As an absolute minimum you must add to the baby robot the Raw Material Delivery Agent. You must submit a working robot that has been extended by your team. Follow these specs for delivering the player jar as well as the source code. * Deliver your source code as a compressed eclipse project. When we expand your source code we should get the following directory structure: |_src | |_ |_test |_ As for the projectName. Use your team name followed by the project number. If your team name is SilverSnakes and this is subproject 3 then the project name should be SilverSnakes3. * Deliver your player as a jar file. Use the given manifest file supplied with the GenericPlayer located at: http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/source/GenericPlayer/player/player.mf This manifest file has two important entries. The first is the "Main-Class" entry which defines the entry point for the player (the class with the public static void main method). This makes the jar executable and this is in turn important for the Admin to run your player. In the generic player, it is the GenericPlayer class. The second important record is the "Player-Class" entry which points to a class that implements the PlayerI interface. In the generic player. it is again the GenericPlayer class. This is important because we'll have an evaluator that evaluates the intelligence of the different agents of your robot. * It is important to unit test your application. We expect you to put some "Brain Power" in writing the test cases. Demonstrate this to us by writing a test plan and a reasonable amount of test cases.