Representing knowledge
Kripke Models
We implemented the knowledge of the different agents, by the use of Kripke models. After distributing the cards among the agents, 4 cards are in front of every agent and each card is unknown to everyone. Each agent therefore has a Kripke model containing n^(4*a) worlds, which represents the possible values a card can have. Here, a stands for the number of agents (which can be specified between 2 and 4) and n stands for the different card values available in the game deck (default = 13 (0 - 9 or the card is one of the three special cards)). We assume none of the agents count cards, they only know the average value of the game deck.
This means that when the game is run with 4 agents and a default card value deck, each agent considers 13^(4*4) = 13^16 worlds as possible. When the game starts, the agent is allowed to see two of his own cards, immediately eliminating many worlds. So the agent begins the game with (13^14)+2 worlds.
Implementation of the Kripke Models
Each agent keeps track of the possible values each card can have. This can be either an exact value, or a range of possible values. Combining this knowledge of all cards results in all the possible states the agent can be in. Every state is connected to every state. If an agent receives more knowledge about a card, the relations to states that are not possible anymore are erased. This is how we implemented depth 1 knowledge.
Next, each agent keeps track of what he knows about other agents, including himself (depth 2 knowledge). For example, you can represent whether agent 1 knows that agent 4 knows the value of a card, or that agent 1 knows that agent 4 knows that the card value is lower than 5. This fact can thus differ from the fact about the exact same card stored at the 1st depth. Combining the knowledge of depth 2 results in all possible relations for other agents you think are possible. This extra knowledge can result in relations to states that are not possible anymore.
Depth 3 knowledge is used to represent knowledge about what an agent knows about what another agent knows about what another agent knows (including himself). For instance, a fact about what agent 1 knows that agent 3 knows that agent 4 knows can be represented here. Adding the relations between worlds the agent knows other agents know that other agents know are possible to the Kripke model can again result in relations to states that are not possible anymore. Therefore, adding depth 2 and depth 3 knowledge can help an agent in making him more certain about the values of the cards on the table.
The combination of all these facts of all the different depths, will give the Kripke model of the agent. Through combining the Kripke models of all agents, the global Kripke Model is obtained.
Updating knowledge
A turn consists of all the steps an agent can make until the next agent may make a move. These steps include getting a card, using the card and discarding a card. Since each step in a turn may contain meaning for one or more agents, the knowledge of all the agents is updated after each step, using update-rules.
An example of updating knowledge when the agents only keep track of knowledge at depth 1: Suppose agent 1 is peeking at his own 3rd card. Then, that agent should update his knowledge about its 3rd card to the value that it just saw. Other values are no longer possible for this card and relations to worlds with these other values are erased.
An example of updating knowledge when the agents also keep track of knowledge at depth 2: Suppose agent 1 discards a card, instead of putting it (for example a card with the value 6). Then, the other agents know that all the values of agent 1's cards (that they know that agent 1 knows the true value of) are lower than, or equal to, 6. Otherwise agent 1 would have put the card with value 6 on its own higher card. So the other agents update their knowledge that agent 1's cards (that they know that he knows of) should be <= 6. They erase any realtions to worlds in which agent 1's cards are larger than 6. Additionaly, at depth 2 they also erase all relations to worlds in which agent 1 knows that his own cards are larger than 6.
An example of updating knowledge when the agents also reason about knowledge at depth 3: Suppose agent 1 peeked his 3rd card. Then agent 1 knows that agent 2 knows that agent 1 peeked at his 3rd card. This sort of knowledge then can be used in the strategy, if you want to pick a card the others players know the least about.
An important note with the rules used when updating the second and third base is: these rules only work if the agents think agent 1 uses the default strategybase (see strategy below). Because if you believe an agent uses a different strategy (like always get a closed card, to let the other agent's know as little as possible about your own cards), these update-rules may not hold. So we have different update-rules for different strategy bases.
All Knowledge-updating Axioms
All axioms we used/created for updating the knowledge of the agent, can be seen here (pdf). With this list of axioms we probably haven't reached completeness of the model, however, we did show that our axiom system is sound. In addition, using this set of axioms our agents reason and apply knowledge with very good results.
Strategies used by agents
To decide which action an agent wants to do, the agent uses his strategy base. Because we want to implement different strategy types, agents can have different strategy bases. One strategy type, for example, could be that an agent always wants to draw from the closed deck. The game rules are handled by the game (for example: the agent can't choose to draw from the open pile if the open pile is a special)
Regular Strategy
An example of a strategy when only reasoning about knowledge at depth 1: When an agent holds the card with the value 4, he must decide if he want's to put the card in one of his own positions, or if he wants to discard the card. If he knows one of his own cards has a higher (expected) value then the card he is holding, he will put the card there. Otherwise he would discard the card.
An example of this strategy when also reasoning about knowledge at depth 2: Suppose that agent 1 wants to swap his third card with another one. The value of his third card is 8. Agent 1 will consult his depth 1 knowledge about the cards of the other agents to decide which card is the best pick (lower value is better). Also, the agent wants to make sure that the minimum amount of other agents will know his new card. Therefore, the agent consults his depth 2 knowledge. He will pick the card, of course with a lower value, which the other agents know the least about.
An example of a strategy when including knowledge at depth 3: Suppose that agent 1 knows all his four cards (K1 KnowAllOwnCards), and they are all <= 4. Also, agent 2 knows that agent 1 knows his own cards (K2K1 KnowAllOwnCards) and agent 1 knows that agent 2 knows that (K1K2K1 KnowAllOwnCards). Then, if agent 1 discards a card with the value 6, agent 2 knows that all agent 1's cards are <= 6 (K2 Allagent1Cards <= 6). Then, agent 1 also knows that agent 2 knows that (K1K2 Allagent1Cards<=6). If you don't want to give away that much knowledge to everyone, your strategy could be to just put the card on a position instead of discarding it (so, giving a lower priority to getting the best cards, but a higher priority on letting no-one know how good you're cards are).
Paranoid Strategy
The paranoid agent will never draw a card from the open pile, even if it's a zero, because he doesn't want other agents to know his cards. The other agents know this agent is paranoid, so they won't update their knowledge if this agent did 'get Closed'.
Psychic Strategy
The psychic agent knows the values of all the cards (except the cards on the closed pile), all the time. The other agents don't know that this agent is psychic, so they will update their knowledge like if it's an agent using the regular strategy. When an agent uses this strategy, the other agents could know something that's false, since these agents think that the psychic agent uses the normal strategy and they update their knowledge based on that strategy.
All Strategy rules
All strategy rules we used/created for choosing an action, can be seen here (pdf). With this list of strategy rules we probably haven't reached completeness. However, it is the most rational strategy we could come up with ourselves in which agents always aim for the lowest possible card values. In addition, using this strategy, our agents reason and apply knowledge with very good results.
