\documentclass{llncs}

\title{SDG Game Requirements/Design: From Generic Form to the CSP Version}
\author{ Karl Lieberherr, Feng Zhou}
\institute{ College of Computer \& Information Science\\
  Northeastern University, 360 Huntington Avenue \\
    Boston, Massachusetts 02115 USA.\\
      \email{\{lieber,fengzhou\}@ccs.neu.edu}}

\date{\today}

\begin{document}
\maketitle
\section{Generic Requirements}

We parameterize the SDG game with the kind
of derivatives, raw materials etc. to be used. This supports better separation
of concerns at the requirements level. We can formulate the 
important game rules without knowing the details of the
derivatives.

\subsection{Parameterization}
The SDG game is parameterized by a tuple $C=(Typ,D,R,O,F,Q)$,
where $Typ$ is a set of types, $D$ (derivatives)
is a set of pairs $d=(t,price)$, where $t$ in Typ
and $price$, the price, is in [0,1].
$R$ (raw materials)
is a set with each
element $r$ in $R$ having a type $typ(r)$ in $Typ$,
$O$ is the set of outcomes for elements in $R$.
We denote an outcome for $r$ as $o(r)$. 
$F$ (finished product)
is a set of pairs
$(r,o(r))$, where $r$ in $R$ and $o(r)$ is in $O$.
$Q$ (quality) is a function that maps a finished
product $(r,o(r))$ to $[0,1]$.
The game is about buying and selling derivatives.
When a derivative $d=(T,p)$ is offered, only its type $T$ and
price $p$ in $[0,1]$ are known.
The creator and buyer
of a derivative need to do a min-max analysis for type $T$
which makes the game interesting.
By a min-max analysis I mean that it must be known
what the worst-case raw material is for a given type.
The seller must know this to price the derivative properly
and the buyer must know this to decide whether the price is right.
The buyer of a derivative will be paid the quality
of the finished product s/he achieves for the raw material
produced by the seller \emph{after} the derivative was bought.
All sets are finite.

$SDG(C)$ is a tuple $(P,account,store,config)$
$P$ is an ordered set of players,
$account$ is a function that assigns 
a positive real number to each player.
$store$ is a function that assigns 
a pair $(forSale, bought)$ to each player,
where $forSale$ is a set of derivatives for sale and
$bought$ is a set of bought derivatives.
A bought derivative is a tuple $(d,seller,r,f)$,
where $d$ is a derivative, $seller \in P$, 
$r \in \{R, absent\}$ and $f \in \{F, absent\}$.
$config$ is a tuple $(init, maxTurns, timeslot, mindec)$ which configures
the game. 
This configuration tuple will be later expanded with specifics
for the combinatorial structure to be used in the game;
for example, CNF or CSP.
$init$ is a positive real number, giving the initial
amount of the account of each player in $P$.
$maxTurns$ is the maximum number of turns the game will be played.
$timeslot$ is the amount of time given to each player.
$mindec$ is a small real number which specifies the minimum
decrement when the price of a derivative is lowered.

\subsection{Game Rules}
The $SDG(C)$ game has an asynchronous and a synchronous version.
Here we define the synchronous version. In the asynchronous
version, players could buy and sell at any time.
The rules of the synchronous $SDG(C)$ game are:

\begin{enumerate}
\item{Main Objective.}
The winner of the game is the player with the most money in 
the player's account at the end of the game.
The account value ranks the players. Players with the same account
value have the same rank.
\item{Uniform Turns.}
Only one player is playing at a given time. When a player is done,
the next player is the next element in the ordered set $P$.
A player may indicate that s/he is done in a variety of ways,
for example by creating a file.
In other words, the players take turns in a uniform sequence.
\item{Buy or Re-offer (to make derivatives more attractive).}
On each turn, a player must buy at least one derivative
offered for sale by other players or
re-offer all derivatives for sale by all other players at a lower price.
When a derivative is bought the seller is paid by the buyer the
price of the derivative.
\item{Offer new derivative}
On each turn, a player must offer a derivative whose type
does not exist yet in the store, or whose price is lower 
than the price of all other derivatives of the same type in the store.
\item{Timely reaction raw material delivery.}
A player must deliver raw materials for derivatives bought
from them in the previous round. The type of the raw material must
match type of the derivative.
\item{Obligation to buy back the finished product.}
The owner of a derivative is obliged to pay for a finished product
based on the quality achieved as soon as the finished product is delivered.
\item{Price lowering.}
When lowering the price of a derivative, it must be lowered at least by $mindec$.
\item{Bought once.}
A derivative may only be bought once from the store. 
\item{Positive account.}
Players must maintain a positive account.
\item 
Players must finish within $timeslot$.
\item
Players that don't comply with the rules are removed from the game.
\item
If a player is removed from the game, its derivatives
are removed from the store and its bought, but unfinished
derivatives are refunded to the buyer.
\item
After $maxTurns$ rounds, nothing can be bought but raw materials are still delivered
and finished until all outstanding obligations are met.
\end{enumerate}

\subsection{Archiving Concern}

We want to archive games for further analysis. 
We use the following 4 archiving transactions.
\begin{enumerate}
\item
When a player $p$
offers a derivative $d$, we archive $create(p,d)$.
\item
When a player $p$ buys a derivative $d$, we archive 
$buy(seller,p,d)$ where $seller$ is the seller of the derivative.
\item
When a player $p$ delivers raw material $r$ for derivative $d$, we archive
$deliverR(p,d,r)$.
\item
When a player $p$ delivers the finished 
product  $f=(r,o(r))$ for raw material $r$ for derivative $d$, we archive
$deliverF(p,d,f)$.
\end{enumerate}
Given a sequence of archiving transactions, we can check
whether the players followed the rules of the game.
For example, a player $p$ can only finish raw material 
for a derivative that $p$ bought previously.

\subsection{Security Concern}

It must be difficult for the players to cheat.
A so called non-functional requirement.
Currently, we don't pay much attention to this requirement,
to avoid an overload. Put in principle we should.
It is not a good idea to add security as an after-thought.


\subsection{Specialization for CNF}

This specialization initiates learning about propositional calculus
and basic combinatorics. Algorithms for MAX-SAT are important to
play the game well.

$Typ = (r1,r2)$ where $r1$ and $r2$ are clause types.
A clause type is a pair $(l,p)$, where $p$ is the set
of positive literals and $l$ is the length of the clause.
A derivative is a pair (t,p), where $t \in Typ$ and $p$ is
the price.
$R$ is the set of weighted CNFs of type $Typ$ where each clause has a positive
integer weight. The elements of $R$ are of a type in $Typ$.
$O$ is an assignment $J$ for a CNF.
$F$ is a pair $(r,J)$, where $J$ is an assignment for CNF $r$.
$Q(r,J)$ is the weighted fraction of satisfied clauses in CNF $r$ under
assignment $J$.

To make the sets finite we use the following configuration tuple:\\
$(maxVars, maxClauses, maxWeight, maxClasueLength)$.

\subsection{Specialization for CSP}
This specialization initiates learning about Boolean constraint
satisfaction.
Algorithms for MAX-CSP are important to
play the game well.

$Typ$ = set of Boolean relations of at most rank 3.
There are 256 Boolean relations of rank 3.
$R$ is the set of $CSP(Typ)$-formulas.
A derivative is a set of relations in $Typ$ and a price. 
$O$ is a Boolean assignment $J$ for a $CSP(Typ)$-formula.
$F$ is a pair $(r,J)$, where $J$ is an assignment 
to the variables of $CSP(Typ)$-formula $r$.
$Q(r,J)$ is the weighted fraction of satisfied constraints in $CSP(Typ)$-formula
$r$ under assignment $J$.

To make the sets finite we use the following configuration tuple:\\
$(maxVars, maxConstraints, maxWeight)$.

\section{Reflection on the course}

We can recognize elements of the game in real life.
You have selected this course based on a a set of features:
course description, college requirements, reputation, etc.
Based on those features you have selected to take my course.
The features correspond to the type of a derivative
which you buy only by knowing the type.
Now Feng and I are delivering raw materials (subprojects) within
the constraints of the course features we agreed upon.
While we make the raw materials a bit hard for you,
we do this with the objective of challenging and expanding
your intellectual capabilities in managing software development.
(This is different than in the game where we find hard raw materials
to avoid a high payout.)
You finish the raw materials by finding solutions to the subprojects
and you will be paid by the quality of your finished product
(your grade). Your real payout, however, is the set of 
new skills you learn about managing software development.

You can learn about managing software development by
learning the theory and by practicing the management
of a software development project. It is my belief that
without having experienced a project, you won't absorb the theory well.
That is why we experience the project of developing
algorithmic players.

\section{Design} 
The requirements don't specify how the players communicate
with each other. There are two options:  a centralized
versus a decentralized design. We use a centralized design
using an administrator.
The players and the administrator communicate through XML documents.

\section{Implementation}
We use Java as implementation language and a Java data
binding tool to automatically generate parsers and printers
from an XML schema.

In the implementation we practice Adaptive Programming (AP).
In AP, as little structural information
as possible is spread as narrowly as possible.
(A good design principle in general not only
for structural information.)

{\bf Acknowledgements:}
Milena Georgieva Dimitrova has given detailed feedback
on the requirements and she has written the previous
version of the requirements.

\end{document}