CSU 670 Fall 2007 Out: October 12, 2007 Due October 19, 2007 : NEW: Due on October 23.This subproject consists of 3 parts: Creating Derivatives, Buying Derivatives, the Complete Game.
Input: A set of possible CNF types Output: A type T, not yet in use and a price for the derivative of type T. Postcondition: Ideally we would like to have a type T for which you know a good price price(T). I.e., when you produce raw material for T you and you get a finished product, you will have to pay less than what got for the derivative (price(T)).
With our lack of information about what the most difficult raw material of a given type T is, let's reuse the construction from project 5. Given a type T, we constructed RawMaterial(T). Find the maximum assignment for RawMaterial(T) (why can you do that efficiently?) and make the maximum satisfaction ratio the price of your derivative. This is the algorithm I recommend you use as a first approximation: Choose a T involving two clause types. Apply the construction above to determine the price for the derivative with type T.
Of course, this might make your derivative too expensive because another player could have a more clever way of constructing raw materials in which only a smaller fraction can be satisfied.
Test your DerivativeCreation agent on suitable test cases.
Input: A derivative d that is for sale. Output: Accept offer/ Reject offer Post condition: Buy if price(d) < inf max fsat(R,J), where the infimum (inf) is among all raw materials R of type(d) and the maximum is among all assignments J to the variables of R. Of course, the condition type(R) = type(d) must hold where type(d) is the type of the derivative and type(R) is the type of the raw material. We call the solution to the inf max problem for derivative d, inf-max(d). Note that such min-max or inf-max problems are common in the analysis of games because we want to win even when the oponent makes the best move. In SDG, our move is to choose raw material and the oponent's move is to find a good assignment.Making the buying decision is easier said than done. You need to predict the worst case raw material for type type(d). Learn from the history about how to price d. If a derivative with type type(d) was not sold so far, you are out of luck? Are you? Computing inf-max(d) precisely can be done but is left to the individual teams.
Implement the Administrator and the Player, create two instances of the Player and let them play against each other. Use the blackboard as discussed in class. To start the game, the players need to deposit their executable player (running under Windows XP) in a directory, called executables in the blackboard. The deposit needs to be done by a certain time, like 10 pm. The format of the executables directory is a list of files of the form player_name.bat which contains the information about invoking player_name.exe or player_name.jar. By the deadline, the administrator will come and start the game by starting a new thread for each executable. Those threads have the blackboard as shared memory. At any one time, only one thread is active, namely the thread corresponding to the player who is currently selling and buying etc.