Diplomacy Programming Project:
Call for Volunteers

Danny Loeb

Diplomacy Programming Project

Key Words: Jeux, programmation paralle`le, intelligence artificielle, architecture, diplomacy, alpha-beta, ne'gociation, semantique
Software: LCS, C References

Small Games Interface and Player

Key Words: Jeux, arbres, graphes, acyclique, interface, recursion, intelligence artificielle

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.

These simulation will be based on the following previous experience: We propose to write a Small Games Interface which will open channels of communication between computer small game players and/or human players as does the Diplomat Interface. The rules of the game to be played will be generated and transmitted in the form of a labeled abstract tree containing at most several thousand nodes.

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:

The'orie des Jeux a` Plusieurs Joueurs

Key Words: Mathe'matiques, Jeux Combinatoires

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.

  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.

Danny Loeb
University of Bordeaux

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