How to Guess This Game's Number Mathematically?

Question

So, I and my friends have a game named "Strike Ball". It's basically number guessing game. There are minimum 2 player. Both of them think a n digit number where every digit is different (ex. 1210 isn't allowed). Then they guess the opponent's number, the opponent will answer "k Strikes l Balls" where:

Strikes happened when the digit match the position and the number. So, if opponent's number is 1284 and you guess 1385, it's 2 Strikes.

Balls happened when the digit match the number, but the position isn't right. So, if opponent's number is 1284 and you guess 2173, it's 2 Balls.

The players take turn until someone finally get n Strikes (the player guess the number right) and the player who gets n Strikes wins.

My question is, is there any mathematical calculation to guess the number? Because all I can do is brute force by saying every digit possibly and it's kinda not effective.

Answer 1

I got motivated to write a close-to-optimal solver for you. This solver only works once you have already figured out exactly which digits you need, and only need to guess their correct permutation. It is a little brute-force: it remembers all possible permutations, and every time you ask a question and get a certain number of strikes $= M$, it selects only those permutations that have exactly $M$ digits in the same positions as the permutation in question, and deletes all the others. The permutation in question is selected at random out of those that are still considered possible. Surprisingly, for 10 digits it only requires approximately 10 questions to arrive at the correct permutation. It can still be optimized by considering which permutation could potentially exclude most of the remaining possible permutations, but such an algorithm would be at least $O(N_P^2)$ where $N_P$ is the number of possible permutations, which would take a really long time to compute. While I hate to have an algorithm scaling with the number of permutations (which is 3 millions for 10 digits), I don't think it is possible to easily reduce the dimension of this problem - it is equivalent to cutting out hyperspheres in from from a convex polytope in 10D space. I don't think there is a compact representation of all the points remaining after a few such cuts. So any efficient strategy for solving this problem is most likely impossible to execute in your head or on a piece of paper.

Note: In my code I have used a notion of distance. Distance is $D - M$, where $D$ is the number of digits and $M$ is number of strikes

Here is the code in Python:

import itertools
import numpy as np

# Generate all permutations of N distinct digits
NDIGIT = 10
perm_set = set(itertools.permutations(range(NDIGIT)))


# Count distance between two permutations
def permdist(A, B):
    return np.count_nonzero(np.array(A)-np.array(B))

# Get some item in the set (first one, whatever that means)
def anySetItem(S):
    for e in S:
        break
    return e

# Your opponent generates a random secret permutation
secret_perm = np.random.permutation(NDIGIT)

print("Secret permutation is", secret_perm)

# Ask questions until there is only one possible permutation remaining
while(len(perm_set) > 1):
    # Question permutation can be any permutation that is still possible
    question_perm = anySetItem(perm_set)

    # Ask question here: Calculate distance between secret permutation and question permutation
    dist = permdist(secret_perm, question_perm)

    #Find delete all permutations that are not correct distance from original
    set_to_delete = set([])

    # If this permutation is not the optimal permutation, it should be deleted
    if dist != 0:
        set_to_delete.add(question_perm)

    # We should also delete all permutations that are not the correct distance from this permutation,
    # as they can't possibly be correct
    for e in perm_set:
        if permdist(e, question_perm) != dist:
            set_to_delete.add(e)

    # Subtract sets
    perm_set -= set_to_delete

    print('I asked for permutation', np.array(question_perm), ': distance was', dist, ',number of possibilities got reduced to', len(perm_set))

print(np.array(anySetItem(perm_set)), 'is my final guess')
print(secret_perm, 'was the correct answer')

Here is an example output of the code

Secret permutation is [2 1 6 0 3 8 5 9 4 7]
I asked for permutation [4 8 1 6 9 5 0 3 7 2] : distance was 10 ,number of possibilities got reduced to 1334961
I asked for permutation [9 2 0 1 7 3 5 8 6 4] : distance was 9 ,number of possibilities got reduced to 488000
I asked for permutation [9 5 6 0 1 2 3 7 4 8] : distance was 7 ,number of possibilities got reduced to 36752
I asked for permutation [3 5 0 2 1 4 8 7 9 6] : distance was 10 ,number of possibilities got reduced to 7281
I asked for permutation [1 7 5 9 0 2 3 4 6 8] : distance was 10 ,number of possibilities got reduced to 437
I asked for permutation [9 1 6 3 2 8 7 0 4 5] : distance was 6 ,number of possibilities got reduced to 121
I asked for permutation [9 3 6 0 2 7 4 1 8 5] : distance was 8 ,number of possibilities got reduced to 29
I asked for permutation [9 6 3 0 5 8 7 2 4 1] : distance was 7 ,number of possibilities got reduced to 4
I asked for permutation [2 1 6 0 3 8 5 9 4 7] : distance was 0 ,number of possibilities got reduced to 1
[2 1 6 0 3 8 5 9 4 7] is my final guess
[2 1 6 0 3 8 5 9 4 7] was the correct answer