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.
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
A solution has a quality between [0,1].
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.
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.
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.
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.
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.
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
(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
The avatar ranking produced by the tournament will tell.
Can we build a learning avatar that will learn as fast as a human?