DAI-List Digest Friday, 7 August 1992 Issue Number 85 Topics: Re: DAI Event at AI Olympics Re: DAI Event at AI Olympics Re: DAI Event at AI Olympics Please send submissions to DAI-List@mcc.com. Send other requests, such as changes in your e-mail address, to DAI-List-Request@mcc.com. ------------------------------------------------------------------------ From: juggy@cerc.wvu.wvnet.edu (V. Jagannathan) Subject: Re: DAI Event at AI Olympics Date: Fri, 24 Jul 92 13:33:29 EDT | Date: Mon, 6 Jul 92 09:44:06 JST | From: huhns@mcc.com | Subject: DAI Event at AI Olympics | | Due to the great popularity and success of the Robot Olympics held at | the recent AAAI Conference in San Jose, California, there has been a | preliminary discussion of including additional events at future AAAI | or IJCAI Conferences, such as | | * a DAI or multiagent event, in which ...? | | Well, it is up to us, the DAI research community, to define what this | event should be. To start a discussion of this, here is my | suggestion: | "The Cooperation Competition" | | Each entry consists of one software agent that has expertise in domain | X. Solving a problem in domain X requires the cooperation of two | agents, so two entries would perform at a time. If the agents are | able to cooperate and solve the problem correctly, they both obtain a | high score. If they fail to solve the problem, either due to lack of | cooperation or lack of sufficient expertise, they both obtain a low | score. Each agent is paired with every other agent for solving the | problem, and its final score is the sum of its results from all | pairings. | | Domain X must be a domain that can be simulated graphically, so that | the judges and audience can observe the competition. It also must be | a domain that does not require an inordinate amount of expertise, | because we want the entrants to focus on their cooperation strategies, | rather than on the domain itself. Here are some possibilities for | such a domain: | | * Furniture Moving - the agents must move a table from one room | through a doorway to another room. Cooperation is required, | because the table can only be carried by two agents, one at each end. | | * Planetary Exploration or Scavenger Hunt - the agents must locate a | number of objects hidden on a planet. By cooperating, they should be | able to find the objects faster and more efficiently. | | * Maze Exploration - by communicating and cooperating, two agents | should be able to explore a maze faster than either one individually. | Agents would be scored on how fast they traversed the maze. | | * Team vs. Team Capture (from Ed Durfee) - each entry is a team of | agents that cooperate with each other to capture their opponents' | agents by surrounding them. Points are awarded for each capture. | | Whatever the domain, we would need to specify a domain vocabulary and | a communication protocol | | Please let DAI-List know if you have any ideas or opinions about this, | or if you might be interested in participating. I am intersted in participating. Here are a few more ideas on problem areas: * FAA Air traffic control problem - the RAND experiment of early 1980 - where planes try to land and have to coordinate with other planes and control center. I met a person from MITRE at AAAI (don't recollect his name), and apparently they are in the process of designing next generation control towers. If there are simulations of such environments that are publicly available - then it might be worth looking into this kind of problem .. * House design: Requirements and constraints for a house are provided. The agents cooperate in designing the layout and structure of the house. Evaluation based on satisfying initial requirements, measure of cooperation ... - juggy ------------------------------------------------------------------------ Date: Sat, 25 Jul 1992 19:21:28 -0400 From: frege@zip.eecs.umich.edu Subject: Re: DAI Event at AI Olympics This mail is a response to Dr. Huhns suggestion for a DAI Olympics, which he calls ``The Cooperation Competition''. I very welcome his suggestion. The LaTex file below describes a card game called ``MIGHTY'' [[ Because of the length of the file, I have only included the introduction and conclusion. Please contact Mr. So directly to obtain the complete document. - Huhns]] which I have been thinking as a good domain to test DAI theories and models for quite some time beforehand. I think it complements the domains mentioned in Dr. Huhns mail - Furniture Moving, Planetary Exploration or Scavenger Hunt, Maze Exploration, and Team vs. Team Capture - in that the domain is ``cognitive'' or more precisely ``nonphysical''. Yet, it retains some of the advantages of the ``physical-spatial'' domain such as having a finite number of possible actions for each situation (i.e., the cards one can play), and thus the search space is well defined. Moreover, it has both ``competition' and ``cooperation'' as the core strategy to be used in the game. Briefly, the game involves 5 players, and the players are divided into two groups - offense and defense. The two groups compete with each other, while members of the same group should cooperate with each other - in a sense, very much like the ``Team vs. Team Capture'' domain. What distinguishes this domain, I think, is that the success of a group often depends on how they successfully communicate their intentions via action (i.e., card plays), and thus may provide insights into the semantical and pragmatic issues related to communication and action among possibly heterogeneous agents which may not share a common language for communication yet share the same extensional world for perception and action. Also, it is my experience that the game involves much common-sense reasoning about how to effectively manage and use finite resources, and due to uncertainties of the world, lots of hypothetical reasoning and belief revisions during the play. Modelling other agents is often critical when the games are played several times with the same players, and since who becomes a friend and who becomes a foe is newly decide for each game via negotiation, the agent modelling process itself has some dynamism. Compared to most other card games I 've played so far, MIGHTY requires much more thinking than luck to win. For implementing the game, I suggest writing a Game Server program which can receive request to register for a play in a game of type X, automatically group the requestees for play and simulate (or run) the game by interacting with the players (i.e., the client programs). How to use the server should be contained in a document and distributed to interested users. TCP/IP would have no problem for low level communication, I think. The basic idea is that the players don't have to be physically co-present as was the case in AAAI Robotics Competition. The scoring and evaluating the performance of players can be automatically done as well. But I think retaining the basic transactions among the agents as full proof seems worth while for scientific evidence. Well, I hope you take a look at it and tell me what you think about it as a candidate domain for DAI Olympics. Young-pa So EECS Dept. The University of Michigan P.S. Some people have mentioned the similarity between MIGHTY and BRIDGE. I am not sure how they are similar or different. I know BRIDGE involves 4 players. If you know BRIDGE please let me know what you think about the similarities and differences between the two. \documentstyle[12pt]{report} \begin{document} \title{\bf A Game called MIGHTY \\ and \\ its Implications \\ for \\ Distributed Artificial Intelligence} \author{\bf Young-pa So \\ \\ EECS Department \\ The University of Michigan \\ ({\em e-mail : frege@crim.eecs.umich.edu})} \maketitle \newpage \chapter{Introduction} This report presents a card game called ``MIGHTY'', and discusses its possible implications for researches in AI and DAI in particular. If you are not interested in the details of the game you can skip chapters 2 and 3. ``MIGHTY'' is a 5 person card game which has similar characteristics to the card game ``BRIDGE''. The 5 people are partitioned into two disjoint groups - the offense and the defense. The overall goal of each group in the game is to win as many points as possible by cooperating with other ``friends'' in the same group. The game is interesting in that it requires the skill (or intelligence) to cooperate with other ``friends'' in the group to win the game. The payoff is thus on a group basis rather than on an individual basis. Also interesting thing to note is that there are many important heuristics to learn concerning how to effectively cooperate with one another, and what are the safe strategies for these kinds of situation and so on. When you begin as a novice, there is definitely the feeling that you did something wrong on your play at such and such situation, and you get to learn the basic heuristics of the game from experience. Since it involves 5 people, the game is moderately complex, and allows many interesting and unexpected situations. You may sometimes want to induce your friend or foe to make a move that would lead to a strategically advantageous situation, and you sometimes have the opportunity to deceive both your friends and foes. \chapter{Implications for DAI research} Here, I will present some of the features of ``MIGHTY'' that I think makes it a good game for stimulating research in DAI. First, it retains some of the advantages of the ``physical-spatial'' domains much studied in DAI such as having a finite number of possible actions (i.e., the cards one can play) for each situation, and thus the search space is well defined. Secondly, it has both ``competition' and ``cooperation'' as the core strategy to be used in the game. In a sense, it is very much like a war game between two groups. Thirdly, in ``MIGHTY'', the success of a group often depends on how the members successfully communicate their intentions via actions (i.e., card plays). Usually in a game there is a lot of implicit communication through the cards each player plays, and there can be a lot of information contained in the play of a card by one agent. Thus some reasoning about the intentions of the other players when making their moves is needed. Thus, by carefully examining the communicative processes that go on in the game, we might gain insights into the semantical and pragmatic issues related to communication and action among possibly heterogeneous agents which may not share a common language for communication yet share the same extensional world for perception and action. Fourthly, modelling other agents is often critical when the games are played several times with the same players, and one may maintain a model of each of the other players - both friends and foes - so that one can predict the behavior of the other agents and thus plan its own behavior - short term and long term. It may be that the other agent who seems to play intelligently is just a {\em random} agent randomly choosing his moves. Or it might be that the other agent is faking and making a deceptive move in order to generate false beliefs among the players temporarily but eventually to come to a strategically advantageous situation in the game for their group. Moreover, since who becomes a friend and who becomes a foe is newly decide for each game via negotiation, the agent modelling process needs sophistication. Lastly, it is my experience that the game involves much common-sense reasoning about how to effectively manage and use finite resources one has. A player may play aggressively when it has many important resources (cards) - {\it Joker, Joker Gun, GIRUDA cards, etc.} - whereas, if it does not have much good resources to exert control over, it can take a passive role and try to assist his/her friends as much as he can. And due to uncertainties of the world, much hypothetical reasoning and belief revisions are needed during the play. Therefore, much insights can be gained on several types of reasoning under and about uncertainties in a distributed multiagent environment by implementing and experimenting those reasoning processes. \chapter{Conclusion} I think there can be much to be gained in DAI by implementing agents that can play a moderately complex cooperative game like ``MIGHTY''. As a person who have experience with ``MIGHTY'', I think it has much to give to DAI and also to AI in general. One could easily code a program that abides by the rules of the game yet makes random choices when there are multiple allowable cards it can play in its turn. Then, incrementally, more ane more intelligent strategies and heuristics can be added to the basic program and its performance can be evaluated by having it play games with people or other artificial agents. People can write their own game playing agent and have it play the game with other agents - human or machine, and see how well the creature performs, recognize the limitation, redesign, modify, make it work better - a cycle of artificial evolution. \end{document} ------------------------------------------------------------------------ Date: Mon, 27 Jul 92 11:48:36 -0400 From: sidner@crl.dec.com (Candy Sidner) Subject: DAI Event at AI Olympics I think your suggestion is a good place to start. It may be that researchers won't want to choose a domain (like furniture) that is so far from their everyday stuff, but that can be directly questioned. What I particularly like about this matter is that it may give the community some common ground for talking about research. At the moment people's interests are so widespread over different domains, that it is hard to compare. So a single domain, whatever it is, will be great. I am interested particularly in the problem of the communication protocol. As you may remember, furniture moving (pianos, in particular) are an example Barbara and I have pursued a bit. And I think that the difficulty of the competition will turn in part on the richness of the communication protocol. While natural language may be too difficult, there is considerable challenge in posing the question of what kind of artificial languages to allow. The same issues apply to the Maze and Planetary Exploration. In fact if the problem is structured so that the agents remain peers, their communication is likely to be more complex. One question is just what level of complexity is appropriate for such a competition. As for the Team Capture problem, this has enough of a military bias that leader and followers might be the most logical choice (most efficient way to proceed). In that case the communication may be quite limited. Candy