This guide is written for teachers, editors, recruters, and software managers who want to use SCG and define new playgrounds and to call for games taking place in those playgrounds. The playground is to be used by students, researchers, potential employees and software developers or their avatars. The intent is to educate, innovate (through crowd sourcing of small intelligent crowds), or evaluate. SCG is parameterized by a domain D and a set of claims based on D. The playground designs described are submitted to an SCG arena to define a new game to take place in the arena. Students either register themselves or their avatars for the next tournament to determine who has the best skills.

Instance = (n,k) Solution = binary decision tree valid: has n+1 leaves labeled 0, 1, ... n. ... quality: depth of decision tree / n

Instance = (n0,C) Solution = n valid: n>n0 quality: irrelevant

Instance = indirected graph G = (V,E) Solution = subset S of V valid: S is independent set quality: |S|/|V|

Instance = X Solution = Y valid: y in Y(x)? quality: irrelevant

It is important that claims don't have to mathematical. Mathematical claims are expressed in predicate logic and potentially we can prove them to be either true or false. Because we need a more powerful notion of claim to make SCG interesting we define a claim using a general protocol to determine whether a refutation is successful, in the sense of Karl Popper.

A protocol consists of a data gathering algorithm involving Alice and Bob and a predicate that determines the outcome of the refutation protocol. The data gathering algorithm is of the form (Alice (data) Bob(data))+ or (Bob(data) Alice(data))+. The predicate gets all the data for evaluation. We distinguish between defense and refutation predicates. Alice always makes the claim and Bob tries to refute.

setOfInstances = (n,k) (singleton) q = number of questions needed protocol: Bob((n,k)) Alice(decision tree DT for n,k) defense = valid((n,k),DT) and depth(DT) <= q/n

setOfInstances = (n,k) (singleton) q = number of questions needed r = irrelevant protocol: Alice((n,k)) Bob(decision tree DT for n,k) refutation = valid((n,k),DT) and depth(DT)<= q/n

setOfInstances = {(n0,C)} q = irrelevant protocol: Alice(n0,C)) Bob(n) defense = n>n0 and f(n) <= C*g(n)

setOfInstances = {(n0,C)} q = irrelevant protocol: Bob (n0,C)) Alice(n) refutation = n>n0 and f(n) <= C*g(n) Exercises: HSR(n,2) in O(n) HSR(n,2) not in O(log(n)) HSR(n,2) in O(n^(1/2)) n^(1/2) not in O(log(n))

setOfInstances = {G=(V,E)} q = 0.9 of secret solution r = running-time <= |E|^2 protocol: Alice (G=(V,E),secret sA = Alice' solution) Bob(sB = Bob's solution) defense = |sB|/|sA| >= 0.9

setOfInstances = X q = irrelevant r = time protocol: Bob(x) Alice(y) defense = predicate(x,y)

setOfInstances = X q = irrelevant r = time protocol: Alice(x) Bob(y) refutation = predicate(x,y)Both HSR and Landau are mathematical claims.

Alice' claim C1-pos(setOfInstances, q, r) means that if Bob gives her an instance p in setOfInstances she will find a solution of quality q using resources r.

The complement of this claim is: C1-neg(setOfInstances,q,r) means that Alice can find an instance p in setOfInstances so that Bob cannot find a solution y of quality q within resource bound r. Note that such a solution y might exist but the calim says that it is "hard" to find.

protocol C1-pos: Bob(x) Alice(y) defense = predicate(x,y)is translated into

protocol C1-neg: Alice(x) Bob(y) refutation = predicate(x,y)The simple rule for claim negation is: the domain stays the same and, in the protocol, the roles of Alice and Bob are reversed and a defense is changed into a refutation.

Alice claims C, Bob tries to refute. Claim is of the form: Exists x in X ForAll y in Y(x): p(x,y). Refutation protocol: Alice provides x, Bob provides y.

If C true and Bob refutes, then Alice is careless. We call this accidental refutation.

If Alice defends C, and Bob is perfect then C is true.

If Bob refutes C, and Alice is perfect then C is false. Bob found a counterexample.

If C is false and Alice defends, then Bob is careless. We call this an accidental defense.

Alice claims C, Bob tries to refute. Claim is of the form: ForAll x in X Exists y in Y(x): q(x,y). Refutation protocol: Bob provides x, Alice provides y. The analysis is similar to the one above.

"If Bob perfect, we have a proof that C is true." can be replaced by: "the stronger Bob is, the more likely it is that the claim is true." A similar statement applies to Alice.

For EA claims: a successful defense might be a big step towards a proof. For AE claims: a successful refutation might be a big step towards a proof of the negation.

Consider the following scenario: You and your partner play with claims C and !C. C always gets defended while !C always gets refuted. This is an indication that you should try to prove C. Example: n^(1/2) in O(n/log(n)).

How can carelessness happen in HSR?

In the SCG/Board, the TA or the SCG/Board tool deducts points for carelessness and in SCG/Avatar, it is the administrator that makes the deduction.