マスターマインド（ボードゲーム）

首謀者

マスターマインド完了ゲーム
デザイナー	モーデカイ・メイロウィッツ
活動年数	1970年から現在
ジャンル	ボードゲーム 紙と鉛筆のゲーム[ルート]
プレイヤー	2
セットアップ時間	5分未満
プレイ時間	10～30分
チャンス	無視できる
年齢範囲	8歳以上

マスターマインド（ヘブライ語： בול פגיעה、ローマ字：bul pgi'a）は、イスラエルで発明された2人用の暗号解読ゲームです。 ^{[1] [2]}これは、おそらく1世紀前に遡る 「  Bulls and Cows」と呼ばれる以前の鉛筆と紙を使ったゲームに似ています。

マスターマインドは、イスラエルの郵便局長で電気通信の専門家であったモーデカイ・メイロウィッツによって1970年に発明されました。大手玩具会社にアイデアを提案し、ニュルンベルク国際玩具見本市で展示した後、英国レスター近郊に拠点を置くプラスチック会社、インビクタ・プラスチックスに採用されました。インビクタはゲームのすべての権利を購入し、創設者のエドワード・ジョーンズ・フェンリーはゲームをさらに改良しました。1971年から1972年にかけて発売されました。^{[1] [2] [3]}

このゲームは、 Bulls and Cowsと呼ばれる紙と鉛筆を使ったゲームに基づいています。1960年代にケンブリッジ大学のTitanコンピュータシステムでコンピュータ版が動作し、「MOO」と呼ばれていました。このバージョンはFrank Kingによって書かれました。他のバージョンは、TSS/8タイムシェアリングシステム用にJS Feltonによって、Unix用にKen Thompsonによって書かれました。^[4]また、MITのMulticsシステム用にJerrold Grochowによって書かれました。^[5]

1971年以来、マスターマインドに関する権利はインヴィクタ・プラスチックス社が保有している。(インヴィクタ社はこのゲームを常にマスターマインドと呼んでいた。) 当初は自社で製造していたが、その後、米国とイスラエルでそれぞれ製造権を持つプレスマン・トイズ社とオルダ・インダストリーズ社を除き、世界中でハズブロ社に製造ライセンスを与えている。 ^[6]チーフテン・プロダクツ社は1972年にカナダでの製造権を取得したが、1996年に倒産した。

1973年から、ゲームの箱にはスーツを着た男性が前景に座り、その後ろに若い女性が立っている写真が掲載されるようになった。2人のアマチュアモデル（ビル・ウッドワードとセシリア・フォン）は2003年6月に再会し、別の宣伝写真にポーズをとった。^[7]

ゲームは以下を使用してプレイされます:

• 解読ボード。一方の端には 4 つの大きな穴の列を覆うシールドがあり、さらに 12 列 (または 10 列、8 列、または 6 列) には 4 つの小さな穴の列の隣に 4 つの大きな穴があります。
• 6つの異なる色（またはそれ以上、以下のバリエーションを参照）の丸い頭のコードペグをボード上の大きな穴に挿入します。
• キーペグは、赤（または黒）色と白の2種類があり、平らな頭でコードペグよりも小さく、ボード上の小さな穴に挿入されます。

2 人のプレーヤーは、何回ゲームをプレイするかを事前に決めます。その回数は偶数でなければなりません。一方のプレーヤーがコード作成者になり、もう一方のプレーヤーがコードブレーカーになります。^{[8] : 120}コード作成者は 4 つのコード ペグのパターンを選択します。プレーヤーは、重複や空白を許可するかどうかを事前に決定します。許可する場合、コード作成者は最大 4 つの同じ色のコード ペグまたは 4 つの空白を選択できます。コードに空白が許可されていない場合、コードブレーカーは推測に空白を使用できません。コード作成者は、シールドで覆われた 4 つの穴に選択したパターンを配置します。シールドはコード作成者には表示されますが、コードブレーカーには表示されません。^[9]

暗号解読者は、8～12ターンで、順番と色の両方でパターンを推測します。推測は、解読ボードにコードペグの列を置くことで行います。^{[8] : 120}配置したら、暗号作成者は、推測した列の小さな穴に0～4個のキーペグを置くことでフィードバックを提供します。推測されたコードペグのうち、色と位置が正しいものには、色付きのキーペグが置かれます。白いキーペグは、解答に含まれるコードペグですが、位置が間違っていることを示します。^[10]

推測した色に重複する色がある場合、それらが隠されたコード内の重複する色と同じ数に対応していない限り、それらすべてにキーペグを与えることはできません。たとえば、隠されたコードが赤-赤-青-青で、暗号解読者が赤-赤-赤-青と推測した場合、暗号作成者は最初の2つの赤と青に対して3つの色のキーペグを与えますが、3番目の赤には何も与えません。コードに2つ目の青も含まれているという事実は示されません。^[11]

フィードバックが提供されると、別の推測が行われます。推測とフィードバックは、コードブレーカーが正しく推測するか、デコードボードのすべての行がいっぱいになるまで交互に続けられます。

伝統的に、プレイヤーはコードメーカーとしてプレイしているときのみポイントを獲得できます。コードメーカーは、コードブレーカーが推測するたびに 1 ポイントを獲得します。コードブレーカーが指定された回数内に正確なパターンを推測できない場合は、コードメーカーが追加ポイントを獲得します。(代わりに、配置されたキー ペグの数に基づいてスコアを付けることもできます。) 合意された回数のゲームをプレイした後、最も多くのポイントを獲得したプレイヤーが勝者となります。

その他の規則が規定されることもある。^[12]

暗号解読者の最善の戦略を問う前に、「最善」の意味を定義する必要があります。最小の移動数は、最悪および平均のケースの条件下で、ゲーム理論におけるゼロサムゲームのミニマックス値の意味で分析できます。

^{4 つの穴と 6 つの色がある場合、6 4} = 1,296 通りのパターン があります(重複色は許可されますが、空白は許可されません)。

1977年、ドナルド・クヌースは、可能なパターンの数を徐々に減らしていくアルゴリズムを使用して、暗号解読者が5回以内でパターンを解くことができることを実証しました。^[13] コードペグの6つの色を表す1～6の数字を使用して説明すると、アルゴリズムは次のように機能します。

1. 1,296 個の可能なコード {1111、1112、... 6665、6666} の集合Sを作成します。
2. 最初の推測値 1122 から開始します。(Knuth は、1111、1112、1123、1234 などの「2 組」以外の最初の推測値を使用するこのアルゴリズムでは、すべてのコードで 5 回の試行で勝てないことを示す例を示しています。)
3. 推測して演奏すると、色付きのキーペグと白のキーペグの応答が得られます。
4. 応答が 4 つの色付きキー ペグである場合、ゲームは勝利となり、アルゴリズムは終了します。
5. それ以外の場合は、色付きのペグと白のペグの応答を返さないコードをSから削除します。
6. 次の推測は、応答スコアが最も低い推測を選択するミニマックス技法によって選択されます。この場合、推測に対する応答は、いくつかの色付きおよび白のキーペグであり、そのような応答のスコアは、応答が判明した後でもSでまだ可能なコードの数として定義されます。推測のスコアは、悲観的に、すべての応答スコアの最悪 (最大) として定義されます。最良 (最小) の推測スコアを持つ推測のセットから、次の推測として 1 つを選択し、可能な限りSからコードを選択します。(これらの制約内で、Knuth は、数値が最も小さい推測を選択するという慣例に従います。たとえば、2345 は 3456 より低くなります。Knuth はまた、場合によってはSからのコードが最高スコアの推測に含まれず、次のターンで推測が勝つことができないが、5 回で勝つことを保証するために必要となることを示す例を示しています。)
7. 手順3から繰り返します。

その後の数学者たちは、パターンを解くのに必要な平均ターン数を減らすさまざまなアルゴリズムを発見してきました。1993年に小山健治とトニー・W・ライは徹底的な深さ優先探索を行い、ランダムコードを解く最適な方法は平均5,625/1,296 = 4.3403ターンで解けることを示し、最悪のシナリオでは6ターンでした。^[14]

ゲーム理論におけるミニマックス値は5,600/1,290 = 4.3411である。コードメーカーのミニマックス戦略は、2色以上の1,290パターンの中から1つを均一に選択することである。 ^[15]

遺伝的アルゴリズムが組み込まれた新しいアルゴリズムでは、さまざまな世代を通じて大量の適格なコードが収集されます。これらの各コードの品質は、適格なセットの選択された要素との比較に基づいて決定されます。^{[16] [17]}このアルゴリズムは、実際に隠された組み合わせである確率に基づいて、各適格な組み合わせにスコアを割り当てるヒューリスティックに基づいています。この組み合わせは不明であるため、スコアは、適格なソリューションのセットの特性、または進化的アルゴリズムによって検出されたソリューションのサンプルに基づいています。

アルゴリズムは次のように機能します。P =ゲームで使用されるソリューションの長さ、X ₁ = 完全一致 (「赤いピン」)、Y ₁ = ほぼ一致 (「白いピン」) です。

1. i = 1と設定する
2. 固定初期推測G _{1をプレイ}
3. 応答X ₁とY _{1を取得します}
4. X _i ≠ Pの間繰り返します:
   1. i を増分
   2. E _i = ∅、h = 1と設定する
   3. 人口を初期化する
   4. h ≤ maxgenかつ| E _i | ≤ maxsizeである間繰り返します:
      1. 交差、突然変異、反転、順列を使用して新しい集団を生成する
      2. フィットネスを計算する
      3. 適格な組み合わせをE _iに追加する
      4. 増分h
   5. E _iに属するG _iを推測するゲーム
   6. 応答X _iとY _{iを取得する}

2004 年 11 月、ミヒール・デ・ボンドは、 1 列あたりn 個のペグと 2 色でプレイする場合、マスターマインドボードを解くことはNP 完全問題であることを証明し、 3 分の 1 の 3SAT問題をそのボードで表現する方法を示しました。彼はまた、一貫性のあるマスターマインド(すべての推測が、以前の推測のヒントと一致する秘密のコードの候補になるようにゲームをプレイする) でも同じことを示しまし た。^{[18] [より良いソースが必要]}

マスターマインド充足可能性問題は、「推測のセットと、推測ごとに得点された色付きキーペグと白キーペグの数が与えられた場合、それらの正確な得点を生成する秘密のパターンが少なくとも 1 つ存在するか?」と問う決定問題です (存在しない場合は、コード作成者が少なくとも 1 つの推測を誤って得点したに違いありません)。2005 年 12 月、Jeff Stuckman と Guo-Qiang Zhang は、arXiv の記事で、マスターマインド充足可能性問題が NP 完全であることを示しました。^{[19] [より良いソースが必要]}

色数と穴の数を変えることで、さまざまな難易度のマスターマインドゲームが生まれます。もう 1 つの一般的なバリエーションは、コード作成者とコードブレーカーの役割を担うプレイヤーの数を変えることです。以下は、Invicta、Parker Brothers、Pressman、Hasbro、およびその他のゲーム メーカー が制作したマスターマインドゲームの例です。

東ドイツのVEB Plasticart社が製造したSuper Codeと呼ばれるバージョンもありました。

上記のいずれの難易度も、「空」を追加の色として扱うことで上げたり、位置に関係なくコードの色を推測することだけを要求することで下げたりすることができます。Mini Mastermindでは、色付きコード ペグは色付きまたは白のキー ペグと同じサイズと形状であるため、キー ペグを追加の 2 色のコード ペグとして使用できるようにすることで難易度を上げることができます。

このゲームのコンピューター版やインターネット版も作られており、含まれる駒の数や種類が異なる場合があり、商標権侵害を避けるために異なる名前で呼ばれることも多い。マスターマインドは紙と鉛筆で遊ぶこともできる。4桁の数字を推測する数字版のマスターマインドもある。^[24] 2021年のウェブゲームWordleはマスターマインドと比較されている。^[25]

このゲームは、 Nintendo Switch用のコンピレーションパーティービデオゲームClubhouse Games: 51 Worldwide Classicsに「Hit & Blow」という名前で収録されました。^[26]

• ゲーム＃3 ^[27]
• ゲームとパズル^[28]
• 1980年ゲーム100ゲーム^[29]
• 1981 ゲーム 100ゲーム
• ゲームとパズル^[30]
• プレイボーイ勝者のボードゲームガイド^[31]
• 家族向けゲーム：ベスト100 ^[32]

• イスラエルの発明と発見
• Bulls and CowsとAB – 数字を使った類似ゲーム
• Jotto – 2人用のペンと紙を使った単語ゲーム
• Lingo – 類似のテレビ番組
• Wordle – 2021年の同様のウェブゲーム

• マスターマインド: 拡張現実のアプローチ、レガシー ゲームを新しいインタラクション パラダイムに移植
• Mastermindに関するMathworldの記事
• マスターマインドにおける最適解ルックアップテーブル