Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Languages / C++17

The Clue Game Solver in C++

5.00/5 (7 votes)
4 Mar 2020CPOL4 min read 14.7K  
A small player for your clue game
A nice way to kill your time - a clue game C++ 17 command line player/solver

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:

C++
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:

C++
struct PLAYERCARD
{
    size_t cat = 0;
    size_t idx = 0;
};

Positive Tracking

C++
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

C++
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

C++
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

C++
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); // duh
        }

        if (picks.size() == 1)
        {
            PLAYERCARD pc = picks[0].p;
            o.push_back(pc);
            continue;
        }

        // Choose the item that has the most negatives
        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();
        }

        // Sort
        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

C++
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)
    {
        // Forced
        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

C++
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)