View on GitHub

Cluedo

Perfect Epistemic Logicians playing Cluedo

Created by Laura van de Braak, Luuk Boulogne, and René Mellema

Theory

This section will discuss the theory behind the game cluedo. We will first discuss the rules and possible actions of the game, followed by an explanation of how these can be translated into formal logic.

Cluedo

The rules of Cluedo were mentioned briefly in the introduction, but will be elaborated on further here.

The game Cluedo goes as follows: A reclusive professor gives a party for six guests. Somewhere during the evening, the butler finds the professor dead in the basement. However, it quickly becomes clear that the butler did not commit the murder, and that it did not happen in the basement. The only possible suspects are the six guests. The task of the players is to determine which of the guests committed the crime, with which weapon and in which room.

The game has a board, with nine rooms, six weapon objects, six players (guests) in different colours, and 21 cards representing all rooms, weapons and players. At the start of the game, one card of each category is placed in the vault (also called envelope), without any player having looked at them: these are the 'murder cards'. The rest of the cards is distributed over the players. In a turn, a player throws a set of dice. They are then allowed to move at maximum that amount of steps. If they enter a room, they may then make a suspicion. A suspicion consists of that room, a guest, and a murder weapon they suspect. Following this suspicion, the other players are asked to respond to this suspicion. In order of the game, each player is then asked if they have one or more of the cards of the suspicion. If they have none of these cards, the next player in turn is asked this. If they have one or more of the cards, they have to show exactly one card to the player who made a suspicion. After this, the player who made the suspicion can also make an accusation. To do this, they write down the three suspects, and look in the vault. If they were correct, they win the game. If not, they put the cards back in the vault, and are not allowed to play further: they lose. However, they still have to respond to the suspicions of the other players.

Actions

From the above explanation one can deduce a number of possible actions. From these actions deductions can be made by the other players. This was also discussed by H. van Ditmarsch in his thesis 'Knowledge games', published in 2000.

Perfect Epistemic Logicians in Cluedo

When humans play, they are not always perfect epistemic logicians. Humans can make mistakes, or can forget something that was said. Furthermore, they have limited processing capacity, so may not be able to remember all possible options.

Strategies

The three player actions (suspicion, response and accusation) can be played in different ways. These ways can be described as strategies. These will be discussed in the 'Strategies and Situations' section.

Cluedo in Logic

For this project we chose to build a logic-based version of Cluedo. Most of the game is reasoning, so we can use epistemic logic to do that. We use S5 for this, so we assume equivalence relations. Added on to that, we will make use of Public Announcement Logic, as described by Hans van Ditmarsch and Barteld Kooi in 'The Secret of My Success', published in 2006.

In a game of Cluedo, the actions that change anything in the knowledge of agents can all be formulated as announcements. Some of these are public announcements, which means that every agent receives the announcement and it is common knowledge that all agents received the announcement. There are also private announcements: announcements made by one agent to one other agent. All other agents see the communication happening, but do not know the message announced.

Because we are more interested in the reasoning aspects of Cluedo, we decided to leave the board out of our implementation. The game we built deals only with the murder cards, and with the reasoning the agents do with that.

The actions that change the knowledge of agents in Cluedo are noshow, show and nowin, as described above. take the above description of actions, they can be described in terms of announcements in the following manner:

Private Announcements

Since Cluedo also uses private announcements beside public announcements, we also had to implement those. We implemented private announcements as the removal of relations for an agent between states if those states have different truth values for the announcement and the announcement is made to that agent. We have a proof that this method gives us the correct knowledge change here.

Simplification

Because implementing the full scope of cluedo would be too complex to check formulas in a reasonable amount of time, we decided to simplify our version of Cluedo to a game with only six weapons, four persons, and no rooms. This means that there are only four agents who have two cards each. Because we use two categories, there are only two cards in the envelope, instead of the usual three. Since we are only interested in the reasoning within this game and movement has little influence on this, we will leave it out of our implementation. The other rules for the game stay the same.

This drastically reduces the number of states the game can have. For a given envelope content, agent #1 gets two of the eight remaining cards, agent #2 gets two of the six then remaining cards etc. The number of possible ways in which a single agent can get his/her cards dealt can be calculated by using the binomial coefficient. This coefficient is given by the following equation:

Here k is the number of cards that an agent gets and n is the number of cards that are not dealt yet before dealing to that agent. The total number of possible hands dealt for a given envelope content in the simplified version of cluedo is thus:

Before we deal the cards for the players, one weapon and one person is drawn for the envelope. This means that there are 6 * 4 = 24 possible envelope contents, which results in a total number of 60.480 possible states.

This is a much smaller number than the number of possible states there are in a real game of cluedo that has maximally 6 players. For such a game, the number of possible states for a given envelope content is:

Now there are 9 * 6 * 6 = 324 possible envelope contents. 324 * 137.225.088.000 = 44.460.928.512.000 possible states.