Ezelen a Multi-agent systems project

The Game

The game is called “Ezelen” and can be played with four friends. From all 52 cards in the deck 16 cards are selected, namely all suits (Diamonds, Clubs, Hearts and Spades) of the four different types: Aces, Kings, Queens and Jacks. These will be the cards used when playing Ezelen. The cards are shuffled and distributed over the four players.

The goal of every player is to collect four cards of the same type. At every round the players give one of their four cards to their right-hand neighbour and receive a card from their left-hand neighbour. Different strategies can be used in this game. Some will help the player collect four cards of the same type and some will also make it difficult for other players to collect four cards of the same type.

The Program

The program has been written in Java using the Netbeans IDE. The program creates four agents with their own knowledge model and distributes the cards over the four agents.

The text boxes show the knowledge and beliefs of each agent. The numbers next to the predicate knowledge show in which turn the knowledge was added to the model. Below the text boxes, the hand of the agent is shown, and the card it has just received has a blue border.

In figure 1 the interface of Ezelen is presented. There are four agents, each with their four cards and their own knowledge screen. By pressing the Next button all four agents will choose a card to give to their right-hand neighbour.

Knowledge & Strategies

For the game of Ezelen it is useful to keep track of which players could have which cards to determine who is collecting cards of a certain rank. The player can then choose to start collecting a different rank of cards, or try to sabotage the other player's efforts. With the knowledge the agent has about its own cards, the other cards and where they might be, the agent constructs certain beliefs. It constructs beliefs, because it cannot know for sure where the cards that it needs are. With these beliefs it constructs its goals; situations it desires to be in. With these goals and beliefs the agents has certain intentions.

Every agent has its own knowledge and belief model. These models contain all the things the agent knows to be true and what it considers to be possible. These “things” can be were a certain card is and what the strategy might be of all the other agents. The agent uses both models together to decide what its strategy will be in this round. In the image below you can see the belief model. In every state an agent has a certain belief about which type of card is being collected and which is not.

Every agent also tries to model the beliefs of the other agents about itself by looking at the cards it is passing on. This second degree knowledge could have been used to try to fool the other players so they cannot determine the agent its strategy. In the game of Ezelen, where the individual games often do not take more than a few rounds, we did not find it helpful in reaching the agents goal. Therefore, the agent does not use this knowledge to determine its strategy.

Belief model of the agent. Each T or F stands for that type of card being collected or not, ordered as follows: Ace, Kings, Queens, Jacks. The arrows show which state can be reached from other states. The partitions for each round show which part of the belief model is being used given the number of rounds the agent holds on to its beliefs about which card is being collected and which is not.

Possible Kripke Models

We have considered a few different Kripke models to use in our description and implementation.

One possibility is to keep track of all the agents, and all the cards they may have. Quite a few states can be left out, as they are impossible to reach. E.g. states in which two players have the same card. Doing so, this would still result in C(16,4) × C(12,4) × C(8,4) = 63.063.000 states. We wanted to keep an overview of the global state, and this would not have been possible with this many states. It would also would have been too many to use in our actual implementation. Besides, as the game progresses we cannot exclude the possibility of being in a number of different states as we cannot observe what the agent next to our neighbour is doing.

Another possibility is to keep track of the strategy of every agent. The strategy in this case is what type of card each agent is collecting at this round. This would result in 4×4×4×4 = 256 states. The amount of states is considerably smaller than the amount of the previous kripke model. Nevertheless, it is not optimal to keep track of every agents individual strategy, because you still can't tell for certain which agent has which strategy, also taking into account that the agent may change its strategy at any moment. Therefore, we have chosen the kripke model descrived above. In this model we keep track of the strategies of all the other agents combined. This results in a much more manageable 16 states.

Implementation

At the start of the game, every player only knows for certain which cards it has, which cards there are in the game, that every card is only possessed by one player, and that each player has precisely four cards. The first strategy used by an agent is chosen solely on what the agent knows about its own cards. After the first round, the agent decides which card to collect using the following rules:

• When the agent has three cards of the same type in its hand, it will collect this type. Unless it has been doing so for the previous eight rounds.
• Otherwise, the agent will start to collect the type that is the most likely not being collected by other agents, according to its own belief model, and will keep this strategy for the next two rounds.

Every agent keeps track of which cards were given to it by its left-hand neighbour in the last four rounds. This knowledge is used to determine which type of card is most likely not collected. If the agent's path to its goal has not improved over the last two or eight rounds, it checks which type of card were given to it the most and it will change its strategy to collecting that type of card. This is a logical decision, because the agent can conclude that if it has not received that particular type of card, another agent must be collecting this type as well.

It is also important that the agent considers which card to pass on to its neighbour. It does so by using these rules:

• If the agent has no knowledge nor beliefs about the other players, it will pass on the first card in its hand that is not of the type it is collecting.
• Otherwise, it will pass on the card of the type it is not collecting and is most likely not collected by the other players according to the agent its beliefs.

By passing on the card that is most likely not collected by any other agent, the agent tries to annoy the other players and prevent them from reaching their goal.

Download & Play

The source code is available on Github and as a ZIP archive or a runnable JAR archive.