Side-Choosing Games for General Artificial Intelligence
Joint work with Ruiyang Xu.
Our application area is human computation for formal science
problems and teaching formal science topics and modeling scientific
In a class room setting we use a debating terminology
instead of a gaming terminology. The students debate claims
in some formal science topic and try to push each other
into contradictions in the sense of Socrates.
The Scientific Community Game (SCG)
which we have studied over the last few years,
is based on side-choosing games.
SCG was the breeding ground for the idea of side-choosing games.
We keep the acronym SCG because it also stands for Side-Choosing Games.
To be done: How to use General Artificial Intelligence to assist in playing side-choosing games.
Given is a (large) set of players P and a 2-player win-lose game G
with a player in role Q and a player in role !Q (!Q is called the negation of Q).
Role Q chooses one side of a claim about G and role !Q chooses the other side -- hence the name side-choosing.
One of the roles is the "correct" role and the players P want to determine the "truth", through many game plays using the wisdom of the crowd.
Each game play gives a justified vote for one of the roles with the game play leading to a win as a justification.
Two players from the large set P play a match: each of them declares whether it wants to play as Q or as !Q.
If they choose opposite roles,
they play G under the requested role assignment, and otherwise one of them is forced (playing devil's advocate), by a central authority or by flipping a coin, to adopt the role it does not
like, and the other gets to keep its choice of role, and they play G under the resulting role
assignment. (G may be any win-lose game, i.e., an extensive form game or a simultaneous move game.)
The results of multiple
matches (where the same pair of players may be matched multiple times) are aggregated in a labeled weighted tournament with vertex
set P: for each pair (u, v) it indicates how many matches were won/lost by each player in its selected role and in its forced role.
Instance 1: Judging Game Positions
Choose a chess position. Role Q:
I can win, starting as white in 2 moves. Role !Q: I, as black, can prevent a win of white in 2 moves.
Instance 2: Algorithm Specification (Constructive Proof)
Choose a directed graph H. Role Q: I can give you either a topological ordering of H or a cycle in H.
Role !Q: I can prevent you from doing Q. This side-choosing game is a specification of an algorithm for cycle-checking and topological ordering. Here the good players will all choose role Q.
Instance 3: Predicate Logic (Constructive Proof)
Consider the sentence S: Exists z in Z ForAll x in X Exists y in Y: p(x,y,z), where p is an atomic predicate without quantifiers.
Role Q: I can assign the existential quantifiers so that p becomes true. Role !Q: I can prevent you from doing Q by assigning the universal quantifiers.
In this context role Q is called the Proponent role and role !Q the Opponent role.
The second part of the game after the side choice is called a semantic game for the predicate logic formula (see van Benthem).
Ranking of Players
How can such a
tournament be aggregated into a ranking of players. We propose independent axioms for this setting, then
postulate that the ranking should arise on the basis of a scoring function that determines the score of each player based on its
performance it its own matches (taking into account whether it played in a preferred role or in a forced role).
We arrive at the conclusion
that a player's rank should only depend on the number of unforced losses (i.e., the matches this player played it its selected role and still
One of our axioms is a plot-resistance axiom. Consider a perfect player who always makes the correct side choice and then defends it with a win against any opponent. It is possible that for certain game plays perfect players are not top ranked. Our plot-resistance axiom prevents this and is crucial for trust in the outcome of a tournament.
(Is this possible even if all players play the same number of games?)
Karl Lieberherr, April 2016.