Managing Software Development
Project 1: More Products through Feature Combination
Spring 2008
Karl Lieberherr  
Out: Feb. 5, 2008

Due date: Feb. 12, 2008 

Now that you are familiar with your player and some of its evolution
possibilities using open classes (inter-type declarations)
as well as pointcuts/advice, we take take a closer look at XP 
(Extreme Programming):
http://www.xprogramming.com/xpmag/whatisxp.htm.

In XP: quote from the above page:
The Extreme Programming team keeps the system integrated 
and running all the time. 
The programmers write all production code in pairs ...
end of quote

For us this means that we wan to keep our algorithmic player
in a working state where it can compete against other players.

Again from the above website I quote:

Continuous Integration

Extreme Programming teams keep the system fully integrated 
at all times. We say that daily builds are for wimps: 
XP teams build multiple times per day. 
(One XP team of forty people builds at least eight or ten times per day!)
end of quote

PART 1: Continuous Integration
==============================

Submit your build of the algorithmic player for the modified pay feature:
pay(d,J,F) = fsat(J,F) > d.price ? 1 : 0
from project 2. We called this version of the game:
SDG-SP08-all-or-nothing.
Put your algorithmic player for SDG-SP08-all-or-nothing
into CCIS directory:

/scratch/lieber/sdg/comp1

by Thursday, Feb. 7, 10 pm. Create a directory called 
LastName1_LastName2_LastName3 and put your player and 
additional files it might need into that directory.
If there are only 2 members of the team, you mention
only 2 last names. Use the last names in sorted order.

Your player will be taken from there
and entered into a competition.


PART 2: Software Product Line for SDG
=====================================

In this part we expand our product line considerably.
All we could do so far is still possible in the
expanded product line; we don't want to give up
functionality.

All our relations are Boolean, so variables, such as
x,y and z are either 0 or 1.
In the previous project we experimented with
constraints of the form: R(x,y,z) iff x+y+z>=2.

And before, we had constraints of the form: 
R0(x,y,z) iff x+y+z>=1 and 
R1(x,y,z) iff (1-x)+y+z>=1 and
R2(x,y,z) iff (1-x)+(1-y)+z >=1 and
R3(x,y,z) iff (1-x)+(1-y)+(1-z) >=1 

For example:

(x or y or z) and 
(x or !y or z) and
(!x or y or !z) would be expressed as:

R0(x,y,z) and
R1(y,x,z) and // note the order!
R2(x,z,y)     // note the order

We expand our product line by switching from MAX-SAT to MAX-CSP
(CSP = Constraint Satisfaction Problem).
A derivative now has a type which consists of a set of Boolean relations.
We limit the rank to 3. There are 256 relations of rank 3. Each number in [0..255]
corresponds to a relation. So we can view the type of a derivative as
a set of numbers in [0..255].
The raw material is now a CSP(G)-formula, where G is a set of Boolean relations.
A CSP(G)-formula consists of a set of constraints, each having a weight, a relation from G
and a set of variables.
The MAX-CSP(G)-problem consists of finding an assignment for a CSP(G)-formula F
that maximizes the fraction of weighted, satisfied constraints in F.
A finished product for a raw material (a CSP(G)-formula F) is an assignment to the 
variables of F.
The quality of the finished product is the fraction of weighted, satisfied constraints.

This generalization of the Specker Derivative Game from MAX-SAT to MAX-CSP
has an impact on our solver:

1. We need a way to express the new kinds of derivatives. We need a language
   and a data structure.
   /home/lieber/.www/courses/csu670/f07/project/final-lang
   is the old language.

2. We need a new agent that offers derivatives and prices them appropriately. We have now a much
   larger set of possible derivatives.

3. We need a new agent that buys derivatives at an appropriate price.

4. We need a new agent to finish the raw materials. This agent needs to solve the MAX-CSP(G)
   problem for the purpose of the game. Remember, that the general MAX-CSP(G) problem
   is NP-hard for most G.

Note that the mechanics of the game otherwise stays the same. So the testing we do in part 1
will also be useful for playing the generalized game.

To deal with relations, use the code documented here:

http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/project/project4/IR-2.0/doc/

http://www.ccs.neu.edu/research/demeter/papers/POptMAXCSP/
contains material related to how the relation numbers are computed.
See section 3 of: SPOT-NU-CCIS-07-01.pdf .
Note that in the outsourced code all relations must be of
exactly rank 3. If you have a relation of rank 1 or 2 you need to pad it
to rank 3.

What to turn in:
For 1. to 4. choose very simple solutions that you can implement quickly.

1. requires synchronization between the teams.

The administrator needs to be updated too.

Turn in a working player (it must follow the rules but it may lose all its money)
and administrator.