Paradox in Hit And Blow

Today, I'm going to introduce a paradox I discovered while playing a game 'Hit and Blow.'

IThe game revolves around guessing a sequence of three numbers (sometimes four numbers) set by another player. The objective is to deduce the correct three-digit number through a series of guesses. After each guess, the opposing player provides feedback in the form of 'hits' and 'blows.' A 'hit' indicates that one of the guessed numbers is correct and in its right position, while a 'blow' signifies that a guessed number is correct but placed in the wrong position. The paradox I came across emerged from the game's unique logic and the strategies used to guess the correct number sequence, which led to an unexpected and intriguing challenge that deviates from the standard approach usually taken in this game. And we cannot include same number in the game. So 001, 556, or 333 are not allowed.

For example, let's say the secret number sequence set by the other player is "482". In my first guess, I might try "123". The feedback I receive is "1 blow," indicating that one of these numbers is correct but in the wrong position. None of the numbers are in the correct position, so there are no hits.

Based on a sequence of this guessing process, both the player and their opponent, engage in a strategic battle of wits. Each participant takes turns to guess the three-digit number secretly set by the other. The game continues in this back-and-forth manner, with each player using the received clues to get closer to the correct sequence. The winner of the game is the first player who successfully guesses the opponent's number sequence accurately, achieving 3 hits.

Using Items

In Hit and Blow, players have access to four unique types of items that aid in deducing the opponent's secret number.

• High/Low: This item reveals whether each digit of the opponent's number is 'High' (5-9) or 'Low' (0-4). For example, if the result is "HHL," it indicates that the first digit is in the range of 5-9, the second could be either high or low, and the third is definitely between 0-4. This information helps narrow down the possibilities, as seen in numbers like 560, 893, or 762, where the first digit is high, the second could be high or low, but the third is low.

• Shot: This item allows players to guess a specific digit and learn if it's included in the opponent's number and its exact position. For instance, choosing '5' with a 'Shot' item and discovering the opponent's number is 851 would reveal that '5' is the second digit.

• Shuffle: With the 'Shuffle' item, players can rearrange the digits in their own guessed number. This can be strategically used to test different combinations and see how the feedback changes, helping to refine further guesses.

• Change: The 'Change' item enables players to alter one digit of their guessed number. However, it comes with a restriction: the new digit must remain within the same 'High' or 'Low' category as the original. For example, if a player’s current number is 025 and they choose to change the first digit '0', they can only replace it with other 'Low' digits like 1, 3, or 4, but not with a 'High' digit.

These items add an extra layer of strategy to the game, allowing players to gather more information and make more informed guesses about their opponent's secret number.

Calculate Candidates Programmatically

Following the introduction of these strategic items, players can further enhance their gameplay by programmatically calculating the possible candidates for the opponent's number.

This method involves using the feedback from each guess, along with the insights gained from the items, to systematically narrow down the list of potential numbers. By applying logical deductions and algorithms, players can efficiently eliminate unlikely combinations and focus on the most probable ones.

This approach not only streamlines the guessing process but also introduces a more analytical and methodical aspect to the game. The blend of strategic item usage and programmatic calculation creates a dynamic and intellectually stimulating experience, making each round of Hit and Blow not just a game of luck but a test of logic and strategic planning.

Below code snippet is designed to generate all possible combinations of three-digit numbers, ranging from 012 to 987, without any repeated digits in each number. Initially, it creates a comprehensive list of numbers using the allCandidates function, which constructs every three-digit combination by padding shorter numbers with leading zeros. Subsequently, the removeDuplicatedNumbers function filters this list to exclude any numbers containing duplicate digits. By leveraging a Set in TypeScript, the code efficiently identifies and removes numbers with repeated digits, ensuring each digit in a number is unique. The result is a refined list of all valid three-digit combinations where each digit is distinct, an essential dataset for strategies in games like Hit & Blow.

const allCandidates = (n: number): number[][] => {
  const possibleNumbers = Array.from({ length: 10 ** n }, (_, i) =>
    String(i)
      .padStart(n, "0")
      .split("")
      .map((x) => parseInt(x))
  );
  const filteredNumbers = removeDuplicatedNumbers(possibleNumbers);
  return filteredNumbers;
};

function removeDuplicatedNumbers(array: number[][]): number[][] {
  return array.filter((digits) => {
    const uniqueDigits = new Set(digits); // Create a set from those digits
    return uniqueDigits.size === digits.length; // Compare the size of the set to the length of the digits array
  });
}

And we obtain all possible candidates at first of the game.

console.log(allCandidates(3).map((cand) => cand.join("")));

// ["012", "013", "014", "015", "016", "017", "018", "019", "021", "023", "024", "025", "026", "027", "028", "029", "031", "032", "034", "035", "036", "037", "038", "039", "041", "042", "043", "045", "046", "047", "048", "049", "051", "052", "053", "054", "056", "057", "058", "059", "061", "062", "063", "064", "065", "067", "068", "069", "071", "072", "073", "074", "075", "076", "078", "079", "081", "082", "083", "084", "085", "086", "087", "089", "091", "092", "093", "094", "095", "096", "097", "098", "102", "103", "104", "105", "106", "107", "108", "109", "120", "123", "124", "125", "126", "127", "128", "129", "130", "132", "134", "135", "136", "137", "138", "139", "140", "142", "143", "145", "146", "147", "148", "149", "150", "152", "153", "154", "156", "157", "158", "159", "160", "162", "163", "164", "165", "167", "168", "169", "170", "172", "173", "174", "175", "176", "178", "179", "180", "182", "183", "184", "185", "186", "187", "189", "190", "192", "193", "194", "195", "196", "197", "198", "201", "203", "204", "205", "206", "207", "208", "209", "210", "213", "214", "215", "216", "217", "218", "219", "230", "231", "234", "235", "236", "237", "238", "239", "240", "241", "243", "245", "246", "247", "248", "249", "250", "251", "253", "254", "256", "257", "258", "259", "260", "261", "263", "264", "265", "267", "268", "269", "270", "271", "273", "274", "275", "276", "278", "279", "280", "281", "283", "284", "285", "286", "287", "289", "290", "291", "293", "294", "295", "296", "297", "298", "301", "302", "304", "305", "306", "307", "308", "309", "310", "312", "314", "315", "316", "317", "318", "319", "320", "321", "324", "325", "326", "327", "328", "329", "340", "341", "342", "345", "346", "347", "348", "349", "350", "351", "352", "354", "356", "357", "358", "359", "360", "361", "362", "364", "365", "367", "368", "369", "370", "371", "372", "374", "375", "376", "378", "379", "380", "381", "382", "384", "385", "386", "387", "389", "390", "391", "392", "394", "395", "396", "397", "398", "401", "402", "403", "405", "406", "407", "408", "409", "410", "412", "413", "415", "416", "417", "418", "419", "420", "421", "423", "425", "426", "427", "428", "429", "430", "431", "432", "435", "436", "437", "438", "439", "450", "451", "452", "453", "456", "457", "458", "459", "460", "461", "462", "463", "465", "467", "468", "469", "470", "471", "472", "473", "475", "476", "478", "479", "480", "481", "482", "483", "485", "486", "487", "489", "490", "491", "492", "493", "495", "496", "497", "498", "501", "502", "503", "504", "506", "507", "508", "509", "510", "512", "513", "514", "516", "517", "518", "519", "520", "521", "523", "524", "526", "527", "528", "529", "530", "531", "532", "534", "536", "537", "538", "539", "540", "541", "542", "543", "546", "547", "548", "549", "560", "561", "562", "563", "564", "567", "568", "569", "570", "571", "572", "573", "574", "576", "578", "579", "580", "581", "582", "583", "584", "586", "587", "589", "590", "591", "592", "593", "594", "596", "597", "598", "601", "602", "603", "604", "605", "607", "608", "609", "610", "612", "613", "614", "615", "617", "618", "619", "620", "621", "623", "624", "625", "627", "628", "629", "630", "631", "632", "634", "635", "637", "638", "639", "640", "641", "642", "643", "645", "647", "648", "649", "650", "651", "652", "653", "654", "657", "658", "659", "670", "671", "672", "673", "674", "675", "678", "679", "680", "681", "682", "683", "684", "685", "687", "689", "690", "691", "692", "693", "694", "695", "697", "698", "701", "702", "703", "704", "705", "706", "708", "709", "710", "712", "713", "714", "715", "716", "718", "719", "720", "721", "723", "724", "725", "726", "728", "729", "730", "731", "732", "734", "735", "736", "738", "739", "740", "741", "742", "743", "745", "746", "748", "749", "750", "751", "752", "753", "754", "756", "758", "759", "760", "761", "762", "763", "764", "765", "768", "769", "780", "781", "782", "783", "784", "785", "786", "789", "790", "791", "792", "793", "794", "795", "796", "798", "801", "802", "803", "804", "805", "806", "807", "809", "810", "812", "813", "814", "815", "816", "817", "819", "820", "821", "823", "824", "825", "826", "827", "829", "830", "831", "832", "834", "835", "836", "837", "839", "840", "841", "842", "843", "845", "846", "847", "849", "850", "851", "852", "853", "854", "856", "857", "859", "860", "861", "862", "863", "864", "865", "867", "869", "870", "871", "872", "873", "874", "875", "876", "879", "890", "891", "892", "893", "894", "895", "896", "897", "901", "902", "903", "904", "905", "906", "907", "908", "910", "912", "913", "914", "915", "916", "917", "918", "920", "921", "923", "924", "925", "926", "927", "928", "930", "931", "932", "934", "935", "936", "937", "938", "940", "941", "942", "943", "945", "946", "947", "948", "950", "951", "952", "953", "954", "956", "957", "958", "960", "961", "962", "963", "964", "965", "967", "968", "970", "971", "972", "973", "974", "975", "976", "978", "980", "981", "982", "983", "984", "985", "986", "987"] 

From this candidates, we need to think how should we narrow down from this massive amount of numbers to certain elaborated array.

But ah....... in this time, I will skip to write down this logic😐

Because this article is intending to just introduce paradox, and actually it's not relating to Hit and Blow algorithms itself, but "Shot" item.

Then... what's the paradox?

"Shot" item, which I described in above can narrow down candidates by judging whether chosen number is included in the opponent's one or not. And determine where the number is.

Let's consider about an example of candidates (670, 680, 690, 750, 850, 950). We can see there is 6 at the first half of array and there isn't in the second half. And same about 5 too.

When we shot 0, nothing happened because every candidates contain 0 at the same place.

When we shot 6, candidates will be (670, 680, 690) if opponent's one is included in this 3 numbers. And if not, they will be (750, 850, 950) instead.

It seems obviously better than when we shot 0, because shot 0 can't narrow down anything!

.........But is it really true?

Actually, it's not true.

It must be paradoxical because when we narrow candidates down from 6 to 3, merely the probability to answer is increased from 1/6 to 1/3.

But actually, there is no difference between shot 0 and shot 6, in this case, when we consider "How fast we can win".

Expectation Value

The probability of winning a game is not determined by the immediate chance of correctly answering a target, but rather by the expected value of the total number of answers over time.

Let's define this as ], where represents the total number of answers over time. Consider as the set of candidates, with , where denotes the size of set .

Given the current set of candidates , and assuming the next input is , we need to calculate the expected value of the total number of answers over time, represented as ]. Since each candidate has an equal probability of being the correct answer, ] can be calculated as the average of ], ..., ]:

\begin{eqnarray}E[T] &=& \frac{1}{N} \sum^{N}_{i=1} T(c_i, \mathbf{c}) \newline &=& \frac{1}{N} \sum^{N}_{i=1} E[T(c_i, \mathbf{c})]\end{eqnarray}

The reason why the average of is equal to the average of ] is due to the nature of the expected value and the uniform probability of each candidate being the correct answer.

If the length of candidates is 1, it's obvious that this expectation value must be 0 because we already know the answer. Also, if length is 2, expectation value must be 0.5 because when , we won answer if we input and actual answer is too. But we need to answer once more when actual answer is . So expectation value ] must be (0+1)/2 = 0.5. Same logic remains if input is . So we obtain expectation value as (0.5 + 0.5)/2 = 0.5.

Considering this example, we can calculate ] by this equation with some function :

\begin{align}E[T(c_i, \mathbf{c})] = \frac{1}{N} \sum^{N}_{j=1} U(c_i, \mathbf{c}^{\ast}_{ij})\end{align}

Where is the new candidates assuming actual opponent's number(answer) is and when the input is . For example, let be (670, 680, 690, 750, 850, 950) again. And if our next input is 670, assuming opponent's actual number is 850, hits and blows are 1, 0 respectively. So we obtain (850, 950) as the new candidates that satisfies hits 1, blows 0 against 670. Such way of thinking is similar to calculating entropy in information theory.

Then, what should be? We just can say it's different from at least.

But actually, this can be expressed as below:

\begin{align}U(c_i, \mathbf{c}^{\ast}_{ij}) = 1 + T(c_i, \mathbf{c}^{\ast}_{ij})\end{align}

This is because when looking at , we are not considering the next input yet, but just certain current input is and new candidates is . So we just need to plus 1 to T.

Thus, previous equation become

\begin{eqnarray}E[T(c_i, \mathbf{c})] &=& 1 + \frac{1}{N} \sum^{N}_{j=1} T(c_i, \mathbf{c}^{\ast}_{ij}) \newline &=& 1 + \frac{1}{N} \sum^{N}_{j=1} E[T(c_i, \mathbf{c}^{\ast}_{ij})\end{eqnarray}

Then finally, we obtain a recurrence formula of ].

Shot Expectation Value

Next we have to compare each shot's efficacy.

We calculate expectation value again, but against shot.

At first, fixing constant shot target number , calculate new candidates of the case of shot each places from original candidates , then calculate ] of each new candidates. After calculation of each ], we obtain expectation value of the total number of answers over time after shot n as

\begin{align} E[S_n] = \frac{1}{|\mathbf{c}|} \sum_{place} |\mathbb{c}^{\ast}_{place}| * E[T]_{place} \end{align}

This figure is a concrete example of shot 7.

Finally, using same algorithm, we obtain

as the result.

This means that how we take advantages after shot 0 and shot 6 in this case -though shot 6 narrow candidates down to half than shot 0- have no difference.

Because, whether you can win a game is determined not by the temporary probability of answering a target, but by the expected value of the total number of answers over time.

\begin{align}\end{align}