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 game is summarized in the Bionetics 2010 Keynote Slides and the Bionetics 2010 Keynote Paper.
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.
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.
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.
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.