The algorithm of the fastest victory in the math game

A friend of mine suggested that I play a game. This is a turn-based game and for two players. Here are the rules:

  • Both players guess a four-digit number.
  • Then they flip a coin to decide who goes first.
  • The first player tries to guess the number of the second player.

  • If it fails, the second player tells the first player two numbers:

    1. The first number indicates the number of guessed digits in the number without taking into account the position.

    2. The second number indicates the number of correctly guessed positions.

      Example: The first player guessed the number 2737 The second player tries to guess the number. He says 2274 The first player answers it 2, 1

  • Then they change

  • This continues until one of them guesses the entire number of the opponent.

I won this game using the following algorithm:

Imagine, what our opponent made 4856

  1. First, we guess 4 random numbers.

    1234

    Then look at the answer. In our case, this is 1, 0

  2. On the next turn, we raise the first digit by one from the largest one present in the number. In our case, this is 5.

    5234 #=> [2, 0]

  3. Since we found a new digit, we move it to the right one position, replacing the existing one. We also increase the first one again a number by one.

    6534 #=> [3, 0]

  4. 7654 #=> [3, 1] We guessed the first position. It's 5 or 6, since 7 didn't increase our first number in the answer.

  5. 8654 #=> [4, 1] Hooray! We found all the numbers. It remains only to find the right places for them. So we'll try to rearrange them, starting with the leftmost one.
  6. 6854 #=> [4, 2]
  7. 5864 #=> [4, 1] Here we have lost one digit. It means that she was in the right place. We will return it and ignore it in the future.
  8. 4856 #=> [4, 4] We we won.

We won in 8 moves. I tried to play this game with other people using this algorithm, and in most cases I won. But it still seems to me that it is too primitive. There must be a way to win this game in any scenario in the least number of moves. Any ideas?

Author: Grundy, 2016-09-25
Source

1 answers

Please do not look at the quality, it was written with the speed of typing on the knee :) In several test batches, I guessed for 5 questions. No heuristics:), just randomly take the first available option from the valid ones.

Modified bulls-cows - with allowed repetition of digits; the first 0 can not be.

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

vector<int> var;

class Checker
{
public:
    Checker(int val, int tot, int pos):val(val),tot(tot),pos(pos)
    {
        digs[0] = val/1000;
        digs[1] = val/100%10;
        digs[2] = val/10%10;
        digs[3] = val%10;
    };

    bool operator()(int chk) const
    {
        unsigned char cigs[4];
        cigs[0] = chk/1000;
        cigs[1] = (chk/100)%10;
        cigs[2] = (chk/10)%10;
        cigs[3] = chk%10;

        int position = (digs[0]==cigs[0]) + (digs[1]==cigs[1]) + (digs[2]==cigs[2]) + (digs[3]==cigs[3]);
        if (position != pos) return true;

        int tots = 0;
        bool is[4] = { false, false, false, false };
        for(int i = 0; i < 4; ++i)
        {
            for(int j = 0; j < 4; ++j)
            {
                if (is[j]) continue;;
                if (cigs[i] == digs[j])
                {
                    tots++;
                    is[j] = true;
                    break;
                }
            }
        }
        if (tots != tot) return true;

        return false;
    }
private:
    int val, tot, pos;
    unsigned char digs[4];
};

int main(int argc, const char * argv[])
{
    for(int i1 = 1; i1 < 10; ++i1)
        for(int i2 = 0; i2 < 10; ++i2)
            for(int i3 = 0; i3 < 10; ++i3)
                for(int i4 = 0; i4 < 10; ++i4)
                    var.push_back(((i1*10+i2)*10+i3)*10+i4);

    while(var.size() >= 1)
    {
        random_shuffle(var.begin(),var.end());
        cout << "Size = " << setw(4) << var.size() << "  > " << var[0] << "? ";
        int tot, pos;
        cin  >> tot >> pos;
        if (tot == 4 && pos == 4)
        {
            cout << "I won!\n";
            break;
        }
        var.erase(remove_if(var.begin(),var.end(),Checker(var[0],tot,pos)),var.end());
    }

}

Update. I conducted an experiment on guessing all 9000 numbers. It turned out approximately (I ran only one cycle through all the numbers): Results:

  Попыток  Количество
  -------------------
        2          12
        3          91
        4         614
        5        1865
        6        3138
        7        2329
        8         763
        9         165
       10          23
 2
Author: Harry, 2016-09-25 14:52:15