What Are the Different Types of Digital Gadgets?
Guessing numbers (also known as Bulls and Cows) is an ancient puzzle game of cryptographic deciphering. It originated in the middle of the 20th century and is usually played by two or more people. It can also be played by one person and a computer.
Guess the number
(An ancient puzzle game of password cracking)
Guessing numbers (also known as Bulls and Cows) is an ancient puzzle game of cryptographic deciphering. It originated in the middle of the 20th century and is usually played by two or more people. It can also be played by one person and a computer.
- Chinese name
- Guess the number
- Foreign name
- Bulls and Cows
- game type
- Puzzle
- Time of origin
- Mid 20th century
- Country of origin
The standard rules are explained first, and then several variations are introduced.
Usually played by two people, one figure out and one guess. People who figure out numbers should think about a four number without repeating numbers, and they cannot let the guessing person know. Guess who can start guessing. Every time a number is guessed, the number of people who want to give it will give A and B according to the number, where the number before A indicates the number of the correct number, and the number before B indicates the number of the correct number and the wrong number. .
For example, if the correct answer is 5234, and the person who guessed it is 5346, it is 1A2B. One of the positions of 5 is right, and it is recorded as 1A. The numbers of 3 and 4 are correct, and the position is not, so it is recorded as 2B. Together, it is 1A2B.
Then the person who guesses continues to guess according to the number of A and B of the questioner, until the guess (ie 4A0B).
The strategy of solving a guessing number game usually has two goals: one is to ensure that the game is won under the limit of guesses, and the other is to use as few guesses as possible. The first goal pursues the least guesses in the worst case, and the second goal pursues the least guesses in the average case. For certain digital and digital rule combinations, these two goals cannot be achieved simultaneously. For example, for a 4-digit, 6-digit Mastermind game, the strategy with the least average guesses requires an average of 4.340 times, but the worst requires 6 guesses; if the limit is limited to a maximum of 5 times, the strategy with the least average guesses requires Average 4.341 times. [1]
The solution requires at least 7 guesses. The solution with the least average number was proposed by Tanaka Tetsu and 1996, with an average number of 5.213 times. [2]
The system's guessing strategy can be divided into three categories: simple strategy, heuristic strategy and optimal strategy. Let's take the standard rules (10 digits, 4 digits, excluding repeated digits) as examples to introduce these types of strategies. These strategies also apply to other rule variations.
This strategy is very straightforward-guess the first of the possible answers every time. For example, first guess 1234. If the feedback is 2A0B, the possible answers include 1256, 1257, 5236, and so on. According to the simple strategy, guess 1256 next time because 1256 is the smallest number among all possible answers.
The advantage of the simple strategy is that it is very fast, but the disadvantage is that it requires a lot of guesses. For standard rules, the simple strategy requires a maximum of 9 guesses, and an average of 5.560.
This type of strategy is the most common solution for guessing numbers games. The algorithm steps are as follows:
a. First guess 1234 and get the first feedback (xAyB).
b. From all numbers, filter out all possible numbers that meet the known feedback, and call it the "possible set".
c. For all numbers (not just the possible set that is screened out), evaluate the "good or bad" of each number one by one and give it a score. Pick the number with the highest score and guess. If multiple numbers have the same score, the number in the possible set is preferred.
d. Repeat step bc until 4A0B is guessed.
Obviously, the focus of heuristic strategy is how to evaluate the "good or bad" of a number? Many intuitive evaluation indicators have been proposed. The introduction is as follows:
Worst-case indicator (Knuth, 1977) [3] : Given a number, consider the number of elements in different feedback partitions brought by this number, and choose the number with the least number of elements in the largest feedback partition as the next guess . For the standard rule, this evaluation index requires a maximum of 7 guesses, with an average of 5.385 times.
Average condition indicator (Irving, 1978): This is a fairly intuitive indicator, which has a good effect under various rule variants. Given a number, if I guessed that number, how big would my "possible set" shrink on average? Pick the guess that minimizes the expected size of the possible set. For the standard rule, this evaluation index requires a maximum of 7 guesses, and an average of 5.268 times.
Expected steps indicator (Neuwirth, 1982): Also known as the "entropy" indicator. Given a number, this indicator calculates if you guess this number, then how many steps are needed to guess the answer. Of course, this number of steps is only a rough estimate. It assumes that each possible guess can reduce the possible set by half (or a certain constant multiple k), so the estimated step number is a logarithmic function of the possible set size, that is, the estimated step number = log (number of possible elements in the set). For the standard rule, this evaluation index requires a maximum of 7 guesses, and an average of 5.265 times.
Feedback number indicator (Kooi, 2005) [4] : Given a number, this indicator calculates the number of different feedbacks that the number may bring. The more feedback the better. For the standard rule, this evaluation index requires a maximum of 8 guesses and an average of 5.308 times.
It's also worth noting that the effectiveness of heuristics often depends on the arrangement of all numbers. But the impact is generally small.
The optimal strategy for a guessing number game needs to be obtained by a computer using exhaustion. The idea is that because the choices for each guess are limited (because the total number of digit combinations is limited), and we know that all answers must be guessed within a limited number of times, the computer can exhaust all guesses and find out Best strategy.
In addition, some literatures use genetic algorithms to solve the problem of guessing numbers, which will not be described in detail here.
The following is a list of the effects of the above-mentioned solutions when no rules are used for reference. These results are calculated by a computer program.
Standard rules
For standard rules (4 digits, 10 digits, no repeating digits), the table below lists the maximum guesses, average guesses, and number of answers for each guess. For example, using the "average situation indicator" requires a maximum of 7 guesses, an average of 5.268 guesses, and 1885 numbers that require 6 guesses.
algorithm | Average times | 1 time | 2 times | 3 times | 4 times | 5 times | 6 times | 7 times | 8 times | 9 times |
Simple strategy | 5.560 | 1 | 13 | 108 | 596 | 1668 | 1768 | 752 | 129 | 5 |
Worst case indicator | 5.385 | 1 | 3 | 44 | 515 | 2124 | 2151 | 202 | - | - |
Average condition indicator | 5.268 | 1 | 4 | 59 | 574 | 2430 | 1885 | 87 | - | - |
Expected steps indicator | 5.265 | 1 | 4 | 53 | 560 | 2515 | 1796 | 111 | - | - |
Number of feedback indicators | 5.308 | 1 | 11 | 80 | 556 | 2277 | 1929 | 183 | 3 | - |
Mastermind rules
The following table lists the effects of various algorithms when applied to Mastermind rules (4-digit, 6-digit, repeatable). [4]
algorithm | Average times | 1 time | 2 times | 3 times | 4 times | 5 times | 6 times | 7 times | 8 times | 9 times |
Simple strategy | 5.765 | 1 | 4 | 25 | 108 | 305 | 602 | 196 | 49 | 6 |
Worst case indicator | 4.476 | 1 | 6 | 62 | 533 | 694 | - | - | - | - |
Average condition indicator | 4.395 | 1 | 10 | 54 | 645 | 583 | 3 | - | - | - |
Expected steps indicator | 4.424 | 1 | 4 | 70 | 611 | 590 | 20 | - | - | - |
Number of feedback indicators | 4.373 | 1 | 12 | 72 | 635 | 569 | 7 | - | - | - |
