Project 6

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.

Derivative Creation Agent

To play the Specker Derivative Game well, we need to solve the following sub problem:
Input: A set of possible CNF types 
Output: A type T, not yet in use and a price for the derivative of type T.

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.

Derivative Buying Agent

Which derivatives should you buy? First buy the ones for which you know that you will make money.
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,

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 complete game

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.