#
Side-Choosing Games for General Artificial Intelligence

Joint work with Ruiyang Xu.
##
Background

Our application area is human computation for formal science
problems and teaching formal science topics and modeling scientific
communities.
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)
http://www.ccs.neu.edu/home/lieber/evergreen/specker/scg-home.html
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.
###
Fundamental Contributions

To be done: How to use General Artificial Intelligence to assist in playing side-choosing games.
##
Definition

###
Basic Game

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.
###
Forcing

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.)
###
Tournaments

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.
##
Examples

###
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
lost).
##
Plot Resistance

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.