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.