Diplomacy Programming Project:
Call for Volunteers

Danny Loeb

Diplomacy Programming Project

• Test recent work on strategy finder using diplomatic constraints from observation module. Tests may be done against humans, and/or in self-play mode using the Diplomat Interface.
• Improve front end of strategy finder and observation module in order to make such testing easier. Incorporate the strategy finder in the Judge (Diplomacy Adjudicator)?
• Make observation module an LCS agent (instead of a mere function) so that it can access the Strategy Finder to detect violation of general agreements.
• Write negotiation module including ambassador agents for each country, and a process that manages the relations between existing agreements.

Small Games Interface and Player

Certain situations in real-life are much better modeled by multi-player interactions than by simple two-player interactions. Thus, the theoretical and practical study of multi-player games is of fundamental importance. The theory of multiplayer games is much more complicated (and unexplored) in that the diverse players may have incentives to communicate and even collaborate.

A matricial theory of multiplayer games is fairly well developed. However, it supposes that the players enter into negotiations in order to conclude binding accords.

On the other hand, combinatorial multiplayer games (as described by labeled abstract trees) have been relatively unexplored. (See however the work of Propp, Straffin and Li.) In this model, a player wins and all of the others lose. We can longer suppose that the players have the possibility of negotiating.

The sets of players who can force a victory forms a maximal intersecting family. We can thus classify multiplayer games by M. I. F.'s. This classifications is somewhat unsatisfactory (the vast majority of games with a fixed odd number of players form a single class). We thus introduce the notion of stable coalitions. These coalitions can force a victory, and despite the fact that this victory can not be ``shared'' (as in matricial games), each member of the coalition has an incentive to follow the common strategy.

As compared to the case of two-player combinatorial games, we are confronted here with an embarrassing wealth of conflicting classification schemes. Before spending considerable effort classifying particular multi-player games, we must choose the most appropriate system of classification among the many alternatives.

We propose to continue our research on multiplayer games along two main axes.

• First, to continue our theoretical research on the properties of these classifications. For example, all of the models of multiplayer combinatorial games studied so far give a value to a subgametree of a given node independent of the sequence of moves required to attain that node. Can more realistic play be achieved using the history of play? (See below.)
• Second, practical human-machine simulations can be made in order to determine which systems of classification given rise to human play? Also, we may study the interactions of simulated players based on different systems of axioms? Finally, we will study the role of communication and negotiation in multi-player situations?

• Diplomacy Programming Project. The Diplomacy Programming Project hopes to design programs using the results of combinatorial game theory, matricial game theory, and artificial intelligence that play diplomacy and actually negotiate with each other. A Diplomat interface has been written in LCS. It launches game playing programs written in any language and open windows for human players. The Diplomat Interface then accepts orders, transmits messages from one player to another, and distributes results. Diplomats are being developed in C and LCS for use with the Diplomat Interface. (See below.)
• Metagame B. Pell has completed a thesis on Metagame. Computer game research has not resulted in a measure of progress in artificial intelligences. Chess programs perform strongly using methods different from those used by humans, and not easily applied to even similar games. Pell proposed a new measure by which programs would be written to play arbitrary games given a specification of their rules in Prolog.
• Symbolic Algebra Package. Wolfe wrote a symbolic algebra programming package in C which manipulates game trees, and performs most of the useful mappings in the theory of combinatorial games. The package is invaluable in analyzing combinatorial games, generating and testing hypotheses, and motivating the theory. This package is for the combinatorial game theorist what a spreadsheet is for an accountant, saving the mathematician from routine, but important, and often complex calculations. Combinatorial game theorists around the world have found many applications for this package and are constantly developing new functionalities. For example, Mu"ller and Garcia have added new graphical interface capabilities.

Wolfe's symbolic tree manipulating tools could then be used to apply the recursive rewrite rules found in the various combinatorial theories of multi-player games under development. These theories along with the diplomacy programming project negotiating protocols would form the strategic basis of a computer Small Games Player.

Thus, the work proposed is divided into two parts:

• Small Games Interface. A program is needed to test theories regarding small multiplayer games. A multiplayer game is defined by its ``game tree,'' actually a labelled acyclic graphs. The game trees in question here will have at most a few thousand nodes. The Small Games Interface program (SGI) must generate random (reduced) game trees or accept as input known games and generate their reduced game trees. The SGI must accept input from computer game players (which are programs written in an arbitrary language), or human players (via a graphical interface). The SGI must keep each player apprised of the rules of the game and the progress of the game. The SGI accepts moves from players and acts are ``referee''. Optionally, the SGI should allow certain types of communication between players. The program should be easily maintainable so as to add additional ``known'' game and better graphical interfaces. The interface used by the computer players should be as simple and as unrestrictive as possible in order to fascilate the comparison of large numbers of algorithms.
• Small Games Players. The small game player (SGP) is designed to work in conjunction with the small game interface described above. The SGP takes as input the game tree of a small multiplayer game and the history of the game. Given a position in which the SGP must move, it classifies the ``types'' of the various options according to one of the many formulae given in ``Stable Winning Coaltions'' by Daniel Loeb. (e.g. the set of (stable) winning coalitions of a position can be computed recursively from the sets of (stable) winning coalitions of the various options.) Given a system of classification, an order of preference among the types, and a method of breaking ties (possibly involving the history of the game), the SGP submits an appropriate move. Different methods should be compared systematically using the small game interface. Experiments involving communication between players may be invisaged.

The'orie des Jeux a` Plusieurs Joueurs

Recent work on combinatorial multi-player games has led to the discovery of various method of classification. Either by what sets of players form a "winning coallition" or "stable winning coallitions" There are many open questions.

• Given two games of known types, what types are possible for the sum of these games. This problem has been solved for 2 and 3 players. (eg: a 2nd player win plus another 2nd player win is never a 2nd player win). What happens with 4 players? Or with 3 players using stable winning coallitions.
• 3 player impartial games have further been classified by Jim Propp into equivalence classes under the addition of games. Can this be done using the notion of stability or with 4 players?
• Probabilistic models have calculated the probability of a "random" game being of a given type for 3 or 4 players. With formal calculation programs such as Maple, 5 player solutions should be possible.
• Jurg Nievergelt suggested generalizing Stable Winning Coalitions to non-winner take all situations.

1. J. Conway, ``On Numbers and Games'', Academic Press, 1976.
2. E. Berlekamp, J. Conway, et R. Guy, ``Winning Ways for your mathematical plays, Volume I: Games in General,'' Academic Press, 1972.}
3. D. Loeb, Challenges in Playing Multiplayer Games.
4. S.-Y. R. Li, N-person Nim and N-person Moore's games,} Internat. J. Game Theory 7 (1978) 31--36.
5. J. G. Propp, Three-Person Impartial Games.
6. P. D. Straffin, Jr., Three-person winner-take-all games with McCarthy's revenge rule, College J. Math. 16 (1985) 386--394.
7. D. Loeb, Stable Winning Coalitions.

If you wish to e-mail feedback on this article to the author, and clicking on the mail address above does not work for you, feel free to use the "Dear DP..." mail interface, which is located here....