Scientific Community Game (SCG) for Algorithms
Asymmetric and Direct SCG
We use an informal version of SCG where the players are humans (as opposed to programs)
and where precise English definitions
are sufficient so that all parties: the two virtual scientists and
the administrator and the chief scientist can agree.
Innovation is done in teams of three with a fourth member, the chief scientist,
setting the subject, called a niche of problems to be solved. The two virtual scientists, Alice and Bob, make little discoveries
and communicate them as problem solving techniques and their execution
on specific problems. The administrator, called Nina,
supervises Alice and Bob. Nina is a trusted intermediary who gets to know about
Alice and Bob's solution techniques and secret solutions.
But Nina hides those reliably from the other party.
Nina needs to know Alice' and Bob's secrets so that she can verify Alice' and
Bob's claims.
Algorithm Instantiation for Learning and Innovation
SCG is used for learning about algorithms and their analysis.
This involves first doing small "innovation" steps that have been done the first time
many years ago and then combining those "innovation" steps in novel
ways to solve new algorithmic challenges.
At least initially, we use Asymmetric and Direct SCG because students
need to learn about high level algorithm design and analysis
without having a detailed implementation.
The disadvantage of the direct approach is that students are involved in
executing the game. It does not happen automatically at the press of a button
as with the indirect version of SCG where the virtual scientists are played by
software.
Later in the course, we will use one
software implementation of the virtual scientists to
execute competitions at the press of a button.
And we will go through the innovation cycle a few times.
How we use SCG
We divide the class into x teams of 3 students playing the roles
(virtual scientist, virtual scientist, administrator).
The 3 communicate in English using Google Wave.
The administrator checks the 2 two virtual scientists and
the virtual scientists check the administrator.
If the 3 ever get into a fight (they disagree about which of the virtual scientists
won),
we will do an algorithm/analysis review in class.
We play direct SCG with multiple rounds and after each round,
algorithms and analysis may be improved to respond to problems
encountered in previous rounds.
In the virtual scientist role, students accumulate reputations.
We will focus on prediction reputation where the virtual scientist
with the best algorithm and best analysis wins.
To win, the students must provide clear, correct algorithms, they must analyze them
and compare their analysis with the analysis of other students.
They must make analysis statements about their algorithms that they can support
when executing their algorithms on the problems provided by the other virtual scientist.
They must find hard problems for the other virtual scientist to solve
within the prediction/analysis they made.
Why using SCG
Computer Science is a science and algorithms are an important part of this science.
The communication between students gets channeled through the game to specific
algorithmic problems and the amount of student communication increases
significantly. Students get frequent feedback on their algorithmic decisions.
They learn experientially about algorithms and their analysis.
Your peers will tell you when your algorithm is wrong by giving a specific
input where it misbehaves.
Your peers will tell you when your analysis is wrong again by giving you
a specific input where there is a mismatch.
Benefits of using SCG
We use an algorithm incarnation of SCG where the learning objectives are:
(1) Learning to design algorithms that are correct and efficient.
(2) Describing algorithms and reasoning about their correctness.
(3) Analyzing algorithms and reasoning about the correctness of the analysis.
Analyzing an algorithm is about predicting how the algorithm
will behave on a set of inputs having the same feature.
The reasoning part involves both proving correctness and finding counterexamples
if the algorithm is not correct.
Running the algorithm is only possible on small examples because it
is done manually in this version of SCG.
Algorithm development is about producing correct algorithms that use
minimal resources (of which time is a very important one).
Disadvantages of using SCG
The students need to learn the rules of a scientific community
and apply it to a scientific algorithm community.
There is the "learning the game" overhead but the rules of
a scientific community are useful to know for numerous scientific fields.
How Algorithm SCG works
We have two virtual scientists Alice and Bob, an SCG administrator Nina
and a chief virtual scientist Karl.
The game is played through structured messages that are exchanged using
Google Wave.
The chief virtual scientist determines the topic of the game: a niche X
of some problem domain depending on which algorithm design problem
is in the syllabus.
Both Alice and Bob design their best algorithms for X and they analyze them.
The analysis must be of the form requested by the chief scientist, e.g.,
compute an upper bound on the number of primitive operations needed to
solve the problem as a function of its input size.
Alice and Bob send their prediction function to Nina which passes it on to the other party.
Alice analyses the prediction function of Bob and vice versa.
Both Alice and Bob define 2 problems in niche X. They try to make challenging
problems for their opponent so that the opponent will have a hard time to satisfy their
prediction.
Summary of steps:
Chief scientist defines niche X.
Alice defines algorithm AliceAlg and sends prediction function AlicePredict to Nina.
Bob defines algorithm BobAlg and sends prediction function BobPredict to Nina.
(In some applications AliceAlg and BobAlg also need to be shared
so that Nina can check what Alice and Bob claim.)
Nina sends AlicePredict to Bob and BobPredict to Alice.
Alice sends c1 problems in niche X with Alice' solution to Bob through Nina.
Bob sends c1 problems in niche X with Bob' solution to Alice through Nina.
Nina hides the secret solution of Alice.
Nina hides the secret solution of Bob.
Alice solves Bob's problems and sends results to Nina.
Bob solves Alice' problems and sends results to Nina.
Nina determines winner at both levels: solution quality and prediction quality.
Based on the outcome, Alice and Bob improve their algorithm for the next round.