Scientific Community Game Playground Designer Guide

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 with 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 SCG Game Courts to define a new game to take place in the Game Courts. Students either register themselves or their avatars for the next tournament to determine who has the best skills.

The definition of a playground includes: (1) a domain definition that specifies the problem to be solved, (2) a claim set definition the claims of which specify how well niches of instances of the problem are claimed to be solved, including a refutation protocol that precisiely defines successful refutation of a claim in the sense of Karl Popper (3) a strengthen predicate on pair of claims. Karl Popper's ideas a reasonably summarized here (from Carla Fehr's web page): http://www.ccs.neu.edu/home/lieber/evergreen/specker/scientific-method/Popper-Carla-Fehr.html

There are two kinds of SCG: SCG/Avatar (where avatars developed by humans play the role of scholar) and SCG/Board (where humans play the role of scholar). This document is written for SCG/Avatar but much of it also applies to SCG/Board.

Domain

Computational Problems and Instances

Example HSR

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

Example Landau (O notation)

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

Example Independent Set

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

Domain for mathematical Claim: ForAll Exists

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

Example Boolean MAX CSP

Instance = CSP formula = set of integer weighted constraints using Boolean relations.
Solution = assignment to the variables in a CSP-formula.
valid: assignment is total.
quality: fraction of satisfied weighted constraints.

Claim(Domain)

It is important that claims don't have to be 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.

Strengthen Relation

Besides the domain and claim set definitions, a third important component is the strengthenP relation which is a relation between two claims. strengthenP(C1,C2) means that claim C2 is stronger than claim C1.

Example HSR: claims and strengthening

positive: HSR(n,k) <= q

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

negative: HSR(n,k) > q

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

Example Landau (O notation)

positive: f(n) in O(g(n))

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

negative: f(n) !in O(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))

Example Independent Set

positive: Bob can efficiently approximate Alice' solution within 0.9.

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

Mathematical Claim: ForAll Exists

positive

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

negative

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

Example Boolean MAX CSP

Alice(CSP formula f, secret solution SA for f)
Bob(solution sB for f)

Protocol Negation and Complement of a Claim

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)

protocol C1-neg:
  Alice(x) Bob(y)
  refutation = predicate(x,y)

Special case: Mathematical claims and accidental defenses and refutations

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.

Baby Steps Towards Proofs

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)).

Careless Scholars

How can carelessness happen in HSR? Alice claims HSR(9,3)<=3 which is a wrong claim. Alice defends it because Bob does not find the bug in Alice decision tree. But the Admin will find the bug and kick Bob out of the game. It is a violation of SCG rules not to compute valid and quality correctly. Alice' reputation is reduced before Bob is kicked out.

Avoidable Accidental Defenses

Avoidable Accidental Defense of False Claim

Avoidable Accidental Defense of True Claim

In the SCG/Board, the TA or the SCG/Board tool deducts points for carelessness and in SCG/Avatar, it is the administrator that detects an SCG rule violation and kicks the avatar out of the game.

Skill-related Accidental Defense and Refutation

Defense of False Claim

Refutation of True Claim

Protocol Kinds

Standard Positive

Standard Negative

Secret Positive

Secret Negative

Renaissance

Baby Avatar Generation