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 SCG involves proposing and opposing computational hypotheses 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 hypothesis has the flavor of a belief about X and has a confidence. A hypothesis proposed by agent Alice makes a prediction about the behavior of Alice' algorithm solving problems in a niche. Alice' hypothesis should be hard to strengthen and it must be easy to check, given witnesses, whether the hypothesis 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.
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 hypotheses are collected.
Reputation is zero sum. The confidence expresses the proposer's likelihood that it will not lose reputation when another agent tries to oppose the hypothesis. The agents start the game with an initial reputation. The gain or loss in reputation is proportional to the confidence of the hypothesis 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. Hypotheses 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 hypotheses 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 hypotheses in this domain, and how to create hard hypothesis 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 hypotheses, the game is about analyzing the hypotheses. This requires specific mathematical and algorithmic skills. For example, for the Maximum Boolean CSP with relation set hypotheses, 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.