The Scientific Community Game

by Karl Lieberherr, Ahmed Abdelmeged and Yue Liu and members of the "Spring 2011 Managing Software Development CS 5500" class.

The Scientific Community Game (SCG) is a family of scientific games parameterized by a playground occupied by scholars. The playground defines the domain of scientific discourse as well as the argumentation that must be used by the scholars to defend and refute their claims. The scholars are constructive virtual beings: they like to turn problem instances or raw materials into high quality solutions or products and make predictions about the quality of their solutions or products.

Domain

A scientific domain is defined by Instance and Solution. The set of instances is called Instance. Elements in Instance are solved and yield a valid solution in Solution. A solution has a quality between [0,1].

Examples of Instance / Solution: Raw Materials / Product, Algorithm / Input, Number / Graph, Network / Flow, Expression / Assignment, Number / Number, Graph / Path, Numbers / Decision Tree, Terrain / Trajectory, Program / Type Error, Program with Spec / Correctness Proof.

The claims the scholars make are typically about sets of instances but can also be about a singleton instance. Sets of instances are defined by InstanceSet, also defined in Domain.

Example

Domain: MinMax. The objective of MinMax is to have a simple calculus example. Maximal strengthening requires calculus skills. The Claim C-pos(t) is defined by: ForAll [x a real number in [0,1]] Exists[y a real number in [0,1]] (x*y + (1-x)*(1-y^2)) >= t. t in [0,1] is a real number. C-pos(t) is true for t=0 and false for t=1 and there is one number where it switches which is (sqrt(5) - 1)/2.

The domain is called MinMax, because Bob will try to find an x0 so that (x0*y + (1-x0)*(1-y^2)) is minimum for the maximum y and Alice will try to find a y0 so that (x0*y0 + (1-x0)*(1-y0^2)) is maximum. Bob tries to minimize and Alice tries to maximize.

Instance = [0,1] real numbers. Solution = [0,1] real numbers. InstanceSet = [0,1] real numbers.

Protocol

Orthogonal to domains are protocols. While a domain defines what the scholars talk about, a protocol defines the order of scientific discourse and who defends or refutes a claim. Protocol is parameterized by Instance and Solution and it is specified by a protocol definition language. Several predefined protocols are available.

Example

In mathematical form, the protocol is: ForAll [x in Instance] Exists[y in Solution] p(x,y). If Alice is the proposer, and Bob tries to refute,

instance x from Bob
solution y from Alice
!p(x,y) means that Bob refuted successfully.

Claim

A claim is built on a domain and a protocol. A claim includes an instance set, a protocol about how to exchange instances and solutions and, a quality and a confidence. Some claims are mathematical and correspond to predicate calculus statements. For mathematical claims it is often possible to find a winning strategy (proof), showing that a claim has never a refutation. For other claims, the game has to be played.

Example of mathematical claim

Alice claims Claim C-pos(t): ForAll [x in [0,1]] Exists[y in [0,1]] (x*y + (1-x)*(1-y^2)) >= t. t in [0,1] is a real number. C-pos(0.55) is true but not strong enough. The same for C-pos(0.60). C-pos(0.65) is wrong and can be refuted. Where is the switch-over point from true to false? Answer: t = (sqrt(5) - 1)/2. An exercise in calculus.

Playground

A playground is based on one domain (with one instance set), one or more protocols and one or more claim kinds. The playground also defines a baby avatar if the role of scholar is played by software.

Example of mathematical playground

Domain = MinMax Claim 1: C-pos(t). Claim 2: C-neg(t) (the negated version of Claim 1, automatically generated).

ROI for SCG

A significant, multi-year investment has gone into the development of the generic SCG software culminating in the "Spring 2011 Managing Software Development" course that implemented the current system. Thanks to this investment into the generic software there is, we claim, a significant benefit to users of SCG, be they playground designers or scholars.

ROI for playground designers

Why would a teacher or editor or manager develop a playground? With a small investment of defining a few languages and simple functions, the playground designer gets: (1) a virtual world that fosters innovation and experiential learning in the scientific domain of interest, (2) a focused scientific community where the scholars both collaborate and compete, (3) a knowledge maintenance system. As byproduct of the scientific discourse, the scholars will agree on claims. Those are claims that are candidates for truth modulo the strength of the participating scholars, (4) once a playground has been designed, it is easy to design more because they all follow the same pattern. The playground design knowledge is quickly amortized.

ROI for scholars or avatar designers

Why would a student or researcher participate as a scholar or avatar developer? (1) There is an immediate reward for clever innovations that help to solve the instances more efficiently or with better quality, (2) SCG provides a second order learning environment where what a scholar does has to be taken seriously by all other scholars, (3) it is fun to learn and innovate and try to figure out the clever techniques that others use, (4) even an unknown scholar has a chance to come up with an innovation and prove its value by beating the other scholars in the game, (5) the SCG rules knowledge is quickly amortized because all games follow the same rules.

Interesting AI Experiment:

We have a playground with several learning baby avatars, plus one strong or even perfect avatar. Can the learning avatars learn the behavior from the strong avatar? Which avatar has the best learning algorithm? The avatar ranking produced by the tournament will tell. Can we build a learning avatar that will learn as fast as a human?