Project Description

In this project we implement an agent based simulation to a variation of the deduction board-game Code-777. The aim of the project is to apply epistemic logic to model the knowledge of the agents involved in game playing and experiment different agent behaviors (strategies) as employed throughout the game.

Code 777

Code 777 is a deduction board game by Robert Abbott. There are 28 cards each of which is attributed by a single colored digit. There are four players: North, South, East and West. In front of each player is a rack containing three cards. The remaining 16 cards are not used and kept invisible. Each player could see the cards on the other racks, but not the cards on his own rack. To win, a player must determine the cards on his own rack.

Knowing the cards on his opponents’ racks, a player starts with 19 C 3 = 969 possibilities for his own cards. Throughout the game, each player - in his turn - randomly pick up a question card, from a set of question cards, and asks the question written on it to an opponent of his choice. The selected opponent has to answer truthfully and from his answer, all other players could benefit and reduce their possibilities.

The game proceeds by players picking up question cards in turn until a player identifies his own cards (reduces all his possible card combinations to 1). The player announces his cards and the game finishes.

Reduced Code 777

For the purpose of the project, we considered a reduced version of the game. We reduced the number of cards from 28 to 12 and the number of players from 4 to 3 and accordingly considered a subset of the question base. The game workflow and rules are kept as they are, however, we considered the following modifications to compensate the mentioned reduction. (1) The rack in front of each player contains 2 cards instead of 3. This leaves the deck with 6 unrevealed cards. Since each player could see cards on other players’ racks but not his own rack, this leaves each player with (8c2=28) different cards possibility at the beginning of the game.

Considered Questions & Cards
• On how many racks is the sum of 6 or more
• On how many racks it the sum of 7 or less
• On how many racks there are 2 different colors
• On how many racks are all the cards even
• On how many racks are all the cards odd
• On how many racks exists identical cards
• Is there a rack with 2 consecutive numbers
• On how many racks can you see this number?
• On how many racks can you see this color?

Higher Order Knowledge

The considered game demonstrated the use of higher order knowledge to achieve a better winning possibility, where an agent increases his winning possibility by reducing his opponents’ possibilities. As might be obvious, an agent that has fewer possibilities for his cards has higher possibilities for winning (a player with 10 possible cards combinations left has a higher chance to win that a player with 15 possible cards combinations, since a winning agent is the one with 1 remaining possible cards combinations).

In the considered game, the only decision that could be taken by a player is which opponent to ask a question. Given that a player already knows the question he should ask before deciding the opponent to ask, reasoning about what other players think possible would definitely help.

The game starts by the cards distributed among the agents racks, each rack holds 2 cards. Each agent can see the cards on his opponents’ racks, these are 4 cards, and have the remaining 8 cards invisible to him, 2 on his own rack and 6 on the deck. With the goal to find out his cards, an agent is left with 8c2 = 28 possible card combinations that his cards lies within.

As could be obvious from the game description, each time an agent answers a question, all his opponents will benefit from the answer, reducing their own card possibilities. However, the questioned agent does not benefit at all. It might also be obvious that different questions, will lead to different possibilities reductions. Since an agent picks up a question card randomly, he can’t control that. However, an agent can control possibility reductions of his opponents at his turn by selecting which opponent to ask the question ex. If agent1 asks agent2, then he knows that agent 2 will not benefit this turn but agent3 will. Intuitively, at his turn an agent would like to ask the opponent with the fewest possibilities remaining, since accordingly this agent will not be able to reduce his possibilities. For that, an agent needs to reason about what other agents considers possible, this form of higher knowledge will help him decide which opponent to ask the question.

At the beginning and throughout the game, the agent considers his remaining possibilities as well as what other agents considers possible. At the beginning of the game, an agent assumes each opponent considers 10C2 = 45 possibilities. The reason its 10C2 not 8C2 is that, the agent does not have access to the same information his opponent has (which is the cards on the rack in front of him). These possibilities are reduced throughout the game.

Common Knowledge

Common knowledge increases every turn throughout the game. Starting with NO “relevant” common knowledge between all participating agents, each turn a question is asked, answered and accordingly the answer becomes a common knowledge to all participating agents.

Agents Behaviour

In our implementation, we programed different types of agents – Random, Annoying, Smart1 and Smart2 – With the first 2 considering the current situation, and the last 2 looking ahead one step forward. Given the only agent choice is the opponent they should ask a selected question, these agents’ acts as following.

• Random: Follows a random selection process
• Annoying: Considers opponents and their possibilities. Asks the opponent that he thinks has the least number of possibilities remaining, since by asking him it is guaranteed that this opponent will not have any of his remaining possibilities reduced.
• Smart1: Given that an agent knows the question he should in advance, the agent first checks who is the most opponent that will benefit from that question and ask him, so that he does not benefit at all.
• Smart2: Similar to the annoying agent, but checks the opponents remaining possibilities after asking the question i.e. Given the current agent a1, and his opponents op1 and op2. a1 assumes he asked op2 the question and calculates the remaining possibilities of op1 (since op2 remaining possibilities will not change), then he assumes he asked op1 the question and calculates the remaining possibilities of op2. Knowing the remaining possibilities of op1 and op2, the agent asks the opponent with the lowest remaining possibilities.

Application Description

Reduced Code-777 is implemented in Java and simulates the game playing. As mentioned 4 different types of agents are programmed, each has different behavior that affects his choices. From the settings tab, the user selects the types of agents, the application delay in milliseconds (the simulation speed, in case he wants to take his time thinking and reasoning about the agents choices) and the number of simulations he would like to run (for a normal game simulation or a test he could choose just 1 simulation, however, running the game multiple times (500 for example) would give an intuition about different strategies, in terms of wins). The user could then start the game. During the game play / simulation the user could pause the game or reset his simulations.

Interface

Through the user interface, the user is presented by the actual game play (1), the possibilities each player thinks for himself (2), and possibilities each player considers for his opponents (3). Throughout the game, questions being asked and their responses (which also correspond to the common knowledge) are also presented (4). Through this information a user could reason the agent’s behaviors while the game is being played.

Source Code

Application source code can be downloaded from here