n桁版Hit&Blow(ヌメロン(Numer0n))の出題者側プログラムおよび質問者側プログラム

1. はじめに

「Hit&Blow (ヒット・アンド・ブロー)」 とは、
２人で対戦する数当てゲームの一種で、海外ではBulls&Cowsと呼ばれています。

派生形のゲームとしては、テレビ番組でも取り上げられた**Numer0n(ヌメロン)**が有名ですね。
https://ja.wikipedia.org/wiki/Numer0n

ゲームの内容自体は１世紀以上前には考案されていたようです。

• Bulls&Cows
  
  https://en.wikipedia.org/wiki/Bulls_and_Cows

1970年頃に販売された**「マスターマインド」**と呼ばれるボードゲームもあります。
Hit&Blow(Bulls&Cows) とは多少ルールが異なります。

• マスターマインド
  
  https://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%B9%E3%82%BF%E3%83%BC%E3%83%9E%E3%82%A4%E3%83%B3%E3%83%89

2. ゲームのルール

Hit&Blow(Bulls&Cows) のゲームのルールは以下のようなものです。

通常4桁でプレイされますが、3桁または他の任意の桁数でプレイすることもできます。

紙の上に、プレーヤーはそれぞれ4桁の秘密の番号を書きます。
数字はすべて異なっている必要があります。

次に、順番に、プレーヤーは対戦の数を与える相手の番号を推測し、質問していきます。
一致する数字が正しい位置にある場合は 「Hit」 であり、異なる位置にある場合は 「Blow」 です。
（Numer0nでは、それぞれ、EAT（イート）、 BITE（バイト） と呼ばれます。）

たとえば、

自分の答え（解）：4271
対戦相手の質問：1234

の場合、回答は

1つのHit と 2つのBlow
（Hit は 「2」 , Blow は 「4」 と 「1」 です。）

となり、その結果を相手に伝えます。
相手の質問が終わったら、今度は自分が推測した番号を相手に質問します。

相手よりも 少ない質問回数 で相手の 秘密の番号（答え（解）） を当てた人が、 勝者 となります。

3. 出題者側プログラムおよび質問者側プログラム

3.1. 出題者側プログラム

Hit&Blow(Bulls&Cows) のルールは単純であり、

ランダムな答えを生成し、人間の質問に対してbull数, cow数を答える
出題者側プログラムは早くから作られていました。

最初のものとしては 「MOO」 が有名で、
1970年に JM Grochow によって PL/I を使ってMulticsオペレーティングシステム向けに書かれました。

BSD系 の Unix には、今でも標準で MOO の出題プログラムがインストールされているものがあります。

プログラミング初級の課題として、学校などで出題されることも多いようです。

3.2. 質問者側プログラム

一方、Hit&Blow(Bulls&Cows)をコンピュータにプレイさせる質問者側プログラムは、
出題者側プログラムと比べると計算量も多く複雑です。

実際に、30年前の一般的な 16bit PC では、
正解するまでに数分の処理時間がかかっていました。

とはいえ、昨今のPCでは一瞬で正解が求まります。
（Pythonで8桁以上の処理となると、さすがに少し待たされる）

ちなみに、4桁の解を求める処理を Python3 で記述しても、
最近のCPUでは、0.02秒以内で解が求まるようです。
10,000問の出題でも、170秒程度で終了しました。
（Inten(R) Core(TM) i5-8265U CPU @ 1.60GHz(1.80GHz)の場合 ）

1995〜2000年頃には、JavaScript 等でも記述されるようになり、
Web上の質問者側プログラムで遊べるサイトも数多く登場しました。
現在でも検索すればたくさん見つかります。

４桁でのゲームの場合、初回の質問時の候補数は、

10×9×8×7 = 5040

あります。

質問した番号および回答結果に応じて、回答の条件を満たす集合が決まりますが、

その集合に対して、最良の質問をどう求めるかが
強い質問者側プログラムを作るためのポイントとなります。

この話については、後の章で後述します。

1987年 には bit の ナノピコ教室 の課題としてこの問題が出されました。
この時の優勝者のプログラムは、最小平均質問回数 が 5.22(総質問数26347) だったそうです。

1996年 には、最小平均質問回数26274/5040 = 5.2131 が達成されています。

なお、4桁の Hit&Blow(Bulls&Cows) 場合、7ターン以内に任意の数を解決できることが証明されています。

• ナノピコ教室
  http://www.pro.or.jp/~fuji/computerbooks/algorithm/nanopico.bit.html

• 数当てゲーム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
  

4. Pythonで書いてみた

制作したプログラムは下記に配置しています。
https://github.com/NobuyukiInoue/pyHitAndBlow

初回の質問の番号を決める時ですが、
「0123」 などと決め打ちして質問する手もありますが、

相手が人間である場合には対策を取られてしまいますので、
乱数を使って互いに異なるn桁のランダムな番号を生成して使用しています。

出題者側プログラム では、答えの番号を用意する処理、
質問者側プログラム では、質問する番号を選ぶ処理で、

それぞれ必要となります。

私の作ったプログラムでは、質問に対する Hit数、Blow数 の算出を
簡素化（高速化ではない）するために、
答えや質問のn桁の番号を文字列として扱うことにしました。

１桁ずつ乱数を生成して連結すると、下記のような手順になります。

互いに異なるn桁のランダムな番号を返す(random.randint()版)

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

ちなみに、上記の処理は、
randomモジュールのsample関数を使うと１行で実現できます。

互いに異なるn桁のランダムな番号を返す(random.sample()版)

def create_random_n_digits_number(n:int) -> str:
    return "".join([str(_) for _ in random.sample(list(range(10)), n)])

また、答えの番号や質問の番号を文字列で扱う場合、
Hit数 および Blow数 は下記のような処理で照合できます。

質問の番号と解の候補の番号を照合し、Hit数とBlow数を返す（その１）

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

もしくは、

質問の番号と解の候補の番号を照合し、Hit数とBlow数を返す（その２）

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

ちなみに、その２の方が処理時間は短くて済みます。

次に、n桁の初回質問時の候補を生成する処理です。

4桁の場合、番号の範囲は 0123～9876となりますが、
解の候補の数は 10*9*8*7 = 5040 あります。

生成する方法はいろいろありますが、
n桁に対応するために再帰呼び出して記述すると、以下のようになります。

（初回の）解の候補となる番号のリストを作成する

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

4-1. 互いに異なるn桁のランダムな番号を出力するプログラム

互いに異なるn桁のランダムな番号を出力するだけのプログラムを用意しています。
このプログラムは、質問者プログラムのテスト等で使用します。

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

4-1-1. 実行方法

質問者側プログラムの書式は以下の通りです。

create_random_n_digits_number.py [N]

オプション	説明
N	桁数(2<=N<=10) (デフォルト値は4)

4-1-2. 実行例

$ python create_random_n_digits_number.py 4
2357

4-2. 出題者側プログラム

私が制作した 出題者側プログラム は下記にあります。
出題者側プログラム は比較的簡単なプログラムです。

長くなるので、ソースの掲載は割愛します。

https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/pyHitAndBlow_defence.py
https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/mylibs/lib_hit_and_blow.py

4-2-1. 実行方法

引数の書式は以下の通りです。

pyHitAndBlow_defence.py [N [enable print] [answer number]]]

オプション	説明
N	答えの桁数(2<=N<=10) (デフォルト値は4)
enable_print	未使用(default値はFalse)
answer_number	答えの番号。事前に答えの番号を指定しておくこともできます。

4-2-2. 実行例

$ python pyHitAndBlow_defence.py 4
N ... 4
When you want to end on the way, please input 0

[1] : select number xxxx = 3429        <--- "3429"と入力
input response is Hit = 0, Blow = 2
[2] : select number xxxx = 7594        <--- "7594"と入力
input response is Hit = 0, Blow = 1
[3] : select number xxxx = 9613        <--- "9613"と入力
input response is Hit = 1, Blow = 2
[4] : select number xxxx = 9386        <--- "9386"と入力
input response is Hit = 2, Blow = 1
[5] : select number xxxx = 9036        <--- "9036"と入力
input response is Hit = 1, Blow = 3
[6] : select number xxxx = 9360        <--- "9360"と入力
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)

4-3. 質問者側プログラム

質問者側プログラムは下記にあります。

https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/pyHitAndBlow_offence.py
https://github.com/NobuyukiInoue/pyHitAndBlow/blob/master/mylibs/lib_hit_and_blow.py

質問者側プログラムのおおまかな処理の流れは、

1. 「解の候補である番号」のリストを用意する
2. 「相手の質問の番号」を読み取る
3. 「相手の質問の番号」と「解の候補となる番号」を１つ１つ照合し、Hit数とBlow数が一致する候補のみ残す

の処理を、

桁数が4の場合、回答が Hit数4 になるまで繰り返していきます。

3の処理を示すと、以下のような処理になります。

Hit数とBlow数が一致する候補のみ残し、次の「解の候補である番号」のリストを再生成する

        # 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

１回目の質問では、どの番号を質問しても

正解する可能性は等しく桁数が4の場合には 1/5040 であり、
解が求まるまでに必要な質問数も未定ですが、

２回目の質問の回答の結果によって、
最悪でも解にたどり着くまでの総質問数が決まります。

特に、この２回目の質問では、

「解の候補である番号」 の一覧から次に質問する番号を選ぶのではなく、
「解が求まるまでの質問数を最小にする番号」 を選んで質問した方が、

平均質問数は少なくて済みます。
この方法のことを 「最小質問戦略」 と呼びます。

１万回ほど試行してみたところ、

「解の候補である番号」 の一覧から選んだ場合の、
質問数の平均は 5.469 程度でしたが、

（現時点での実装では）２回目の質問のみですが、
「最小質問戦略」 で質問した場合、
質問数の平均が 5.436 まで下がりました。

突き詰めていくと、5.2131 まで下がるのでしょうが、
（現時点では）そこまでは実装していません。

もしかしたら、pythonのrandomモジュールの乱数の偏りについても考慮が必要かもしれません。
（実際に一般的に使われているrandom関連のライブラリは、内部が２進数で表現されているという都合上、発生しやすい値、発生しにくい値が存在するというばらつきがあります。）

4-3-1. 解の候補から次に質問する番号を選ぶ

「解の候補から次に質問する番号を選ぶ」 場合の処理は下記のようになります。

乱数を使って、解の候補リストの要素の範囲(0〜len(target_numbers)-1)の整数を返し、
その要素の値を次に質問する番号として返します。

２回目以降は、過去に質問したものと同じ番号が選ばれる可能性があるので、
同じ番号だった場合は候補の選択をやり直しています。

解の候補から次に質問する番号を選ぶ

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]

この方法では、平均質問回数は 5.469 回程度と説明しましたが、
それでも対人間で比べるとかなり強いです。
（ちなみに私は、ほとんど勝てません）

4-3-2. 最小質問戦略

「最小質問戦略」の場合、２回目の質問は１回目の質問の番号と応答によって、次に質問する番号を決めます。

１回目の質問が例えば 「0123」 だった場合、下記のような番号を選びます。

選択する番号は、解の候補に限定されませんので、
正解する可能性がない番号が選ばれる場合もありますが、

正解するまでの平均質問数が下がることが立証されています。

１回目の応答	２回目の質問	要素数	総質問数	１回目の質問番号と ２回目の質問番号の 差異
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

参考文献）数当てゲームMOOの最小質問戦略と最強戦略
https://www.tanaka.ecc.u-tokyo.ac.jp/ktanaka/papers/gpw96.pdf

質問数を最小にする番号を選ぶ

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]

4-3-3. 実行方法

質問者側プログラムの書式は以下の通りです。

pyHitAndBlow_offence.py [N [enable print] [answer number]]]

オプション	説明
N	答えの桁数(2<=N<=10) (デフォルト値は4)
enable print	残りの解の候補一覧の表示／非表示の指定(デフォルト値はFalse)
anser_number	答えの番号

4-3-4. 実行例

デフォルトの桁数は4です。
残りの階の候補は非表示の場合の実行例です。
Hit数 と Blow数 は手入力してください。

$ python pyHitAndBlow_offence.py

(remaining count = 5040) Is your number 7016 ?
[1] : please input H, B = 0,1      <-- "0,1" のほか、"0 1", "01" でも可

(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" のほか、"0 2", "02" でも可

(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" のほか、"4 0", "4" でも可
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)

4-3-5. 回答ミスについて

自分が用意していた答えに対する回答を間違えて入力してしまった場合、
途中で解の候補がなくなるため、Hit数が4 に到達する前に終了してしまいます。

質問された番号と自分の答えをよく見比べて、間違いないように気を付けてください。
私自身も5～10%ぐらいの頻度で間違えます。

数万回のテストではcalculate failedは発生しなかったので、
プログラムにバグはなさそうです（たぶん）。
（テストスクリプトについては後述します。）

下記は、

用意した答えは "1234" のつもりでしたが、
１回目の応答で "2 0" ではなく**"0 2"** と回答してしまったため、
Hit数==4 まで到達できずに終了した例です。

$ python pyHitAndBlow_offence.py

(remaining count = 5040) Is your number 9238 ?
[1] : please input H, B = 0 2       <--- "2 0"ではなく間違えて"0 2"と入力している
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)

4-3-6. 自動回答モード

回答の入力が面倒な場合は、

桁数の指定、解の候補の表示の有無に続いて、正解の番号を与えて、
自動回答させることもできます。

後述するテスト用スクリプトでは、この自動回答モードで質問者側プログラムを実行しています。

$ 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)

4-4. 質問者側プログラムのテスト用スクリプト

質問者用プログラムのテスト用に、テストスクリプトも用意しています。
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

いずれのテストスクリプトも、引数として、
答えおよび質問の桁数 と 質問者側プログラムの実行回数 を指定できます。
質問側プログラムを指定回数実行した後、最後に正解までに要した質問の平均回数および実行時間を出力します。

4-4-1. テスト用スクリプト実行時間の目安

参考までに、自動回答モードの質問者側プログラムを、
解が4桁で10000回の実行したときの実行時間を掲載させていただきます。

• 検証環境

項目	値
CPU	Inten(R) Core(TM) i7-8559U CPU @ 2.70GHz
メモリ	16GB(LPDDR3/2133MHz)

• Python版（単一プロセス上で実行）の実行時間

ファイル名	OS	実行時間
test_pyHitAndBlow.py	Windows 10 Pro(version 2004)	166[s]
test_pyHitAndBlow.py	Windows 10 Pro(version 2004) (Out-Fileコマンドレットでファイルへ書き出し。 HDDだともっと遅いかも)	129[s]
test_pyHitAndBlow.py	WSL2(ubuntu18.04)	123[s]

• シェルスクリプト版の実行時間

種類	OS	実行時間
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]

シェルスクリプト版では、出題の度にpyHitAndBlow_offence.pyを起動しており、
プロセスの起動・終了のオーバヘッドが大きいため、単一プロセス版よりかなり遅くなっています。

4-4-2. python3版(test_pyHitAndBlow.py)

実行方法

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

4-4-3. bash用(test_pyHitAndBlow.sh)

実行方法

test_pyHitAndBlow.sh [N [MAX]]

実行例(test_pyHitAndBlow.sh)

$ ./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]

4-4-4. PowerShell用(test_pyHitAndBlow.sh)

実行方法

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]

5. おわりに

最小平均戦略については、

前述したとおり、
現時点では n = 4 のときのみの実装で、
２回目の質問のときだけ最小質問戦略を実行しています。

そのほか、
もしかしたらプログラムにミスなどが残っているかもしれませんが、
優しく知らせていただけると幸いです。