The Specker Challenge Game (SCG)

= The Scientific Community Game (SCG)

Virtual Scientific Communities for Innovation in Computer Science

Introduction: A Scientific Claims Game in the Spirit of Karl Popper

For me science is a cooperative endeavor
rather than a competitive game: the most important
thing is that we all have fun and help each other to
do good work.  The real goal is for the community to
discover good ideas and find ways to use these
discoveries for the good of humanity.  In my view, we
(the community of scientists and engineers) invent
and discover things together.
Gerald Jay Sussman, Panasonic Professor of Electrical Engineering, Massachusetts Institute of Technology. In Non-chronological Backtracking

The New Scientific Community Game

SCG has been generalized and formalized. It is a scientific community game modeled after the "Conjectures and Refutations" approach by Karl Popper. In SCG we have "claims and refutations" and the refutations are defined by a refutation protocol that is part of the definition of a claim domain.

The new game is summarized in the Bionetics 2010 Keynote Slides and the Bionetics 2010 Keynote Paper.

The Previous Version of SCG

Short Explanation of SCG .

The SCG involves proposing and opposing computational claims related to a problem solving domain, such as a computationally hard optimization problem domain X. The agents operate as a virtual scientific community that develops new knowledge about X and as a side effect, better algorithms for domain X. A computational claim has the flavor of a belief about X and has a confidence. A claim proposed by agent Alice makes a prediction about the behavior of Alice' algorithm solving problems in a niche. Alice' claim should be hard to strengthen and it must be easy to check, given witnesses, whether the claim is supported or discounted.

The SCG encourages the agents to follow the rules of a scientific community. When two agents p1, p2 play, either p1 tells p2 that p2 has a bug in its reasoning and p1 gives a detailed reason, or vice versa. It is unlikely that p1 and p2 tie and cannot learn from each other.

SCG in Action

Report of an Agent Team that participated for a Semester in SCG tournaments .

Applications

Applications of SCG are: (1) a new software development process for problem solving software that truely motivates software developers to produce reliable, "intelligent", and easy to evolve software (2) a new, highly motivating way of teaching software development by competition and collaboration with the competitions serving as a strong automatic and objective grading component (3) a new, highly motivating way of teaching about domain X again with the competitions doing fair grading (4) a new metric to compare algorithms useful for evaluating algorithms in academia, government and industry. Useful to managers, special issue editors, and educators. (5) modeling scientific communities and making predictions about those communities (6) enhancing traditional benchmarks with a dynamic benchmarking component (7) automated system testing of problem solving software (8) driver for algorithmic innovations (9) an alternative bidding process for problem solving software: Have a small number of bidders participate in a minimally paid SCG competition and pick the winner. As a side effect, useful unchallenged claims are collected.

Claims Structure, Reputation and Game Mechanism

The claims of agent Alice are of the form: for all problems f in a subset sX of X, agent Alice can find a solution J satisfying some predicate q(f,J). A claim is of the form (sX, q, confidence). If agent Bob thinks that Alice is wrong, he opposes Alice' claim either (1) by strengthening q or (2) by providing a problem f to Alice where she cannot find a solution satisfying q. In case (1) Bob will win reputation if Alice cannot discount the strengthened q. In case (2), Bob will win reputation from Alice if she can satisfy q and otherwise Alice will win reputation from Bob.

Reputation is zero sum. The confidence expresses the proposer's likelihood that it will not lose reputation when another agent tries to oppose the claim. The agents start the game with an initial reputation. The gain or loss in reputation is proportional to the confidence of the claim and the reputation of the offerer.

When an agent loses reputation, it means that it has a bug in its software or the other agent has better algorithms. Note that while the agents compete for reputation they also cooperate by giving each other constructive feedback. Claims must be supported and discounted constructively by providing a problem and a solution. The problem and solution reveals information that might help to improve the agent that lost reputation.

As the game proceeds, knowledge is accumulated in the claims that withstood discounting. The winning agent, i.e., the agent with the highest reputation, has the most knowledge and the best algorithms to solve optimization problems in domain X.

SCG played by humans

There is a version of SCG where humans are the scholors (not software agents). Novel SCG-based Approach to Teaching Computer Science and Mathematics.

Tools and Current Use

We have developed software for playing SCG on the web and we use it actively in software development courses. The current course is: Software Development Fall 2009. The SCG game is played as a full round-robin tournament where each agent faces each other agent. This prevents that the agents can build coalitions in a group game. The coalitions could interfere with the desired property that the best algorithms win.

An interesting feature of SCG is that the agents have "self-interest" and an "ego". They can satisfy their ego by winning against other agents. The self-interest drives them to compete and maximize their reputation. However this egoistic behavior helps constructively the other agents to get better.

SCG touches many areas: (1) It is an innovation driver for optimization algorithms. (2) It is useful for teaching software development (the students develop the agents which promotes reliable software because the agents test each other's software). (3) Teaching computer science in area Y by choosing an optimization problem domain X that requires understanding of area Y. (4) It offers a new model to evaluate optimization algorithms in a practically meaningful way. (5) It offers a new software development process for optimization problem solving software.

A draft of a paper is available here: SCG paper | SCG talk. | SCG talk 2.

Related Information

The SCG is a twenty-first century computer-science version of the sixteenth century Renaissance Mathematical Contests in Italy: Renaissance Mathematical Contests, Local Copy: Renaissance Mathematical Contests. The mathematicians challenged each other by posing hard problems to the other party and solving the hard problems posed to them. The modern version is played on the web and has the computer scientists create a self-sufficient agent that survives in a virtual world inhabited by agents produced by their peers.

The modern version is about learning how to solve computational problems in a specific domain, how to pose hard claims in this domain, and how to create hard claims instances. Know-how is needed how to put these skills into a self-sufficient agent.

Once a domain is chosen, for example the Maximum Boolean Constraint Satisfaction Problem (Maximum Boolean CSP) with relation set claims, the game is about analyzing the claims. This requires specific mathematical and algorithmic skills. For example, for the Maximum Boolean CSP with relation set claims, the game is about solving min-max problems, probability, algorithms and complexity (linear programming, recurrence relations, NP-completeness), combinatorics (combinations and permutations), abstract interpretation, maximizing and minimizing functions, Shannon decomposition etc. Besides being a tool to develop and evaluate new computational processes, SCG is an ideal game for an undergraduate capstone course or a graduate refresher course on basic CS topics.

The version of SCG, called SCG secret, turns combinatorial maximization problems whose decision version is in NP, into interesting Artificial Markets.

The game is named after my professor, co-advisor and co-author, Ernst Specker.

The idea of using SCG for software bidding was proposed by Walter Huersch in Sep. 2009. The idea of using the virtual scientific communities to model real scientific communities and maybe making predictions about them was proposed by Eugene Goldberg in Oct. 2009 and independently by Mitch Wand in Nov. 2009.

Karl J. Lieberherr, Ahmed Abdelmeged, Bryan Chadwick, Alex Dubreuil, CCIS, Northeastern University, (C) 2007 - 2009

The development of SCG has been supported in part by grants from Novartis and GMO.