SCG/Avatar
Question:
How does the domain and claim definition
influence the behavior of the software developers?
Management communicates the requirements to software
developers through domain and claim definitions.
It is the task of the software developers to create an
avatar that implements the requirements and that
successfully competes with the avatars of competitors.
The SCG is designed in such a way that the winning avatar
has the best implementation of the requirements
within the group of competing avatars.
The advantage of SCG is that the software developers
challenge each other through the SCG game mechanism
to improve their software. This mechanism stays invariant
as the domain and claim definition changes.
Definitions
A domain Domain consists of the
set of all problems, called Domain.Problems
and the set of all solutions, called Domain.Solutions
and a predicate called valid:
(Domain.Problems, Domain.Solution)-> Boolean.
There is also a function quality:
(Domain.Problem, Domain.Solution)->[0,1].
In summary, Domain = (Problems,Solutions,valid,quality).
A claim C(D) for domain D consists of a set
of problems in D.Problems, a quality q in [0,1] and
a resource bound r in [0,1].
In summary, a claim C(D) is a triple: (problems,q,r).
Informally, the claim C(D) says that
the claimant can take any problem in C(D).problems
and calculate a solution of at least quality C(D).q
using at most C(D).r resources.
Software Product Lines
Management has the option to ask for software
with many features
by providing a problem set using many related features.
The claims language expresses all feature combinations
but one claim focuses on one feature combination.
The nature of SCG encourages the software developers
to use a product line approach to implement the many features.
Example: The claims partition the set of
all domain problems into subsets of similar problems
that have a property that allows for a better, customized solution.
For CSP, we partitioned the problems into TBall (one relation),
Softball (one relation tree), Baseball (any relation set).
An additional partition is ALL/SECRET depending on whether
we want to satisfy the fraction of all clauses
or the fraction of the clauses of a secret solution.
Singleton claims C(D), where C(D).problems consists of one
element in D.Problems, are also interesting.
Solve Function
The domain D and claim C(D) definitions directly influence
how the crucial solve function
(solve: D.Problems->D.Solutions)
in the avatar should be implemented.
The solve function is useful to implement the
oppose function which is crucial in finding weak
claims proposed by other avatars. One approach is
to apply solve to some "hard" problems in C(D).problems
and determine the quality that can be achieved.
This gives information about whether a refutation or
a strengthening attempt is appropriate.
The solve function is also useful for implementing the
provideProblem function. Before a problem is provided,
we apply our own solve function to get an estimate for the quality
that can be achieved. The goal is to find a problem where
only a low quality can be achieved.
Finally, the solve function is a useful method to implement
the propose function.
In summary, the solve function is central to playing the game well.
By defining the domain D and claim C(D) appropriately, we can guide
the software developers to implement a strong solve function
that solves the problems we want to have solved. Through
the claims language, the software developers make predictions
on how well and how efficiently the solve function will perform
on certain subsets of problems.
Quality Function
The quality function expresses how well a solution solves
the problem.
It might define the quality in terms of the asymptotic quality.
For example, for HighestSafeRung,
with a generic decision tree depth HSR(n,2):
If < n, quality is 0,
if < k * kth root of n, quality is 1-1/k,
if < log(n), the quality is 1.
The strongest claim to be made is 1/2.
For some domains the quality function is set to 1 for all solutions.