CS 4500 Fall 2009 Out: September 18, 2009 Due: September 25, 2009 Karl Lieberherr Subproject 2 INTRODUCTION This subproject will already result in our first agent competition (for the simpler game: Classic SCG CSP T Ball) thanks to the functioning agent "babies" that the teaching staff has prepared for you. Section 5.3 in http://www.ccs.neu.edu/home/lieber/courses/cs4500/f09/requirements/requirements-cs4500-f09.pdf explains the different versions of the Classic SCG CSP game. The agents 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 challenges 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 challenge 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 agent can exploit this result in three ways: If the agent sees the challenge d on sale at a price p < break-even(d), the agent 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 agent knows such a good assignment must exist. The agent will look for the assignment by flipping a suitably bent coin. The second way to use the result is to never offer a challenge d below the price break-even(d) because we know that for all raw materials r of challenge 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/software/IR-2.0/doc/ (documentation) http://www.ccs.neu.edu/home/lieber/courses/software/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 Notice the reverse order of the variables. PART 1: 15 points ======================================== Compute an upper bound on the price of the challenge d in Classic SCG CSP T Ball at which you would buy the challenge. 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 challenge d to be the largest real number in [0,1] for which we can prove that for all raw materials r of challenge 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 agent that buys all challenges 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 agent that only offers challenges d at a price p > break-even(d). The hope is that once such a challenge is sold, the agent 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 agent 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 agent, it will perform better than the baby agent. We will include a plain baby agent in the competition for comparison. ======================================== Turn in your agent 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/cs4500/f09/sep25 make sure you name your agent 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/cs4500/f09/sep25/SilverSnakes2.jar for this subproject 2. Remember that your source code will be made available to the class at a later time. The submitted agents are made available to the entire class so that you can check the competition results and observe the behaviors of all agents and learn from them. Competitions will be held on the due date at midnight, started by an aotomated script. The competitions are expected to run less than 2 hours. Make sure that the computer on which you run your agent is available on the web. Follow the following steps to ready your agent on the web: To be written by Bryan. 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. As an absolute minimum you must add to the baby agent the Problem Delivery Agent. You must submit a working agent 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 2 then the project name should be SilverSnakes2. * 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 agent. * 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.