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 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.
A domain Domain consists of the set of all instances, called Domain.Instance and the set of all solutions, called Domain.Solution and a predicate called Domain.valid: (Domain.Instance, Domain.Solution)-> Boolean. There is also a function Domain.quality: (Domain.Instance, Domain.Solution)->[0,1]. In summary, Domain = (Instance, Solution, valid, quality).
A claim C(D) for domain D consists of a set of instances in D.Instance, a quality q in [0,1] and a resource bound r in [0,∞). In summary, a claim C(D) is a triple: (instances, q, r).
Informally, the claim C(D) says that the proposer can take any instance in C(D).instances and calculate a solution of at least quality C(D).q using at most C(D).r resources.
The refutation protocol: the refuter creates an instance p in C(D).instances that is conjectured to be hard to solve by the proposer. The proposer solves p and defends successfully if both quality(p,sol) > C(D).q and the resources consumed < C(D).r. Refutations are central to SCG. In the spirit of Karl Popper, every claim has a precisely defined refutation protocol that must be used to refute the claim.
The game is zero sum. The successful defender wins 10% of the reputation of the refuter. The successful refuter wins 10% of the reputation of the proposer.
To counteract the proposal of trivial claims in the scientific community, there is a second way to oppose: strengthen. Strengthening means to increase C(D).q or decrease C(D).r or both. If the proposer cannot refute the strengthened claim, the proposer will lose 10% of its reputation to the opposer.
There are a few variations of this protocol that are useful. In the early exploration phase of a domain, it makes sense to consider optimal claims: The proposer claims that the refuter cannot find a better solution than the proposer. In this case, there is no need for strengthening and the quality function takes three arguments: Domain.quality: (Domain.Instance, Domain.Solution, Domain.Solution)->[0,1]. The second solution argument is called secretSol and is the solution found by the refuter. The refutation protocol uses a refutation predicate to determine whether the refutation is successful.
The refutation protocol in this case: the refuter creates an instance p in C(D).instances that is conjectured to be hard to solve by the proposer and she finds her secret solution called secretSol. The proposer solves p and defends successfully if both quality(p,sol,secretSol) > C(D).q and the resources consumed < C(D).r.
We consider the Highest Safe Rung problem (HSR): Given a ladder with n rungs and a set of k identical jars, determine the highest safe rung from which to throw a jar without breaking it, using a minimal number of questions. HSR(n,k)=q means that we can find the highest safe rung with q questions. It is an exercise in constrained tree balancing generalizing linear search to binary search and all the shades in between.
We are looking for decision trees of minimal depth to determine the highest safe rung. To explore the domain, we have the scholars use optimal claims. In this phase, they find better ways to balance the trees than their peers. Then we ask them to make absolute claims about how well they can solve the problem, using the standard refutation protocol. For example, HSR(n,2) <= 2 * sqrt(n). Then the scholars go back to the optimal claims and they figure out a way to find the optimal solutions based on rediscovering the modified Pascal triangle where M(q,q) = 2^q. To do well in competitions, the scholars use dynamic programming to efficiently compute the entries in the modified Pascal triangle.
Domain: an instance is a pair (n,k), n a natural number, k <= n. The domain puts an upper bound on the number of rungs, e.g., n < 10000. A solution is a decision tree to determine the highest safe rung. valid((n,k), decisionTree) is a predicate which checks that the decision tree is valid: any path from root to leaf must have at most k left branches. All rungs 0..n of the ladder must appear on the leaves. If a jar breaks on rung n, it breaks on all higher rungs. If a jar does not break on rung n, it does not break on all lower rungs.
The two quality functions are: quality((n,k), decisionTree) = depth(decisionTree)/n. quality((n,k), decisionTree, secretDecisionTree) = if depth(decisionTree) <= depth(secretDecisionTree) then 1 else 0. The proposer claims she can achieve quality 1.
Claim(Domain): ({(25,2)}, 9/25, 5 seconds). In this special case we have a singleton claim. 9/25 is the quality to be achieved within 5 seconds.
For an absolute claim: ({(n,k)}, 2*sqrt(n)/n, 10 seconds). This claim predicts that the depth of the decision tree divided by the number of rungs is at most 2*sqrt(n)/n. The result must be delivered in 10 seconds for ladders with up to 10000 rungs.
We have a tournament with 10 avatars, including Avatar-Alice (developed by Alice) and Avatar-Bob (developed by Bob). The game has been specialized to claims of the form: (n,2) where at most two jars are allowed to break. The first tournament is scheduled for midnight, Jan. 10, 2011 with registration starting 6 hours earlier. The programmers have one week to get their avatars ready. The game engine has created a baby avatar that is given to all competitors. But the baby avatar is simple: it makes only random decisions on what to propose, oppose and provide and uses a linear search decision tree for solving instances. Alice improves her baby avatar by using a better decision tree construction: Instead of stepping through the ladder in steps of one she uses steps of two. This creates decision trees of depth (n/2)+1 instead of depth n with the baby avatar. Bob is more ambitious and instead of stepping through the ladder in steps of two, he uses steps of 3. This creates decision trees of depth (n/3)+1.
The competition starts on-time at midnight with all 10 avatars and will last for a few hours. Unfortunately Avatar-Bob has a bug and loses against all avatars, including Avatar-Alice. Avatar-Alice also loses several matches because other avatars have determined a better algorithm to construct the decision trees. Both Alice and Bob study the game history of the first tournament to try to figure out the algorithmic strategies used by the other avatars.
Alice has an idea: instead of stepping in increments of two, she steps in increments of g and lets g be a function of n, the number of rungs. She thinks that g = log^2(n) is a good choice. Bob has a related idea: He thinks that g = sqrt(n) is a good choice. This results in trees of depth: 2*sqrt(n)-1. In the next competition, it turns out that Bob's choice turns out to be a good one and he wins all matches, except one. In the match, according to the game history, an avatar CLEVER claimed that HSR(25,2) = 7. Avatar-Bob predicted that 2*5-1 = 9 questions are needed. So Avatar-Bob tried to refute but failed. CLEVER produced the decision tree of depth 7.
Before the next tournament, both Alice and Bob studied the behavior of avatar CLEVER that was recorded in the game history. They found that CLEVER seems to have an efficient algorithm to construct optimal decision trees. They try to figure out a new algorithm.
Alice and Bob now work together to try to beat CLEVER. They construct an algorithm based on a modified Pascal Triangle but their avatars still lose against CLEVER because CLEVER is not only constructing optimal decision trees but does so very quickly.
Alice remembers memoization as a general algorithmic technique to speedup algorithms. They add it to their decision tree construction algorithm but CLEVER is still faster and wins again in the next competition.
Finally, Alice figures out a fast iterative algorithm with much smaller memory requirements. In the next competition Avatar-Alice and CLEVER tie in winning the tournament.
This is a story that could easily happen in real games. Notice how SCG induces social engineering leading to innovation.
Management has the option to ask for software with many features by providing an instance 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 instances into subsets of similar instances that have a property that allows for a better, customized solution. For CSP, we partitioned the instances 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).instances consists of one element in D.Instance, are also interesting.
The domain D and claim C(D) definitions directly influence how the crucial solve function (solve: D.Instance-≫D.Solution) 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" instances in C(D).instances 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 provideInstance function. Before an instance is provided, we apply our own solve function to get an estimate for the quality that can be achieved. The goal is to find an instance 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 instances 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 instances.
The quality function expresses how well a solution solves the instance. 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 HSR(n,2) ≤ n, quality is 0, if HSR(n,2) ≤ k * kth root of n, quality is 1-1/k, if HSR(n,2) ≤ 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.