Cluedo optimal suggestion asking

Question

I am writing an algorithm to ask for the most optimal suggestion (murderer, weapon, place). I would like to hear your opinions about this method, possible improvements, or limitations.

In order of importance:

1. Never use a card that you already know another player has: You won't gain any information.

2. Never use a card that another player knows I have: That player could potentially gain as much information from my suggestion as myself.

For example I own the dagger, and player B knows that. Additionally he has the kitchen, and I don't know that. I then suggest it was Plum, with the dagger, in the kitchen; when somebody disproves my accusation player B would know that the other player had to show me Plum.

3. Use my own cards a maximum of one time throughout the entire game: The entire point of using one of your own cards is to suggest that somebody else has it, or that it is one of the cards in the envelope. If I repeat one of my cards then this would happen:

I use my card no.1: The person that disproves me now possibly has no.1 (according to all the other players). But then I use no.1 again and this same player is now not able to disprove my suggestion. (All the other players now know he didn't have it; this gives them extra information that either I have it or it is in the envelope)

4. Never use a card that you know is in the envelope: This only gives the other players information about other people not having that card.

5. If you have used all your cards once, make suggestions about 3 unknown cards.

Answer 1

You are trying to write a set of human understandable rules for a problem that a machine can do much better at. What you have designed is a set of heuristics for what is fundamentally a statistics problem. If you want to achieve true optimality, I recommend you start over entirely.

There are 9 rooms, 6 players, and 6 weapons. This means that there are only 324 different valid guesses (9 * 6 * 6) in general, and if you restrict this algorithm to a guess given the room you are in, you only have 36 options. While these are is too big for a human to evaluate in real-time, they are negligible to a computer. What you want to write is a set of scoring criteria for each of these card combinations, and then to pick the card combination that has the highest score as your guess (breaking ties at random).

In order to talk further about optimal, we need to get rigorous about this scoring mechanism. It sounds from your starting attempt like there are two things you care about:

1. Gaining as much information that you don't already know

2. Revealing as little information that you do already know to other players.

It's going to be quite complicated to handle both of these, so let's focus on just point 1 at first (as it's the more important of the two).

In order to gain information, you algorithm needs to have as input everything that you already know about where cards are. This is:

• How many cards each player has

• Which cards you know the locations of (including your own cards)

• Which cards you know certain players do not hold

You then build a probability model of the location of each card (including the middle). Cards that you know the location of will have probability 100% associated with that location. Then, for an arbitrary guess, you model what the players will do with that guess, namely show you a card or pass to the next player. For this purpose, you probably want to assume the worst case, namely that if a player holds a card matching your guess that you already know the location of, that's the card you will be shown. With all of this, you can determine the probability that you will be shown a new card versus it will get back to you with no one showing you anything. You need to add in a bit of logic for figuring out what you learn if it gets back to you without anyone showing you anything.

But at the end of this, you have a probability of learning new information with a given guess. At this point you could throw in some weighting for different types of cards (I believe rooms to be more valuable pieces of information because you have to get to the room to guess it), but you don't have to. Compare this probability across each guess and take the one with the highest chance of telling you something new.

With such an algorithm, you could even run it on all 324 card combinations, look at the top 10 most valuable guesses, and from that determine the most valuable room to go to next (or maybe even add in some weighting for room distance).

At this point, you could now try to tackle part 2: giving away as little information as possible. What you probably want to do is subtract some amount from the score of each guess for how much information it gives away, but this gets complicated quite fast as to do it optimally requires modeling everything the other players know. You could just add a negative weight to any guess that would reveal a card you know to be in the envelope, but this would be a delicate thing to calibrate, and at this point we're back in the realm of heuristics rather than being able to talk about an "optimal" guess. My recommendation is to not include this in your first attempt at this algorithm.

Answer 2

Your current algorithm is flawed because it ignores:

A. the difficultly in moving rooms, how many goes it takes to move rooms

B. the fact that there are more rooms to eliminate than weapons/murderers

C. it doesn't suggest when you should use your own cards in your suggestion, just when you shouldn't

D. Your rule no2 fails to take account of an opponent with sufficient memory (or sufficient record keeping) - just because another player doesn't know you have the card now, doesn't mean he can't go back through previous goes when you show him the card later. You could use this to fix my problem C, and say you shouldn't ever use your own cards. But of course if you never show the card it doesn't matter. So you need to take account of the likelihood of showing a card later.

---

As an example for my problem A, let's say you start with equal distance to two rooms - one of which you have the card to, and one of which you don't. By your current algorithm there is no priority between the two. But obviously you get more information by going to the room you don't have. Let's now say the room you don't have is 2 spaces further away, but the final roll of the dice allows you to go to either - is it acceptable to still go to the room you don't have, or will it arouse suspicion? Is that suspicion worth it anyway? What about if the extra distance takes you an extra turn? Is it now too suspicious?

For my problem B it may prove better to eliminate rooms and not worry about eliminating weapons/people. It might be possible to eliminate weapons/people by analysing other people's guesses and the responses they get. So this may lead to you wanting to suggest your own cards for weapon and person in order to eliminate rooms. But if you get shown a card, and then on your next turn leave the room, that's a pretty strong signal to all the other players that the card you were shown was the room.

But let's say you use your own cards for weapon and person, and no-one can help you with the room; you now know the room. Before your next go, you get dragged into another room; one you have the card for, and you're forced to show that room card to the person whose go it is. According to your algorithm rule no2 you MUST move rooms before making a suggestion. This is going to a) lose you time in moving rooms, b) possibly result in you moving to a room where people will show you the room card or c) make it really obvious that the room you were dragged from was important when you try to get back there. Actually you've done the hardest bit (finding the room in the envelope); your best course of action is to stay in the room you have the card for, and force other players to show you their weapon/people cards.

Another example where your algorithm falls down is when you have the card that proves your own innocence. If you constantly accuse the same person, it means no-one is showing you that person card, which means either you have it or its in the envelope. Players who don't know that you have it will therefore accuse that person to check whether you have it or its in the envelope. If that person is you, then you get free movement to lots of different rooms! This can be a blessing or a curse though - if they move you to a room which you've already eliminated it can use up your valuable time.

---

In summary your algorithm is too simplistic. If you ignore the rooms and only apply it to weapons/people it's fairly good though.