\section{Related Work}
\label{RelatedSection}
The SCG has not grown in a vacuum. We make connections to several related areas.

\subsection{ToDo}

Paper by Sebastian Deterding:
From Game Design Elements to Gamefulness:
Defining Gamification.
MindTrek 11, ACM.
Augmented reality games that use digital devices
to overlay game representations over the environment [50].

From Wikipedia: Education and AR:

Augmented reality applications can complement a standard curriculum. Text, graphics, video and audio can be superimposed into a students real time environment. Textbooks, flashcards and other educational reading material can contain embedded markers that, when scanned by an AR device, produce supplementary information to the student rendered in a multimedia format.[59][60][61] Students can participate interactively with computer generated simulations of historical events, exploring and learning details of each significant area of the event site.[62] AR can aide students in understanding chemistry by allowing them to visualize the spatial structure of a molecule and interact with a virtual model of it that appears, in a camera image, positioned at a marker held in their hand.[63] Augmented reality technology also permits learning via remote collaboration, in which students and instructors not at the same physical location can share a common virtual learning environment populated by virtual objects and learning materials and interact with another within that setting.[64]

[64] Collaborative Augmented Reality in Education
by Hannes Kaufmann

Connection between augmented reality and SCG.
For learning: Students pose problems to each other and solve them.
Structured scientific discourse.

intrinsically motivating instruction by Tom Malone
http://mailer.fsu.edu/~jkeller/EDP5217/Library/Curiosity%20&%20Attention/Attention/Malone(1981)%20Intrinsically%20Motivating%20Instruction.pdf



which book by Dan Pink should we reference?
If what he says is right, SCG will be a big thing
when little or no monetary rewards are offered.


Dan Pink's three principles Purpose, Mastery, and Autonomy. I think there could be several ways to map these three principles onto SCG. Here is my shot:

Mastery : of knowledge about a particular problem solving domain (i.e. how to find (good) solutions to problem instances, what are the hard instances?) Mastery is manifested by the ability to provide harder to falsify claims about players ability to solve problem instances as well as the ability to spot problems in other players claims. 

Autonomy : Players are free to choose the claims they propose. There are several restrictions on autonomy imposed by the game as well. For example, players don't choose the claims they want to dispute. Players do not choose their
action time. Claims proposed by the players are restricted by the lab designer.

BUT: the players choose the lab they want to play in
(out of thousands of labs).

Also players should have a way to interact with
lab designers to propose modified labs.

==================

SCHECHTER, S. E. How to buy better testing: using
competition to get the most security and robustness for your
dollar

BACON, D., CHEN, Y., PARKES, D., AND RAO, M. A
market-based approach to software evolution. OOPSLA Â9:
Proceeding of the 24th ACM SIGPLAN conference companion
on Object oriented programming systems languages and
applications (2009).

\subsection{Crowd Sourcing and Human Computation}

There are several websites that organize competitions.
What is common to many of those competitions? We believe that 
the SCG provides a foundation to websites such as
TopCoder.com
%TopCoder \cite{TopCoder} 
or kaggle.com.
%which is more specialized.

The SCG makes a specific, but incomplete proposal of a programming interface to
work with the global brain
\cite{Bernstein:2012:PGB:2160718.2160731}.
What is currently missing is a payment mechanism for 
scholars and an algorithm to split workers into
pairs based on their background.

The SCG is a generic version of the ``Beat the Machine'' approach
for improving the performance of machine learning systems
\cite{attenberg2011beat-ipeirotis}.

Scientific discovery games, such as FoldIt and EteRNA,
are variants
of the SCG.
\cite{Cooper:2010:CDS:1822348.1822354} describes the
challenges behind developing scientific discovery games.
\cite{Andersen:2012:ITG:2207676.2207687} argues that complex
games such as FoldIt benefit from tutorials.
This also applies to the SCG,
but a big part of the tutorial is reusable
across scientific disciplines.

\subsection{Logic and Imperfect Information Games}
Logic has long promoted the view
that finding a proof for a claim is the same as finding a defense strategy
for a claim.


Logical Games
\cite{LogicalGames}, 
\cite{sep-logic-games}
have a long history going back to Socrates.
The SCG is an imperfect information game which builds on 
Paul Lorenzen's dialogical games \cite{sep-logic-dialogical}.

\subsection{Foundations of Digital Games}

%According to Jonas Linderoth
%\cite{exploratory-performatory} 
%games challenge two aspects of human nature: our ability to choose appropriate actions and our ability to perform appropriate actions.
%\cite{exploratory-performatory} views 
% gaming as a cycle between interrelated
% exploratory and performatory actions.
%
%What are the exploratory and performatory actions in SCG?
%Exploratory actions are: (1) proposing a claim which means choosing from a set of claims.
%(2) Choosing an action: refute, agree or strengthen a given claim.
%Performatory actions are: (1) the proponent should defend the proposed claim.
%(2) If an opponent decides to refute, he should succeed in refuting, etc.
%In SCG we also have a cycle of interrelated exploratory and performatory actions.

A functioning game should be deep, fair and interesting which requires careful
and time-consuming balancing.
\cite{AIIDE125470} describes techniques used for balancing that complement
the expensive playtesting. This research is relevant
to SCG lab design. For example, if there is an easy way to refute claims
without doing the hard work, the lab is unbalanced.
%SCG has the interesting property that 
%if a ``clever procedure'' is known
%to scholar Alice but, not to scholar Bob, Alice can easily win over Bob.
%If both know the clever procedure, the game is a tie.
%The goal of an SCG lab is to discover such a clever procedure.

\subsection{Architecting Socio-Technical Ecosystems}

This area has been studied by James Herbsleb and the
Center on Architecting Socio-Technical Ecosystems (COASTE) at CMU
http://www.coaste.org/.
A socio-technical ecosystem supports straightforward
integration of contributions from many participants
and allows easy configuration.

The SCG has this property and provides a specific 
architecture for building knowledge bases in
(formal) sciences. 
Collaboration between scholars is achieved through
the scientific discourse which exchanges instances
and solutions. The structure of those instances and solutions
gives hints about the solution approach. An interesting
question is why this indirect communication approach
works.
% so well.

The NSF workshop report \cite{ScacchiNSFReport} discusses socio-technical innovation
through future games and virtual worlds.
The SCG is mentioned as an approach to make the scientific method 
in the spirit of Karl Popper available to CGVW (Computer Games and Virtual Worlds).

\subsection{Online Judges}

An online judge is an online system to test programs in programming contests.
A recent entry is \cite{Petit:2012:JEP:2157136.2157267} where private inputs
are used to test the programs. 
%\cite{TopCoder} 
Topcoder.com includes an
online  judge capability, but where the inputs are provided by competitors. 
This dynamic benchmark capability is also expressible with the SCG: 
The claims say that for a given program, all inputs
create the correct output. A refutation is an input which
creates the wrong result.

\subsection{Educational Games}
The SCG can be used as an educational game. One way to create adaptivity for learning
is to create an avatar that gradually poses harder claims and instances.
Another way  is to pair the learner with another learner who is stronger.
\cite{Andersen:2012:OAE:2282338.2282398} uses concept maps to guide the learning.
Concept maps are important during lab design: they describe the concepts that need
to be mastered by the students for succeeding in the game.

\subsection{Formal Sciences and Karl Popper}
James Franklin points out in
\cite{Franklin1994-FRATFS}
that there are also experiments in the formal sciences. One of them is the `numerical
experiment' which is used when the mathematical model is hard to solve.
For example, the Riemann Hypothesis and other conjectures have resisted proof
and are studied by collecting numerical evidence by computer.
In the SCG experiments are performed when the refutation protocol is elaborated.

Karl Popper's work on falsification
\cite{nla.cat-vn1027910}
is the father of non-deductive methods in science.
The SCG is a way of doing science on the web according to Karl Popper.

\subsection{Scientific Method in CS}

Peter Denning defines CS as the science of information processes
and their interactions with the world \cite{Denning:2005:CSS:1053291.1053309}.
The SCG makes the scientific method easily accessible by expressing the
hypotheses as claims.
Robert Sedgewick in \cite{ScientificMethodProgramming} stresses the importance of
the scientific method in understanding program behavior.
With the SCG, we can define labs that explore the fastest
practical algorithms for a specific algorithmic problem.

\subsection{Games and Learning}
Kevin Zollman studies the proper arrangement of communities of learners
in his dissertation on network epistemology \cite{Zollman2007-ZOLTCS}.
He studies the effect of social structure on the reliability
of learners.

In the study of learning and games the focus has been on learning
known, but hidden facts.
The SCG is about learning unknown facts, namely new constructions.

\subsection{CSP-based Game Design}
CSP is increasingly being used in the procedural content generation (PCG) community, although not in industry.
For example,
Tanagra\cite{Smith:2010:TML:1822348.1822376} uses a numerical constraint 
solver to guarantee level playability.
In addition, Magy El-Nasr
used constraint solving for lighting and adaptive systems for games
\cite{El-Nasr:2004:ALD:1008213.1008238}.


\subsection{Origins of SCG}

A preliminary definition of the SCG was given in a keynote paper
\cite{scg-bionetics}.
\cite{scghome} gives further information on the \SCGp.
The original motivation for the SCG came from the two papers with Ernst Specker:
\cite{jacm-81} and the follow-on paper
\cite{lieber-specker:partial-2}.
Renaissance competitions are another motivation: the public problem solving duel between Fior and
Tartaglia, about 1535, can easily be expressed with the SCG protocol language.

\section{Future Work}
\label{FutureWorkSection}
We see a significant potential in putting the refutation-based Scientific Method 
into the cyberinfrastructure and make it widely available.
We plan to, iteratively, improve our current implementation
based on user feedback.

We see an interesting opportunity to mine the game histories and make suggestions
to the scholars how to improve their skills to propose and defend claims.
If this approach is successful, the SCG will make contributions to computer-assisted 
problem solving.

\section{Summary and Conclusions}
\label{ConclusionSection}
The SCG provides a simple interface to 
a community that uses the (Popperian) Scientific Method.
The SCG provides for effective
customization of the generic scientific machinery 
by using lab definitions. Since the SCG models
a scientific community it is a broad enabling tool for innovation and learning
%widely applicable
and deserves a central place in the world's cyberinfrastructure
and serious games world.
We believe that the game design approach we outline in this paper
has many applications to other games.
We start with a game goal and translate
it into a blame assignment for moves 
that are inconsistent with the design goal.
Then we derive a payoff function
that is fair, sound and competitive.
Such a systematic approach eliminates a lot of game testing because
we know that many properties are formally guaranteed.

{\bf Acknowledgments:} We would like to thank 
% Ahmed Abdelmeged,
Bryan Chadwick, Magy Seif El-Nasr, David Lazer, Rory Smead,
Abraham Bernstein and Gillian Smith for their input and
feedback on the paper.


%\section{Future Work}

%There is one aspect missing in SCG: timing. In science the first
%proponent and defender of an idea gets special credit. Also those scholars
%who provide stepping stones for others get credit (citation counts).

%Proposal:
%Use timestamps for all proposals, refutations, defenses and strengthenings.
%Do a retrospective of a competition or a series of competitions.
%
%Compute first times:
%
%First time a claim is proposed, refuted, defended or strengthened.
%
%Reward first scholar if the refuted claim is false.
%
%Reward first scholar if the proposed or defended or strengthened claim is true or optimal. 
%
%
%true, false, optimal may have uncertainty: true = mostly defended.
%false = mostly refuted.
