** "Hit & Blow" ** is It is a type of number guessing game in which two players play against each other, and is called ** Bulls & Cows ** overseas.
** Numer0n **, which was featured on TV programs, is famous as a derivative game. https://ja.wikipedia.org/wiki/Numer0n
The content of the game itself seems to have been devised over a century ago.
There is also a board game called ** "Mastermind" ** that was sold around 1970. The rules are slightly different from ** Hit & Blow (Bulls & Cows) **.
The rules of the ** Hit & Blow (Bulls & Cows) ** game are as follows.
It's usually played in 4 digits, but you can also play in 3 digits or any other number of digits.
On a piece of paper, each player writes a four-digit secret number. All numbers must be different.
Then, in turn, the player guesses the number of the opponent giving the number of matches and asks questions. ** "Hit" ** if the matching numbers are in the correct position, ** "Blow" ** if they are in different positions. (In Numer0n, they are called ** EAT ** and ** BITE **, respectively.)
For example
My answer (solution): ** 4721 ** Opponent Question: ** 1234 **
If, the answer is
** 1 Hit ** and ** 2 Blow ** (** Hit ** is ** "2" **, ** Blow ** is ** "4" ** and ** "1" **.)
And tell the result to the other party. When the other person's question is over, ask the other person the number you guessed.
The person who guesses the opponent's ** secret number (answer (solution)) ** with ** fewer questions ** than the opponent is the ** winner **.
The ** Hit & Blow (Bulls & Cows) ** rules are simple and
Generate a random answer and answer the number of bulls and cows to human questions The ** Questioner's Program ** was created early on.
The first one is famous for ** "MOO" **, Multics Operating System using ** PL / I ** by ** JM Grochow ** in 1970 Written for .wikipedia.org/wiki/Multics).
Some ** Unix ** of ** BSD series ** still have the ** MOO ** question program installed as standard.
As a beginner's task in programming, it seems that it is often asked at schools.
On the other hand, the ** questioner-side program ** that lets the computer play ** Hit & Blow (Bulls & Cows) ** Compared to the ** questioner side program **, the amount of calculation is large and complicated.
In fact, on a typical 16-bit PC 30 years ago, It took a few minutes to get the answer right.
However, with today's PCs, the correct answer can be found in an instant. (When it comes to processing 8 digits or more in Python, you have to wait for a while)
By the way, even if you write the process to find a 4-digit solution in ** Python3 **, With modern CPUs, it seems that the solution can be found within ** 0.02 seconds **. Even the ** 10,000 questions ** were completed in ** 170 seconds **. (For Inten (R) Core (TM) i5-8265U CPU @ 1.60GHz (1.80GHz))
Around 1995-2000, it began to be described in ** JavaScript ** etc. Many sites that can be played with the ** questioner side program ** on the Web have also appeared. You can still find many by searching.
In the case of a 4-digit game, the number of candidates at the time of the first question is
10×9×8×7 = 5040
There is.
Depending on the number you asked and the result of the answer, the set that meets the conditions for the answer will be decided.
How to ask the best question for the set It is a point to make a strong ** questioner side program **.
This story will be discussed later in a later chapter.
In ** 1987 **, this issue was raised as an issue for ** bit ** ** nanopico classroom **. The winner's program at this time was that the ** minimum average number of questions ** was ** 5.22 (total number of questions 26347) **.
In ** 1996 **, the ** minimum average number of questions 26274/5040 = 5.2131 ** was achieved.
In the case of 4-digit ** Hit & Blow (Bulls & Cows) **, it has been proved that any number can be resolved within ** 7 turns **.
** Nanopico classroom ** http://www.pro.or.jp/~fuji/computerbooks/algorithm/nanopico.bit.html
** Minimum question strategy and strongest strategy of number guessing game MOO **
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/moo/moo.html
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/papers/gpw96.pdf
The created program is arranged below. https://github.com/NobuyukiInoue/pyHitAndBlow
It's time to decide the number for the first question, There is a way to ask questions such as ** "0123" **,
If the other party is a human, measures will be taken, so Random numbers are used to generate and use n-digit random numbers that are different from each other.
** In the questioner side program **, the process of preparing the answer number, ** In the questioner side program **, in the process of selecting the number to ask a question,
You will need each.
In my program, I calculated ** Hits ** and ** Blows ** for questions. To simplify (not speed up) I decided to treat the ** n-digit number ** of the answer or question as a ** string **.
If you generate random numbers one digit at a time and concatenate them, the procedure is as follows.
Returns n different random numbers(random.randint()Edition)
def create_random_n_digits_number(n:int) -> str:
target_number_str = ""
for _ in range(n):
while True:
d = str(random.randint(0, 9))
if d not in target_number_str:
target_number_str += d
break
return target_number_str
By the way, the above process is This can be achieved in one line by using the ** sample function ** of the ** random module **.
Returns n different random numbers(random.sample()Edition)
def create_random_n_digits_number(n:int) -> str:
return "".join([str(_) for _ in random.sample(list(range(10)), n)])
Also, when handling the answer number or question number as a character string, ** Hit number ** and ** Blow number ** can be collated by the following processing.
Match the question number with the solution candidate number and return the Hit number and Blow number (Part 1)
def response_check(n:int, answer_number:str, target_number:str) -> (int, int):
"""
response check.
"""
H, B = 0, 0
for i in range(0, n):
if target_number[i] == answer_number[i]:
H += 1
else:
for j in range(0, n):
if i != j and target_number[i] == answer_number[j]:
B += 1
return H, B
Or
Match the question number with the solution candidate number and return the Hit number and Blow number (Part 2)
def response_check(n:int, answer_number:str, target_number:str) -> (int, int):
"""
response check.
"""
H, B = 0, 0
for n, m in zip(answer_number, target_number):
if n == m:
H += 1
elif n in target_number:
B += 1
return H, B
By the way, the processing time of the second is shorter.
Next is the process of generating n-digit candidates for the first question.
In the case of 4 digits, the range of numbers is 0123-9876
,
The number of solution candidates is `` `9 * 8 * 7 * 6 = 5040```.
There are various ways to generate it, If you call it recursively to correspond to n digits, it will be as follows.
Make a list of candidate numbers for the (first) solution
def create_target_numbers(n:int)-> [str]:
"""
create target numbers.
"""
target_numbers = []
def sub_create_target_numbers(n, workStr):
if n == 0:
target_numbers.append(workStr)
return
for i in range(10):
if str(i) not in workStr:
sub_create_target_numbers(n - 1, workStr + str(i))
if n == 1:
for i in range(10):
target_numbers.append(str(i))
elif n > 1:
for i in range(10):
sub_create_target_numbers(n - 1, str(i))
return target_numbers
We have prepared a program that only outputs n-digit random numbers that are different from each other. This program is used for testing the ** Questioner Program **.
https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/create_random_n_digits_number.py https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/mylibs/lib_hit_and_blow.py
The format of the questioner's program is as follows.
create_random_n_digits_number.py [N]
option | Description |
---|---|
N | Number of digits (2 <= N <= 10) (default value is 4) |
$ python create_random_n_digits_number.py 4
2357
The ** questioner side program ** that I created is below. ** Questioner side program ** is a relatively simple program.
Since it will be long, I will omit posting the source.
https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/pyHitAndBlow_defence.py https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/mylibs/lib_hit_and_blow.py
The format of the argument is as follows.
pyHitAndBlow_defence.py [N [enable print] [answer number]]]
option | Description |
---|---|
N | Number of digits in answer (2 <= N <= 10) (default value is 4) |
enable_print | unused (default value is False) |
answer_number | Answer number. You can also specify the answer number in advance. |
$ python pyHitAndBlow_defence.py 4
N ... 4
When you want to end on the way, please input 0
[1] : select number xxxx = 3429 <--- "3429"Enter
input response is Hit = 0, Blow = 2
[2] : select number xxxx = 7594 <--- "7594"Enter
input response is Hit = 0, Blow = 1
[3] : select number xxxx = 9613 <--- "9613"Enter
input response is Hit = 1, Blow = 2
[4] : select number xxxx = 9386 <--- "9386"Enter
input response is Hit = 2, Blow = 1
[5] : select number xxxx = 9036 <--- "9036"Enter
input response is Hit = 1, Blow = 3
[6] : select number xxxx = 9360 <--- "9360"Enter
input response is Hit = 4, Blow = 0
congratulations!!!
my answer number is 9360.
===== challenge history ======
[1] .... 3429 (0, 2)
[2] .... 7594 (0, 1)
[3] .... 9613 (1, 2)
[4] .... 9386 (2, 1)
[5] .... 9036 (1, 3)
[6] .... 9360 (4, 0)
The questioner side program is below.
https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/pyHitAndBlow_offence.py https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/mylibs/lib_hit_and_blow.py
The general processing flow of the questioner's program is
Processing,
If the number of digits is 4, repeat until the answer is ** Hits 4 **.
The process of 3 is as follows.
Regenerate the next list of "candidate solutions", leaving only candidates with matching hits and blows
# create new canidiates numbers list.
new_target_numbers = []
for current_number in target_numbers:
if answer_check(n, current_number, selected_number, H, B):
# new candidates number add.
new_target_numbers.append(current_number)
target_numbers = new_target_numbers
In the first question, no matter which number you ask
The probability of correct answer is ** 1/5040 ** when the number of digits is 4 and The number of questions required to find a solution is undecided,
Depending on the result of answering the second question At worst, the total number of questions to reach the solution is determined.
Especially in this second question
** Instead of choosing the number to ask next from the list of "candidate numbers" ** ** It is better to select "Number that minimizes the number of questions until a solution is found" ** and ask a question.
The average number of questions is small. This method is called ** "minimum question strategy" **.
After trying about 10,000 times,
** When selected from the list of "Numbers that are candidate solutions" ** The average number of questions was about ** 5.469 **,
Only the second question (in the current implementation), If you ask in ** "Minimum Question Strategy" ** The average number of questions has dropped to ** 5.436 **.
In the end, it will drop to ** 5.2131 **, We haven't implemented that much (at this time).
Perhaps you also need to consider the random number bias in the random module of python. (Random-related libraries that are generally used in practice have variations in that there are values that are likely to occur and values that are unlikely to occur because the inside is expressed in binary.)
** "Choose the next question number from the solution candidates" ** The process is as follows.
Using random numbers, return an integer in the range of elements (0 to len (target_numbers) -1) in the ** solution candidate list **, Returns the value of that element as the number to ask next.
From the second time onward, the same number as the one you asked in the past may be selected, so If the numbers are the same, the candidates are selected again.
Select the number to ask the next question from the solution candidates
def create_canidiate_number(n:int, target_numbers:[str], history:HistoryRecords) -> str:
"""
create canidiate number.
"""
if len(history.challenge) == 0:
index = random.randint(0, len(target_numbers) - 1)
return target_numbers[index]
else:
while True:
index = random.randint(0, len(target_numbers) - 1)
if target_numbers[index] in history.challenge:
continue
return target_numbers[index]
In this method, I explained that the average number of questions is ** 5.469 **, but Still, it is ** quite strong ** when compared with humans. (By the way, I can hardly win)
In the case of "minimum question strategy", the number of the second question is determined by the number and answer of the first question.
If the first question is, for example, ** "0123" **, select a number like the one below.
The number you select is not limited to solution candidates, so In some cases, a number that is unlikely to be answered correctly will be selected,
It has been proven that the average number of questions to answer correctly decreases.
First response | Second question | Element count | Total number of questions | With the first question number Second question番号の difference |
---|---|---|---|---|
4H0B | ---- | 1 | 0 | --- |
3H0B | 0245 | 24 | 73 | 1H1B |
2H2B | 0132 | 6 | 15 | 2H2B |
2H1B | 0145 | 72 | 240 | 2H0B |
2H0B | 0245 | 180 | 659 | 1H1B |
1H3B | 0134 | 8 | 22 | 2H1B |
1H2B | 0245 | 216 | 804 | 1H1B |
1H1B | 0245 | 720 | 2992 | 1H1B |
1H0B | 0456 | 480 | 1446 | 1H0B |
0H4B | 1230 | 9 | 23 | 0H4B |
0H3B | 1435 | 264 | 1004 | 0H2B |
0H2B | 1245 | 1260 | 5548 | 0H2B |
0H1B | 1456 | 1440 | 6595 | 0H1B |
0H0B | 4567 | 360 | 1446 | 0H0B |
References) Minimum question strategy and strongest strategy of number guessing game MOO
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/papers/gpw96.pdf
Choose the number that minimizes the number of questions
def create_canidiate_number4_Minimum_question_strategy(n:int, target_numbers:[str], history:HistoryRecords) -> str:
"""
create canidiate number.
(Minimum question strategy)
"""
if len(history.challenge) == 1:
while True:
selected_number = create_random_n_digits_number(n)
if selected_number in history.challenge:
continue
H, B = response_check(n, history.challenge[-1], selected_number)
if history.response[-1] == [3, 0]:
if (H, B) == (1, 1):
return selected_number
elif history.response[-1] == [2, 2]:
if (H, B) == (2, 2):
return selected_number
elif history.response[-1] == [2, 1]:
if (H, B) == (2, 0):
return selected_number
elif history.response[-1] == [2, 0]:
if (H, B) == (1, 1):
return selected_number
elif history.response[-1] == [1, 3]:
if (H, B) == (2, 1):
return selected_number
elif history.response[-1] == [1, 2]:
if (H, B) == (1, 1):
return selected_number
elif history.response[-1] == [1, 1]:
if (H, B) == (1, 1):
return selected_number
elif history.response[-1] == [1, 0]:
if (H, B) == (1, 0):
return selected_number
elif history.response[-1] == [0, 4]:
if (H, B) == (0, 4):
return selected_number
elif history.response[-1] == [0, 3]:
if (H, B) == (0, 2):
return selected_number
elif history.response[-1] == [0, 2]:
if (H, B) == (0, 2):
return selected_number
elif history.response[-1] == [0, 1]:
if (H, B) == (0, 1):
return selected_number
elif history.response[-1] == [0, 0]:
if (H, B) == (0, 0):
return selected_number
else:
return selected_number
else:
while True:
index = random.randint(0, len(target_numbers) - 1)
if target_numbers[index] in history.challenge:
continue
return target_numbers[index]
The format of the questioner's program is as follows.
pyHitAndBlow_offence.py [N [enable print] [answer number]]]
option | Description |
---|---|
N | Number of digits in answer (2 <= N <= 10) (default value is 4) |
enable print | Specify display / non-display of the remaining solution candidate list (default value is False) |
anser_number | answer number |
The default number of digits is 4. Candidates for the remaining floors are examples of execution when hidden. Enter ** Hits ** and ** Blows ** manually.
$ python pyHitAndBlow_offence.py
(remaining count = 5040) Is your number 7016 ?
[1] : please input H, B = 0,1 <-- "0,1"Besides"0 1", "01"But yes
(remaining count = 1440) Is your number 2950 ?
[2] : please input H, B = 0,1
(remaining count = 378) Is your number 4365 ?
[3] : please input H, B = 0,2 <-- "0,2"Besides"0 2", "02"But yes
(remaining count = 99) Is your number 3628 ?
[4] : please input H, B = 0,2
(remaining count = 19) Is your number 1234 ?
[5] : please input H, B = 4,0 <-- "4,0"Besides"4 0", "4"But yes
calculate successful.
===== challenge history =====
[1](5040) ---> 7016 (0, 1)
[2](1440) ---> 2950 (0, 1)
[3]( 378) ---> 4365 (0, 2)
[4]( 99) ---> 3628 (0, 2)
[5]( 19) ---> 1234 (4, 0)
If you make a mistake in entering the ** answer ** for the answer you have prepared, Since there are no solution candidates in the middle, it ends before the ** hit number reaches 4 **.
** Compare the number asked and your answer ** and be careful ** to make sure. ** I myself make mistakes about 5-10% of the time. ** **
Since ** calculate failed ** did not occur in tens of thousands of tests, There seems to be no bug in the program (probably). (The test script will be described later.)
The following is
The answer I prepared was intended to be ** "1234" **, Because I answered ** "0 2" ** instead of ** "2 0" ** in the first response. This is an example of exiting without reaching ** Hits == 4 **.
$ python pyHitAndBlow_offence.py
(remaining count = 5040) Is your number 9238 ?
[1] : please input H, B = 0 2 <--- "2 0"Not by mistake"0 2"Is inputting
input response is Hit = 0, Blow = 2
(remaining count = 1260) Is your number 1792 ?
[2] : please input H, B = 1 1
input response is Hit = 1, Blow = 1
(remaining count = 204) Is your number 2763 ?
[3] : please input H, B = 0 2
input response is Hit = 0, Blow = 2
(remaining count = 47) Is your number 1324 ?
[4] : please input H, B = 2 2
input response is Hit = 2, Blow = 2
(remaining count = 0) calculate failed.
===== challenge history ======
[1](5040) ---> 9238 (0, 2)
[2](1260) ---> 1792 (1, 1)
[3]( 204) ---> 2763 (0, 2)
[4]( 47) ---> 1324 (2, 2)
If you have trouble entering the answer,
After specifying the number of digits and displaying the solution candidates, give the correct answer number, You can also have them answer automatically.
In the test script described later, the ** questioner side program ** is executed in this ** automatic answer mode **.
$ python pyHitAndBlow_offence.py 4 false 1234
N ... 4
set answer number ... 1234
(remaining count = 5040) Is your number 1653 ?
input response is Hit = 1, Blow = 1
(remaining count = 720) Is your number 7463 ?
input response is Hit = 0, Blow = 2
(remaining count = 165) Is your number 6054 ?
input response is Hit = 1, Blow = 0
(remaining count = 16) Is your number 3257 ?
input response is Hit = 1, Blow = 1
(remaining count = 2) Is your number 1234 ?
input response is Hit = 4, Blow = 0
calculate successful.
===== challenge history =====
[1](5040) ---> 1653 (1, 1)
[2]( 720) ---> 7463 (0, 2)
[3]( 165) ---> 6054 (1, 0)
[4]( 16) ---> 3257 (1, 1)
[5]( 2) ---> 1234 (4, 0)
A test script is also available for testing the questioner program. https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/test_pyHitAndBlow.py https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/testscripts/test_pyHitAndBlow.sh https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/testscripts/test_pyHitAndBlow.ps1
Both test scripts take as an argument You can specify ** the number of digits in the answer and question ** and ** the number of times the questioner's program is executed **. After executing the question-side program a specified number of times, the ** average number of questions ** and ** execution time ** required until the final correct answer are output.
For reference, the questioner side program in automatic answer mode, We will post the execution time when the solution is 4 digits and executed 10000 times.
Item | Value |
---|---|
CPU | Inten(R) Core(TM) i7-8559U CPU @ 2.70GHz |
Memory | 16GB (LPDDR3 / 2133MHz) |
file name | OS | Execution time |
---|---|---|
test_pyHitAndBlow.py | Windows 10 Pro(version 2004) | 166[s] |
test_pyHitAndBlow.py | Windows 10 Pro(version 2004) (Out-Export to a file with the File cmdlet. HDD may be slower) |
129[s] |
test_pyHitAndBlow.py | WSL2(ubuntu18.04) | 123[s] |
type | OS | Execution time |
---|---|---|
test_pyHitAndBlow.sh(bash) | WSL2(ubuntu18.04) | 530[s] |
test_pyHitAndBlow.ps1(PowerShell) | WSL2(ubuntu18.04) | 554[s] |
test_pyHitAndBlow.ps1(PowerShell) | Windows 10 Pro(version 2004) | 1295[s] |
In the shell script version, pyHitAndBlow_offence.py is started every time a question is asked. Due to the large process startup / termination overhead, it is considerably slower than the single process version.
python test_pyHitAndBlow.py [N [MAX]]
$ python test_pyHitAndBlow.py 4 10
...
...
(remaining count = 2) Is your number 3970 ?
input response is Hit = 2, Blow = 2
(remaining count = 1) Is your number 9370 ?
input response is Hit = 4, Blow = 0
===== challenge history ======
[1] .... 5076 (1, 1)
[2] .... 6049 (0, 2)
[3] .... 5634 (0, 1)
[4] .... 4870 (2, 0)
[5] .... 3970 (2, 2)
[6] .... 9370 (4, 0)
# Latest Average = 5.4000
==== ResultCount history =====
ResultCount[0] = 7
ResultCount[1] = 5
ResultCount[2] = 6
ResultCount[3] = 5
ResultCount[4] = 4
ResultCount[5] = 5
ResultCount[6] = 5
ResultCount[7] = 5
ResultCount[8] = 6
ResultCount[9] = 6
======== distribution ========
0 ... 0
1 ... 0
2 ... 0
3 ... 0
4 ... 1
5 ... 5
6 ... 3
7 ... 1
8 ... 0
9 ... 0
10 ... 0
11 ... 0
12 ... 0
Distribution list Total = 10
==============================
Total Questions = 54
Total Average = 5.4
==============================
start ... 2020-09-05 12:03:34.129205
end ... 2020-09-05 12:03:34.271266
test_pyHitAndBlow.sh [N [MAX]]
$ ./testscripts/test_pyHitAndBlow.sh 4 10
...
...
(remaining count = 6) Is your number 6097 ?
input response is Hit = 0, Blow = 2
(remaining count = 1) Is your number 8160 ?
input response is Hit = 4, Blow = 0
calculate successful.
===== challenge history ======
[1](5040) ---> 4065 (1, 1)
[2]( 720) ---> 4203 (0, 1)
[3]( 180) ---> 8495 (1, 0)
[4]( 26) ---> 1467 (1, 1)
[5]( 6) ---> 6097 (0, 2)
[6]( 1) ---> 8160 (4, 0)
# Latest Average = 5.4000
==== ResultCount history =====
result_count[0] = 4
result_count[1] = 5
result_count[2] = 6
result_count[3] = 5
result_count[4] = 6
result_count[5] = 4
result_count[6] = 5
result_count[7] = 6
result_count[8] = 7
result_count[9] = 6
======== distribution ========
0 ... 0
1 ... 0
2 ... 0
3 ... 0
4 ... 2
5 ... 4
6 ... 3
7 ... 1
8 ... 0
9 ... 0
10 ... 0
11 ... 0
12 ... 0
Distribution list total = 10
==============================
Total Questions = 53
Total average = 5.3000
==============================
start ... 2020-09-05 13:09:44
end ... 2020-09-05 13:09:46
total execution time ... 2[s]
test_pyHitAndBlow.ps1 [N] [MAX]
D:\pyHitAndBlow> .\testscripts\test_pyHitAndBlow.ps1 4 10
...
...
(remaining count = 16) Is your number 3895 ?
input response is Hit = 2, Blow = 2
(remaining count = 1) Is your number 5893 ?
input response is Hit = 4, Blow = 0
calculate successful.
===== challenge history ======
[1](5040) ---> 6380 (0, 2)
[2](1260) ---> 4069 (0, 1)
[3]( 304) ---> 1938 (0, 3)
[4]( 16) ---> 3895 (2, 2)
[5]( 1) ---> 5893 (4, 0)
# Latest Average = 5.4
==== ResultCount history =====
ResultCount[0] = 6
ResultCount[1] = 5
ResultCount[2] = 7
ResultCount[3] = 4
ResultCount[4] = 5
ResultCount[5] = 7
ResultCount[6] = 4
ResultCount[7] = 6
ResultCount[8] = 5
ResultCount[9] = 5
======== distribution ========
0 ... 0
1 ... 0
2 ... 0
3 ... 0
4 ... 2
5 ... 4
6 ... 2
7 ... 2
8 ... 0
9 ... 0
10 ... 0
11 ... 0
Distribution list Total = 10
==============================
Total Questions = 54
Total Average = 5.4
==============================
start ... 2020-09-05 12:20:56
end ... 2020-09-05 12:20:57
Total execution time ... 1.1599779[s]
For the minimum average strategy,
As mentioned above Currently only implemented when ** n = 4 **, We are implementing the minimum question strategy only for the second question.
others, There may be some mistakes in the program, but I would appreciate it if you could kindly inform me.