CSU 670 Spring 2009, Software Development				Karl Lieberherr
Out: January 27, 2009
Due: February 3, 2009

Topics for your current player
------------------------------

Get ready for the next T Ball competition February 3:
Improve raw material construction.
  (To be discussed in class.)
Improve the buying algorithm for maximizing profit (0/1 Knapsack:
http://en.wikipedia.org/wiki/Knapsack_problem).
Use outsourced software to compute maximum bias.
  (see below)

Some of the functionality below will be useful for 
your current and future players.

PART 1:  2+ points
========================================
TESTING

Compare your player and the administrator
against our requirements document.
http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/project/csu670-sp09-reqs.pdf

What to turn in:
All discrepancies you find with a description how to repair the software.

Your modified player that implements the requirements.

Pay detailed attention to sets versus lists.

PART 2: 5 points
========================================

Roadmap

By now you have acquired significant knowledge about
the Specker Derivative Game and you know the code
base on which you build. 

Document your road map to the 
fast pitch softball stage of your algorithmic trader
(multiple relations).
This is a 1-2 page document,
summarizing requirements, clarifying issues left open or left contradictory
in the requirements document and enumerating the steps you intend to follow.
Explicitly list what components will be changed and/or developed, their use and
where they fit in the whole scheme of things.
Make a plan for your fast pitch softball project.

Estimate the time it will take you to 
finish each component given that you have already
worked on several of the components.
The development diaries should be helpful in doing the estimations.

PART 3: 20 points
=================================================

We implement simple functionality that you need for the project.
All implementation is done in DemeterF because the programs
look like designs and can easily be adapted to other structures.

We use the following example using a short-hand notation
(slightly different than our standard):

CSP-Formula F:

5: 22 1 2 3        // 5 is weight, 22 the relation
4: 22 1 2   4
2:  2 1 2   4

PART A: 5 points
===========================================================
(Note: you might already have this from the previous subproject)

Compute the Shannon cofactors of a CSP-formula F for a 
literal z of variable x.
Given F, we want to compute F_x and F_x'
according to the formula:

F = x and F_x or x' and F_x'

Use Ahmed Abdelmeged's relation class you used for computing the quality of a finished product.

The Shannon cofactors are useful for many algorithms.

Flow based design to be implemented in DemeterF:
Flow through the CSP-formula F and build the cofactor F_x
by reducing each constraint by setting x to true
in each constraint. For example, the constraint
5: 22 1 2 3, where 1 is set to true reduces to
5:  ? 1 2 3
where ? is the relation number returned by Ahmed's Relation class.
Reducing a constraint means to create a new one
with the same weight, and a new relation number.
The number of variables remains 3.
The relation number will say which variables are don't care variables.
Note that List.index(...) is useful in this context
and of course the Relation.reduce(...) method.

Computing a Shannon cofactor is a translation from the
language CSP-formula onto itself and therefore calls
for the use of the Bc class.

How do you send the literal z? Use an update method.
You need it when you find the new relation number.


PART B: 2 points
===========================================================
Compute the set of relations  contained in CSP formula F.
Predicate T(F) = (2,22)


PART C: 4 points
===========================================================
Compute the weighted fraction WF(F) of constraints of each 
occurring relation number in a CSP formula F.
WF(F) =
2:  2/11
22: 9/11

11 is the total number of weighted constraints.

Note for T Ball, this is not yet important. 
But it will become important for multiple independent
relations (fast pitch softball).

PART D: 7 points
===========================================================
This part will be useful for improving your 
product finishing agent for SDG(CSP).
We provide you with software written by an outsourcing team
that provides you with an abstraction of CSP-formulas
that is good enough to play the SDG(CSP) game 
optimally. The provided software helps you to translate
a CSP-formula into a polynomial on one variable p.
This variable is a probability which you use to generate a random
assignment with bias p.
A random assignment with bias p is an assignment where 
each variable is set to true with probability p.
The maximum bias is the best probability.

http://www.ccs.neu.edu/home/lieber/courses/csu670/f07/outsourced/guaraldi/satsolver-1.1/api/index.html

The following link points to a good implementation:
/home/lieber/.www/courses/csu670/sp09/source/Administrator/lib/willg-1.0.jar
or
http://www.ccs.neu.edu/home/lieber/courses/csu670/sp09/source/Administrator/lib/willg-1.0.jar

Implement the following task:
Input: CSP-formula F (several relations allowed!).
Output: Coefficients and maximum bias of the polynomial.

Test your program with various CSP-formulas including one
where the type is T=(22). The maximum bias should be
one 1/3 in this case. Is it? 

What should the maximum bias be
for T=(X). Test your hypothesis with a CSP(X)-formula.
Try X = 1, 60, 90, 102.

Are the polynomials for 60,90,102 all different?

For part D make a software development plan that you implement during the week.

PART E: (3 points)
==================

Design a class dictionary that accepts the following input.
You define a cd for Boolean expressions and 
Linear Pseudo Boolean expressions.
Note that a raw material consists of a set of weighted
constraints followed by the relation definitions.

Turn in your cd with multiple test inputs.

1: 1 v1 v2 v3
1: 2 v7 v8 v9
1: OneInThree v7 v8 v9
100: AtLeastTwoInThree v7 v8 v9
7: AtLeastTwoInThree2 v4 v5 v6
5: Or2 v4 v5
4: Neg v4
1: Pos v5
4: F15 v5 v6
relations  // formulated with x1 x2 x3
pseudo OneInThree = 
  1*x1 + 1*x2 + 1*x3=1
pseudo AtLeastTwoInThree =
  1*x1 + 1*x2 + 1*x3 >= 2
pseudo AtLeastTwoInThree2 =
  x1 + x2 + x3 >= 2
pseudo F11 =
  2*x1 + 2*!x2 + 7*x3 >= 5
pseudo F12 =
  2*x1 - 3*!x2 <= 3
pseudo F13 =
  2*x1 + 2*!x2 <= 3
pseudo F14 =
  x1 = 1
pseudo F15 =
  3*x1 - 2*!x2 <= 3
Pos = x1 
Neg = !x1
Or2 = (or x1 x2)
F1 = (or !x1 (and (or x2 x1) !x3))
F2 = (or )
F3 = (and)


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/feb3
Make sure you name your robot after your team 
name followed by the subproject number.
We use the same turn-in protocol from subproject 3.

General guidelines for all submissions:

Organize your submissions.
If a project asks for part 1, part 2 with sub parts A and B, part 3,
your submission must have the same structure:

/part1
/part2
   /partA
   /partB
/part3

where partA is a subdirectory of part2, etc.
Readme files are appreciated. They should contain
information like: part 1 is in Y.java and part 2
in C.java and program.input.

If the program runs, submit your tests written in JUnit 4.