SCG: A Novel Tool for Computer Science
SCG is a scientific market game where agents with reputations offer, accept, deliver, and solve challenges. It is a valuable tool for computer science research and learning.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Specker Challenge Game (SCG): A Novel Tool for Computer Science Karl Lieberherr
SCG: a scientific market game Domain X (Problem Solving domain such as an NPO domain) Agents with a reputation: offer-accept-deliver-solve Agents offer challenges with a confidence Agents accept challenges Discounting protocol for challenges: deliver-solve Agent wins reputation when it accepts and discounts a challenge of another agent (challenge confidence * offerer reputation * at-risk). when it supports its own challenge that was accepted by an agent (challenge confidence * acceptor reputation * at- risk).
Think of a scientific community about domain X Scientists have reputations Scientists offer statements with a confidence Scientists question statements (accept) Scientists use discounting protocol (deliver- solve) Scientists win and loose reputation
What is a scientific artificial market game good for? Market works at the press of a button to determine the winner. The winner has the best skills in the chosen domain. Evaluation tool. The feedback is constructive. Testing and Learning Tool. Grading Tool. Over time, the market will collect undiscounted challenges: Belief Maintenance System. Agents must be reliable: Teaching Software Engineering Tool. Grading Tool.
Example: SCG(MAXCSP) Challenge Language 1 Domain MAXCSP: maximize fraction of satisfied constraints. Challenge: Alice challenges Bob to discount this statement belief(pred, 0.7): There exists a problem p in subset pred so that for all solutions s to p, quality(p,s) < 0.7. Confidence = 1. Discounting protocol: Alice gives Bob p , Bob solves it with s : quality(p ,s ) >= 0.7.
Required properties of challenge language Checking discounting and supporting are in P. (Once problem p and solution s are known.) Doing discounting and supporting requires constructive skills. Uncertainty about which problem to be delivered. Optional: mathematical skills When agents are perfect, supporting implies the statement is a theorem and discounting implies the statement is NOT a theorem (a counter example was found).
Skills needed to survive in SCG(X) [Scientific Innovation in X] Agents get skills programmed into them by clever scientists in domain X. Scientists use data mining to learn from competitions and manually improve the agents. [Machine Learning Innovation in X] Agents get skills programmed into them by an agent caregiver programmed with learning skills and data mining skills for domain X. Agent gets updated automatically between competitions and they improve automatically.
Rules of SCG(X) Agents play in rounds. In each
Athena Lightning Sweet Stepdad Peon Athena 3 0 3 0 Lightning 0 Sweet 0 Stepdad 3 Peon 1
Properties of SCG(X) When Alice loses reputation to Bob, Alice can learn from Bob: Alice has a bug in her software. Bob has skills superior to hers. Alice should try to acquire Bob s skills. The winner has the best skills in domain X within the set of participating agents.
Blame assignment Challenge 10 offerer 1 acceptor 2 confidence 1 Problem delivered Solution found Acceptor wins and increases its reputation Where is the offerer to blame? Bad offer that is discountable. Bug in problem finding algorithms. Bug in problem solving algorithm used to check offer.
Agent World for SCG(X) Agent Caregiver lives outside SCG(X) world World-class experts in domain X. Graduate and undergraduate students Studying domain X Studying material needed to solve problems in X Learning algorithms based on game histories. Agent lives inside SCG(X) world Agent win and lose reputation. Agent Caregiver prepares agent for next game.
Tools to facilitate use of SCG(X) Definition of X. Generate a client-server architecture for playing SCG(X) on the web. Administrator enforces SCG(X) rules: client. Baby agents: servers. They can communicate and play a uninteresting game. Baby agents get improved by their caregivers, register with Administrator and the game begins at midnight.
Software Development Skills Needed when agent caregiver is human. Knowledge about domain X needs to be developed by students or taught to them and understood and put into algorithms (offer- accept-deliver-solve) that go into the agent. This tests both whether the knowledge about X is understood as well as the programming skills.
Applications of SCG(X) Find the experientially best algorithms for solving problems in X.
SCG(X) produces history Offerer s reputation: 120. at-risk = 10% Challenge 10 offerer 1 acceptor 2 confidence 1 Problem delivered Solution found Acceptor wins: increase in reputation: 1 * 120 * at-risk = 12
