Project 5

CSU 670 Fall 2007
Out: October 5, 2007
Due October 12, 2007
This subproject consists of 3 parts: Producing Raw Materials, Communication and Coordination and Roadmap.

Producing Raw Materials

Producing Raw Materials Part 1

To play the Specker Derivative Game well, we need to solve the following sub problem:
Input: CNF type T
Output: Weighted CNF F of type T in which only a small fraction of the clauses 
can be satisfied. CNF F contains max_clauses clauses and max_variables variables.

Ideally we would like to have an F that minimizes the fraction of clauses that can be
satisfied. Can we achieve such a post condition efficiently?

With our lack of information about what the most difficult raw material of a given type T is, let's try something that is easy to implement and maybe a good approximation of what we are looking for. Consider a type T = ((j1,p1) (j2,p2). The js are the clause length and the ps are the number of positive literals. Consider one pair of the type and lets call it (j,p). Let's assume that we have n variables. Let's generate ALL clauses of type (j,p) with n variables. How many are there: choose(n,j)*choose(j,p) where choose(n,k) is the binomial coefficient n choose k.

n=4, j=2, p=1
choose(n,j)*choose(j,p) = 6 * 2 = 12.

Here they are: (one clause per line)

!1  2
 1 !2
!1     3
 1    !3
!1        4
 1       !4
   !2  3
    2 !3
   !2     4
    2    !4
      !3  4
       3 !4
Given a type T = ((j1,p1) (j2,p2) we generate choose(n,j1)*choose(j1,p1) clauses for the first pair and choose(n,j2)*choose(j2,p2) clauses for the second pair. Those clauses are delivered as raw material.

We don't take advantage of assigning weights to the clauses; currently all clauses have weight 1. In your own algorithmic player you should choose a clever way to assign weights to the clauses to make it harder to satisfy a large fraction of the clauses.

Producing Raw Materials Part 2

Use your MAXSAT solver from project 4 to find a satisfying assignment. Can you manually do better than your solver? Turn in the outputs from several test runs for different types. This might actually give you information about how to price your derivatives when you play the game!

Communication and Coordination

Implement a simple Administrator and Player for the 
Blackboard Architecture using a 
black board in a file system F that we have chosen.

Implement the following sequence of transactions for one turn of the player:

Put all the transactions for one turn as one batch into the blackboard.

The Adminstrator tells the player that it is 
its turn by setting a flag in the blackboard.

The Player gets the store.

The player prepares a list of transactions and puts them into the blackboard.

The Administrator collects it and updates the store etc.


Document your road map to the final stage of you algorithmic trader. This is a 1-2 page document, listing requirements, clarifying issues left open or left contradictory in the game description 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. Estimate the time it will take you to finish each component given that you have already worked on several of the components.