All you need is clue.hpp.
Included: A VS 2019 solution for Windows, but the code should run on any C++ compiler.
Introduction
My wife says that I have to rest from programming - and I try to. Only that to rest, I also have to code. Perhaps I'm addicted enough, but she has accepted me the way I am and I can't change. Oh well.
I like games like Cluedo. Here is a small console player and the ideas behind it, in C++. There is usage of C++11 plus features like lambdas, std::random, etc.
Dealing
Although Cluedo has a specific set of cards (6 suspects, 6 weapons, 9 rooms), the code can contain any number of categories and each category can contain any number of objects. The function DefaultCards creates a Cluedo setup:
void DefaultCards()
{
cards.clear();
cards[0].resize(6);
cards[0][0] = L"Mustard";
cards[0][1] = L"Orchid";
...
cards[1].resize(6);
cards[1][0] = L"Candlestick";
cards[1][1] = L"Dagger";
...
cards[2].resize(9);
cards[2][0] = L"Ballroom";
cards[2][1] = L"Billiard Room";
cards[2][2] = L"Conservatory";
...
}
The dealer then gets one random card from each category (the guilty cards), then deals the rest of the cards to the players (default 6). The function Inform informs each player of the setup (# of players, type of deal and their own cards). The PLAYERCARD structure contains the card info (category index, item index) and is simple:
struct PLAYERCARD
{
size_t cat = 0;
size_t idx = 0;
};
Positive Tracking
std::map<PLAYERCARD, size_t> Positives;
This std::map is used to store the positives, i.e., the cards that a player is sure to know where they belong. A positive can occur:
- From the initial deal (the cards that a player receives)
- From a card shown in the game to the player
- From a deduction of other cards (see below)
Negative Tracking
std::map<PLAYERCARD, std::unordered_set<size_t>> Negatives;
This std::map is used to store the negatives, i.e., the cards that a player is sure to know where they do not belong. A negative can occur:
- From a non-response of a player. For example, if Player 1 suggests "
Mustard", "Dagger" and "Ballroom" and Player 2 does not respond, Player 1 knows that Player 2 cannot have any of these cards. - When a player's all cards are known, then the player cannot hold any other cards.
Because negatives of a card can match more than one player, the second type of the map is a std::unordered_set. This allows to insert duplicates on the set and they are automatically eliminated.
Possibility Tracking
std::vector<std::tuple<size_t, std::vector<PLAYERCARD>>> Possibilities;
When Player 2 responds to Player 1 suggestion with a card, Player 1 sees that card. Other players cannot see this card, but they know that Player 2 has one of these cards that Player 1 suggested. This vector keeps the possibilities for each player. If a player is known, e.g., to have either Mustard, Dagger or Conservatory cards and later on, the Dagger and Conservatory is excluded, that player can be deduced to have the Mustard card.
Suggestion Intelligence
std::vector<PLAYERCARD> Suggest()
{
std::vector<PLAYERCARD> o;
size_t cats = TypeDeal.size();
for (size_t i = 0; i < cats; i++)
{
struct CARDANDNEG
{
PLAYERCARD p;
size_t nneg = 0;
bool operator <(const CARDANDNEG& can)
{
if (nneg < can.nneg)
return true;
return false;
}
};
std::vector<CARDANDNEG> picks;
for (size_t idx = 0; idx < TypeDeal[i].size() ; idx++)
{
PLAYERCARD t(i,idx);
if (Positives.find(t) == Positives.end())
{
CARDANDNEG can;
can.p = t;
picks.push_back(can);
}
}
if (picks.empty())
{
PLAYERCARD t(i,0);
CARDANDNEG can;
can.p = t;
picks.push_back(can); }
if (picks.size() == 1)
{
PLAYERCARD pc = picks[0].p;
o.push_back(pc);
continue;
}
for (size_t ii = 0; ii < picks.size() ; ii++)
{
auto& p = picks[ii];
if (Negatives.find(p.p) == Negatives.end())
continue;
p.nneg = Negatives[p.nneg].size();
}
std::sort(picks.begin(), picks.end());
auto lastneg = picks[picks.size() - 1].nneg;
while(picks.size() > 1)
{
if (picks[0].nneg == lastneg)
break;
picks.erase(picks.begin());
}
std::uniform_int_distribution<> distr(0, (int)(picks.size() - 1));
int rt = distr(random_engine);
PLAYERCARD pc = picks[rt].p;
o.push_back(pc);
}
return o;
}
Player suggests one card from each category. Version 1 of the suggestion function did that at random. Version 2 only picked cards that are not positives. Current version selects only between cards that have the most negatives.
Next idea about that is to suggest the card that would benefit more to resolve the possibilities if found.
Response Intelligense
std::optional<PLAYERCARD> Respond([[maybe_unused]] size_t pl, std::vector<PLAYERCARD>& pcs)
{
size_t CanRespond = 0;
for (auto& req : pcs)
{
for (auto& my : mycards)
{
if (req.cat == my.cat && req.idx == my.idx)
CanRespond++;
}
}
if (CanRespond == 0)
return {};
if (CanRespond == 1)
{
for (auto& req : pcs)
{
for (auto& my : mycards)
{
if (req.cat == my.cat && req.idx == my.idx)
{
mycardsshown[my]++;
return my;
}
}
}
}
PLAYERCARD Should;
size_t sm = (size_t)-1;
for (auto& req : pcs)
{
for (auto& my : mycards)
{
if (req.cat == my.cat && req.idx == my.idx)
{
size_t count = mycardsshown[my];
if (count < sm || sm == (size_t)-1)
{
sm = count;
Should = req;
}
}
}
}
mycardsshown[Should]++;
return Should;
}
When you have zero or one card to show, there is no choice. When you have more than 1 card that you can respond with, the first version of the algorithm picked at random. The current version selects the card that is most shown in the past (i.e., if you show the Revolver card and at a next time you have the option to show it again, it's picked again).
Accusation Phase
std::optional<std::vector<size_t>> AskGuilty();
After each player gets the responses, it's asked to provide the guilty cards. The steps are:
- Negative cards on maximum player cards are calculated, e.g., if a player's cards are all known positives, all other cards cannot belong to this card.
- Possibilities are resolved. If a player is known, e.g., to have either
Mustard, Dagger or Conservatory cards and the current negatives indicate that the Dagger and Conservatory are excluded, that player can be deduced to have the Mustard card. - For each category:
- If a card is forced because it has all negatives (for example, six negatives/sis players), then this is a guilty card.
- If 5/6 from the cards have positives to a player, then the 6th card is a guilty card.
- If there are more potential guilty cards, the function returns immediately a probability score but suggests no guilty cards.
Future versions of the accusation phase should take into account the chance that another player might solve the mystery before the next chance. Therefore, if the probability of the guilty cards is not 1 but it is relatively big (say, 0.3), then a future version might risk a guilty phase on the reasoning that the player wouldn't have another chance anyway.
Future Plans
To have a player track and estimate the likelihood of other players solving the mystery. If there is a possibility that a player would solve the mystery at the next turn, the current player must suggest the guilty cards even if the probability is low.
Have fun with it!
History
- 4th March, 2020 - First release
