M.Hiroi's Home Page

Puzzle DE Programming

マスターマインド

[ Home | Puzzle ]

問題の説明

パズルではありませんが、今回は「マスターマインド」を解くプログラムを作りましょう。マスターマインドは拙作のページ お気楽 Scheme プログラミング入門 数当てゲーム [2] で作成した、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。 

     [6, 2, 8, 1] : 正解
-------------------------------------
1.   [0, 1, 2, 3] : cows 2 : bulls 0
2.   [1, 0, 4, 5] : cows 1 : bulls 0
3.   [2, 3, 5, 6] : cows 2 : bulls 0
4.   [3, 2, 7, 4] : cows 0 : bulls 1
5.   [3, 6, 0, 8] : cows 2 : bulls 0
6.   [6, 2, 8, 1] : cows 0 : bulls 4

   図 : マスターマインドの動作例

今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。

●推測アルゴリズム

このゲームでは、10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。コードを生成する処理は順列と同じですから、簡単にプログラムできます。次に、この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。

具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。 

[6, 2, 8, 1] が正解の場合

[0, 1, 2, 3] =>, bulls = 0, cows = 2

           [0, 1, 2, 3]  と比較する
     --------------------------------------------------------
           [0, X, X, X]  0 から始まるコードは bulls = 1
                         になるので矛盾する。
           ・・・・

           [1, 0, 3, 4]  cows = 3, bulls = 0 になるので矛盾する

           ・・・・

           [1, 0, 4, 5]  cows = 2, bulls = 0 で矛盾しない。
     --------------------------------------------------------

[1, 0, 4, 5] =>, bulls = 0, cows = 1

次は、[0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しない数字を選ぶ


         図 : マスターマインドの推測アルゴリズム

[0, 1, 2, 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0, X, X, X] というコードは [0, 1, 2, 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。

次に [1, 0, 3, 4] というコードを考えてみます。[0, 1, 2, 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1, 0, 3, 4] と [0, 1, 2, 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。

次に [1, 0, 4, 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0, 1, 2, 3] と [1, 0, 4, 5] に矛盾しないコードを選択するのです。

●プログラムの作成

それでは、プログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に bulls と cows を求める関数を作ります。 

リスト : bulls と cows を求める

# bulls を数える
def count_bulls(xs, ys):
    zs = [x == y for x, y in zip(xs, ys)]
    return zs.count(True)

# 同じ数字を数える
def count_same_number(xs, ys):
    zs = [x in ys for x in xs]
    return zs.count(True)

# bulls と cows を求める
def check_code(xs, ys):
    bulls = count_bulls(xs, ys)
    cows = count_same_number(xs, ys) - bulls
    return bulls, cows

関数 count_bulls() は bulls の個数を数えます。引数 xs と ys はコードを表すタプルです。zip() と内包表記で 2 つの要素の等値を判定し、count() で True の個数を数えれば bulls を求めることができます。

次は、cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つのコードに共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。

関数名は count_same_number() としました。この処理も内包表記を使うと簡単です。xs の要素を取り出して、それが ys に含まれているか演算子 in で判定し、count() で True の個数を数えます。関数 check_code() は 2 つのコードを受け取り、bulls と cows を求めてタプルに格納して返します。

次は生成したコードが今までの結果と矛盾していないか調べる関数 check_query() を作ります。次のリストを見てください。 

リスト : 今までの質問と矛盾しているか

def check_query(code, qs):
    for old_code, old_bulls, old_cows in qs:
        b, c = check_code(code, old_code)
        if b != old_bulls or c != old_cows: return False
    return True

引数 code が生成したコード、qs は今までの質問結果を格納したリストです。質問結果はタプル (code, bulls, cows) にまとめてリスト qs に格納します。for ループで qs から質問結果を順番に取り出し、その要素を変数 old_bulls, old_cows, old_code にセットします。

次に、code と old_colde から bulls と cows を check_code() で求め、変数 b, c にセットします。b と old_bulls が異なる、または c と old_cows が異なる場合、code は矛盾しているので False を返します。すべての質問結果に対して矛盾が無ければ True を返します。

マスターマインドを解くプログラムは次のようになります。 

リスト : マスターマインドの解法

def master(collect):
    qs = []
    for code in permutations(range(10), 4):
        if not check_query(code, qs): continue
        b, c = check_code(collect, code)
        qs.append((code, b, c))
        if b == 4:
            return qs

def solver(collect):
    print_answer(master(collect))

関数 master() の引数 collect には正解のコードを渡します。変数 qs のリストに質問結果を格納します。順列の生成は Python の標準ライブラリ itertools の関数 permutations() を使います。

for ループで順列を一つずつ取り出して変数 code にセットし、check_query() で質問結果と矛盾がないかチェックします。矛盾が無ければ check_code() で bulls と cows を求め、qs に質問結果を追加します。最後に bulls が 4 ならば return で qs を返します。関数 solver() は master() 呼び出して、その結果を関数 print_answer() で表示します。

●何回で当たるか

これでプログラムは完成です。それでは実行例を示しましょう。 

>>> solver((9,8,7,6))
1: (0, 1, 2, 3) : bulls = 0, cows = 0
2: (4, 5, 6, 7) : bulls = 0, cows = 2
3: (5, 4, 8, 9) : bulls = 0, cows = 2
4: (6, 7, 9, 8) : bulls = 0, cows = 4
5: (8, 9, 7, 6) : bulls = 2, cows = 2
6: (9, 8, 7, 6) : bulls = 4, cows = 0
Good Job!!
>>> solver((1,3,5,7))
1: (0, 1, 2, 3) : bulls = 0, cows = 2
2: (1, 0, 4, 5) : bulls = 1, cows = 1
3: (1, 2, 5, 6) : bulls = 2, cows = 0
4: (1, 2, 7, 4) : bulls = 1, cows = 1
5: (1, 3, 5, 7) : bulls = 4, cows = 0
Good Job!!
>>> solver((8,6,4,2))
1: (0, 1, 2, 3) : bulls = 0, cows = 1
2: (1, 4, 5, 6) : bulls = 0, cows = 2
3: (2, 5, 4, 7) : bulls = 1, cows = 1
4: (2, 6, 8, 4) : bulls = 1, cows = 3
5: (8, 6, 4, 2) : bulls = 4, cows = 0
Good Job!!

肝心の質問回数ですが、5, 6 回で当たる場合が多いようです。そこで、5040 個のコードをすべて試してみました。 

リスト : すべてのコードを試す

def solver_all():
    ys = [master(xs) for xs in permutations(range(10), 4)]
    ls = [len(xs) for xs in ys]
    m = max(ls)
    total = sum(ls)
    print(f'平均質問回数 = {total / 5040}')
    print(f'最大質問回数 = {m}')
    for xs in [ys[i][-1][0] for i, x in enumerate(ls) if x == m]:
        print(xs)

プログラムは簡単なので説明は割愛させていただきます。実行結果は次のようになりました。 

>>>> s = time.time(); solver_all(); time.time() - s
平均質問回数 = 5.56031746031746
最大質問回数 = 9
(5, 2, 9, 3)
(9, 2, 0, 4)
(9, 2, 1, 4)
(9, 2, 4, 1)
(9, 4, 3, 1)
11.700564861297607

実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz

平均質問回数は 5.56 回になりました。これは 参考文献 1 の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは (5, 2, 9, 3), (9, 2, 0, 4), (9, 2, 1, 4), (9, 2, 4, 1), (9, 4, 3, 1) の 5 通りでした。 

>>> solver((5,2,9,3))
1: (0, 1, 2, 3) : bulls = 1, cows = 1
2: (0, 2, 4, 5) : bulls = 1, cows = 1
3: (0, 3, 5, 6) : bulls = 0, cows = 2
4: (1, 5, 4, 3) : bulls = 1, cows = 1
5: (1, 6, 2, 5) : bulls = 0, cows = 2
6: (4, 2, 6, 3) : bulls = 2, cows = 0
7: (5, 2, 7, 3) : bulls = 3, cows = 0
8: (5, 2, 8, 3) : bulls = 3, cows = 0
9: (5, 2, 9, 3) : bulls = 4, cows = 0
Good Job!!
>>> solver((9,4,3,1))
1: (0, 1, 2, 3) : bulls = 0, cows = 2
2: (1, 0, 4, 5) : bulls = 0, cows = 2
3: (2, 3, 5, 4) : bulls = 0, cows = 2
4: (3, 4, 0, 6) : bulls = 1, cows = 1
5: (3, 5, 6, 1) : bulls = 1, cows = 1
6: (6, 5, 0, 2) : bulls = 0, cows = 0
7: (7, 4, 3, 1) : bulls = 3, cows = 0
8: (8, 4, 3, 1) : bulls = 3, cows = 0
9: (9, 4, 3, 1) : bulls = 4, cows = 0
Good Job!!

なお、参考文献 1 には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。

●5 つの数字を当てる

次は数字の個数を 5 個に増やして、平均質問回数とその最大値がどうなるか、Python3 (PyPy3) でプログラムを作って確かめてみました。説明は割愛しますので、詳細は プログラムリスト をお読みください。

実行結果を示します。 

>>>> s = time.time(); solver5_all(); time.time() - s
平均質問回数 = 5.994675925925926
最大質問回数 = 9
(1, 8, 3, 9, 0)(3, 9, 8, 0, 1)(5, 2, 9, 1, 7)(5, 3, 6, 2, 7)
(5, 8, 3, 7, 0)(6, 0, 1, 3, 9)(6, 5, 4, 0, 2)(6, 5, 4, 1, 2)
(7, 0, 5, 4, 1)(7, 2, 3, 4, 5)(7, 3, 1, 4, 9)(7, 3, 8, 0, 6)
(7, 3, 8, 2, 5)(7, 4, 0, 3, 5)(7, 4, 2, 6, 1)(7, 4, 9, 2, 6)
(7, 5, 4, 0, 1)(7, 5, 4, 0, 2)(7, 5, 9, 0, 3)(7, 6, 8, 0, 3)
(7, 8, 0, 2, 5)(7, 8, 9, 6, 1)(7, 9, 1, 6, 3)(7, 9, 8, 1, 3)
(8, 0, 7, 6, 5)(8, 0, 7, 9, 4)(8, 2, 1, 7, 9)(8, 2, 7, 6, 0)
(8, 3, 6, 4, 2)(8, 4, 6, 0, 1)(8, 6, 0, 1, 2)(8, 6, 4, 3, 0)
(8, 6, 5, 4, 3)(8, 7, 0, 2, 5)(8, 7, 0, 6, 1)(8, 7, 0, 6, 3)
(8, 7, 1, 0, 9)(8, 7, 5, 4, 0)(8, 7, 6, 0, 2)(8, 7, 6, 1, 2)
(8, 7, 6, 2, 3)(8, 7, 9, 0, 2)(8, 7, 9, 1, 2)(8, 9, 1, 7, 2)
(9, 0, 6, 4, 1)(9, 0, 7, 5, 6)(9, 0, 8, 6, 5)(9, 1, 0, 3, 8)
(9, 1, 0, 4, 7)(9, 2, 6, 0, 4)(9, 3, 7, 6, 5)(9, 3, 8, 4, 0)
(9, 4, 1, 8, 0)(9, 4, 3, 7, 6)(9, 4, 5, 0, 3)(9, 4, 6, 3, 0)
(9, 5, 3, 8, 7)(9, 5, 4, 0, 2)(9, 5, 6, 8, 7)(9, 5, 7, 0, 3)
(9, 5, 7, 6, 8)(9, 5, 8, 4, 0)(9, 5, 8, 4, 1)(9, 6, 4, 0, 1)
(9, 7, 0, 2, 5)(9, 7, 0, 5, 3)(9, 7, 1, 6, 3)(9, 7, 1, 8, 3)
(9, 7, 4, 2, 5)(9, 7, 5, 1, 2)(9, 7, 6, 1, 2)(9, 7, 8, 1, 3)
(9, 7, 8, 4, 1)(9, 8, 0, 1, 7)(9, 8, 0, 5, 7)(9, 8, 0, 6, 3)
(9, 8, 0, 6, 7)(9, 8, 1, 0, 7)(9, 8, 1, 4, 5)(9, 8, 1, 5, 3)
(9, 8, 2, 4, 0)(9, 8, 3, 7, 1)(9, 8, 4, 0, 7)(9, 8, 6, 2, 0)
(9, 8, 6, 2, 1)(9, 8, 7, 2, 5)
466.74050402641296

>>>> solver5((1,8,3,9,0))
1: (0, 1, 2, 3, 4) : bulls = 0, cows = 3
2: (1, 0, 3, 5, 6) : bulls = 2, cows = 1
3: (1, 0, 4, 6, 7) : bulls = 1, cows = 1
4: (1, 2, 0, 5, 8) : bulls = 1, cows = 2
5: (1, 3, 8, 2, 6) : bulls = 1, cows = 2
6: (1, 4, 3, 8, 5) : bulls = 2, cows = 1
7: (1, 5, 3, 7, 2) : bulls = 2, cows = 0
8: (1, 8, 3, 0, 9) : bulls = 3, cows = 2
9: (1, 8, 3, 9, 0) : bulls = 5, cows = 0
Good Job!!
>>>> solver5((9,8,6,2,0))
1: (0, 1, 2, 3, 4) : bulls = 0, cows = 2
2: (1, 0, 5, 6, 7) : bulls = 0, cows = 2
3: (2, 3, 6, 5, 8) : bulls = 1, cows = 2
4: (2, 4, 7, 8, 5) : bulls = 0, cows = 2
5: (3, 2, 6, 7, 9) : bulls = 1, cows = 2
6: (3, 9, 4, 5, 6) : bulls = 0, cows = 2
7: (6, 2, 0, 9, 8) : bulls = 0, cows = 5
8: (9, 8, 6, 0, 2) : bulls = 3, cows = 2
9: (9, 8, 6, 2, 0) : bulls = 5, cows = 0
Good Job!!

平均質問回数が 5.99 回、質問回数の最大値は 9 で、そのときのコードは 86 通りになりました。もっと難しくなるかと思っていたので、予想外の結果にちょっと驚きました。実行時間は PyPy3 でも約 8 分かかります。やっぱり Python では時間がかかりますね。興味のある方は他のプログラミング言語で試してみてください。

●参考文献

  1. 田中哲郎, 「数当てゲーム (MOO, マスターマインド)」, 松原仁、竹内郁雄 編 『bit 別冊 ゲームプログラミング』 pp150 - 157, 共立出版, 1997

●プログラムリスト

#
# master.py : マスターマインド
#
#             Copyright (C) 2022 Makoto Hiroi
#
from itertools import permutations
import time

# bulls を数える
def count_bulls(xs, ys):
    zs = [x == y for x, y in zip(xs, ys)]
    return zs.count(True)

# 同じ数字を数える
def count_same_number(xs, ys):
    zs = [x in ys for x in xs]
    return zs.count(True)

# bulls と cows を求める
def check_code(xs, ys):
    bulls = count_bulls(xs, ys)
    cows = count_same_number(xs, ys) - bulls
    return bulls, cows

# 今までの質問と矛盾していないか
def check_query(code, qs):
    for old_code, old_bulls, old_cows in qs:
        b, c = check_code(code, old_code)
        if b != old_bulls or c != old_cows: return False
    return True

#
def print_answer(qs):
    i = 1
    for code, bulls, cows in qs:
        print(f'{i}: {code} : bulls = {bulls}, cows = {cows}')
        i += 1
    print('Good Job!!')

# マスターマインド
def master(collect):
    qs = []
    for code in permutations(range(10), 4):
        if not check_query(code, qs): continue
        b, c = check_code(collect, code)
        qs.append((code, b, c))
        if b == 4:
            return qs

def solver(collect):
    print_answer(master(collect))

def solver_all():
    ys = [master(xs) for xs in permutations(range(10), 4)]
    ls = [len(xs) for xs in ys]
    m = max(ls)
    total = sum(ls)
    print(f'平均質問回数 = {total / 5040}')
    print(f'最大質問回数 = {m}')
    for xs in [ys[i][-1][0] for i, x in enumerate(ls) if x == m]:
        print(xs)

# 5 つの数字を当てる
def master5(collect):
    qs = []
    for code in permutations(range(10), 5):
        if not check_query(code, qs): continue
        b, c = check_code(collect, code)
        qs.append((code, b, c))
        if b == 5:
            return qs

def solver5(collect):
    print_answer(master5(collect))

def solver5_all():
    ys = [master5(xs) for xs in permutations(range(10), 5)]
    ls = [len(xs) for xs in ys]
    m = max(ls)
    total = sum(ls)
    print(f'平均質問回数 = {total / 30240}')
    print(f'最大質問回数 = {m}')
    for xs in [ys[i][-1][0] for i, x in enumerate(ls) if x == m]:
        print(xs)
Copyright (C) 2022 Makoto Hiroi
All rights reserved.
[ Home | Puzzle ]