Algorytmy i Struktury Danych - MasterMind komputer kontra człowiek

obrazek

Gra MasterMind (Mistrz Intelektu/Umysłu) jest grą o prostych regułach, lecz wymagającą logicznego myślenia. Została wynaleziona przez Izraelczyka Mordecai Meirowica na początku lat 70-tych ubiegłego stulecia. Wynalazca początkowo chciał zainteresować swoją grą duże firmy produkujące gry, jednakże wszędzie został zignorowany. W końcu udało mu się zawrzeć kontrakt z małą angielską firmą Invicta Plastics, która produkowała pomoce dydaktyczne. Grę nieco przebudowano i nadano jej nazwę MasterMind . Wkrótce sprzedano ponad 50 milionów egzemplarzy w więcej niż 80 krajach, co sprawiło, iż stała się ona kasowym przebojem rynku gier logicznych w latach 70-tych.

Zasady gry są następujące:

Do gry potrzebna jest plansza oraz kolorowe, plastikowe grzybki z wyprofilowanymi główkami, które wtykamy nóżkami w otwory na planszy. Grzybki są w dwóch rodzajach: kodowe o sześciu różnych kolorach oraz kluczowe, mniejsze o dwóch kolorach – czarnym i białym. W grze uczestniczy zawsze dwóch graczy – koder (ang. coder) oraz łamacz kodu (ang. code breaker). Koder przy pomocy grzybków kodowych tworzy tajny kod zbudowany z 4 kolorów. Kod ten zostaje ukryty przed drugim graczem specjalną przykrywką na końcu planszy. Łamacz kodu w co najwyżej 6 podejściach stara się odgadnąć kod kodera. W tym celu z kolorowych grzybków układa swoje propozycje 4 kolorowych kodów. Dla każdej propozycji koder odpowiada kombinacją co najwyżej 4 grzybków kluczowych. Grzybek czarny oznacza, iż w kodzie łamacza jeden kolor (nie wiadomo który) jest na tym samym miejscu, co w kodzie kodera. Grzybek biały oznacza, iż kolor łamacza występuje w kodzie kodera, lecz na innym miejscu. Brak grzybków kluczowych oznacza, iż żaden z kolorów kodu łamacza nie występuje w kodzie kodera.

Na pierwszy rzut oka gra MasterMind nie wygląda na problem tekstowy. Skoro tak, to sprowadźmy ją do problemu tekstowego. W tym celu grzybki kodowe przedstawmy jako litery ze zbioru {A, B, C, D, E, F}. Koder będzie tworzył z tych liter 4-ro literowy kod tajny, który ma odgadnąć drugi gracz – łamacz kodu. Grzybki kluczowe przedstawmy jako znaki:

x – literka kodu łamacza odpowiada dokładnie literce kodu kodera co do rodzaju i co do położenia w kodzie.
o – literka kodu łamacza zgadza się z literką kodu kodera tylko co do rodzaju.

Przykład:

		Kod	Klucz
	Kod kodera	BFAC
1.	Kod łamacza	ABCD	ooo
2.	Kod łamacza	BADE	xo
3.	Kod łamacza	BACF	xooo
4.	Kod łamacza	BFCA	xxoo
5.	Kod łamacza	BFAC	xxxx

Zadanie naszego algorytmu będzie polegało zatem na wygenerowaniu 4-literowego kodu kodera, odczycie kodu łamacza, ocenieniu go i wyświetleniu kodu klucza. Odczyt kodu łamacza przerywany jest po 6 próbach lub po otrzymaniu kodu klucza równego xxxx – wszystkie litery kodu łamacza zgadzają się z literami kodu kodera co do położenia i rodzaju. W obu przypadkach wyświetlony będzie kod kodera.

Tworzenie kodu klucza jest dwuetapowe:

Najpierw tworzymy kopię roboczą kodu kodera, ponieważ algorytm niszczy zawartość tego kodu.

W pierwszym etapie wyznaczamy znaki zgodne co do pozycji i rodzaju. W tym celu wystarczy porównać ze sobą kolejne znaki kodu kodera i łamacza. Jeśli są zgodne, do kodu klucza wstawiamy znak x. Jednakże musimy pamiętać o zastąpieniu w kodzie kodera i łamacza zgodnego znaku różnymi symbolami, które nie występują w alfabecie. Chodzi o to, aby w drugim etapie dany znak nie został ponownie zaliczony.

W drugim etapie wyznaczamy znaki zgodne co do rodzaju. W tym celu każdy znak kodu kodera porównujemy z każdym znakiem kodu łamacza aż do napotkania zgodności. Jeśli mamy zgodność, to do kodu klucza wstawiamy znak o. Ponieważ znaki zgodne co do rodzaju i pozycji zostały usunięte z kodu łamacza w pierwszym etapie, zgodność może oznaczać tylko równe znaki, lecz na różnych pozycjach. Znaki zgodne również usuwamy z kodu łamacza, aby nie zostały ponownie zaliczone.

Algorytm gry MasterMind – komputer kontra człowiek

Wejście:

4 znakowe kody łamacza w łańcuchu s_łamacz.

Wyjście:

4 znakowe kody klucza dla kodów łamacza. Na końcu kod kodera.

Elementy pomocnicze:

s_koder : kod kodera.
s_k : kopia kodu kodera.
s_klucz : kod klucza.
i, j : indeksy; i, j ∈ N.
runda : numer rundy; runda ∈ N.

Lista kroków:

K01: Generuj s_koder ; generujemy 4-znakowy kod kodera
K02: Dla runda = 1, 2, …, 6: ; łamacz ma maksymalnie 6 prób
     wykonuj kroki K03…K19

K03:   Czytaj s_łamacz ; odczytujemy kod łamacza
K04:   Dopóki |s_łamacz| < 4, ; kod łamacza musi być co najmniej
       wykonuj: s_łamacz ← s_łamacz+w₂ ; 4-ro znakowy, w₂ – wartownik
K05:   s_k ← s_koder ; kopiujemy kod kodera
K06:   s_klucz ← "" ; zerujemy kod klucza
K07:   Dla i = 1, 2, 3, 4: ; szukamy znaków zgodnych co do typu i pozycji
       wykonuj kroki K08…K11
K08:     Jeśli s_k[i] ≠ s_łamacz[i], ; znaki niezgodne pomijamy
         to następny obieg pętli K07
K09:     s_klucz ← s_klucz+"x" ; w kluczu umieszczamy znak x
K10:     s_k[i] ← w₁ ; znaki zastępujemy wartownikami
K11:     s_łamacz[i] ← w₂ ; aby nie były później zaliczane
K12:   Dla i = 1, 2, …, 4: ; szukamy znaków zgodnych co do pozycji
       wykonuj kroki K13…K18
K13:     Jeśli s_k[i] = w₁, ; znaki usunięte pomijamy
         to następny obieg pętli K12
K14:     Dla j = 1, 2, …, 4: ; znak kodera porównujemy
         wykonuj kroki K15…K18 ; z kolejnymi znakami łamacza
K15:     Jeśli s_k[i] ≠ s_łamacz[j], ; pomijamy znaki różne
         to następny obieg pętli K14
K16:     s_klucz← s_klucz+"o" ; w kluczu umieszczamy znak o
K17:     s_łamacz[j] ← w₂ ; znak łamacza zastępujemy wartownikiem
K18:     Następny obieg pętli K12 ; przechodzimy do następnego
         ; znaku kodera
K19:   Pisz s_klucz ; wyprowadzamy kod klucza
K20: Jeśli s_klucz = "xxxx", ; kończymy pętlę K02, 
     to idź do kroku K21 ; jeśli kod kodera odgadnięty
K21: Pisz s_koder ; wyprowadzamy kod kodera
K22: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program gry MasterMind generuje 4 znakowy kod kodera zbudowany ze znaków A, B, C, D, E lub F. Zadaniem gracza jest odgadnięcie tego kodu w co najwyżej 6 podejściach. W tym celu gracz – łamacz kodu – wprowadza swoje kody. W odpowiedzi komputer wyświetla dla nich kody klucza zbudowane ze znaków x i o.

Pascal

// MasterMind-komputer <-> człowiek
// Data: 13.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  skoder, slamacz, sklucz, sk : string;
  i, j, runda : integer;

begin

  // generujemy kod kodera
  randomize;
  skoder := '';
  for i := 1 to 4 do
    skoder := skoder+chr(65+random(6));

  // rozpoczynamy rozgrywkę
  for runda := 1 to 6 do
  begin

  // odczytujemy kod łamacza
    write ('Runda ', runda, ' : ');
    readln(slamacz);

  // normalizujemy kod łamacza
    while length(slamacz) < 4 do
      slamacz := slamacz+'$';

  // generujemy kod klucza
    sk := skoder; // kopia robocza kodu kodera
    sklucz := '';
    for i := 1 to 4 do
      if sk[i] = slamacz[i] then
      begin
        sklucz := sklucz+'x';
        sk[i] := '#';      // wartownik w1
        slamacz[i] := '$'; // wartownik w2
      end;
    for i := 1 to 4 do
      if sk[i] <> '#' then
        for j := 1 to 4 do
          if sk[i] = slamacz[j] then
          begin
            sklucz := sklucz+'o';
            slamacz[j] := '$'; // wartownik w2
            break;
          end;

  // wyświetlamy kod klucza
    writeln('               : ', sklucz);

  // jeśli odgadnięto kod kodera, kończymy
    if sklucz = 'xxxx' then break;
  end;
  writeln('KOD     : ', skoder);
  writeln;
end.

C++

// MasterMind-komputer <-> człowiek
// Data: 13.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
  string skoder, slamacz, sklucz, sk;
  int i, j, runda;

  // generujemy kod kodera
  srand(time(NULL));
  skoder = "";
  for(i = 0; i < 4; i++)
    skoder += char(65+rand()%6);

  // rozpoczynamy rozgrywkę
  for(runda = 1; runda <= 6; runda++)
  {

    // odczytujemy kod łamacza
    cout << "Runda " << runda << ": ";
    cin >> slamacz;

    // normalizujemy kod łamacza
    while(slamacz.length() < 4)
      slamacz += '$';

    // generujemy kod klucza
    sk = skoder; // kopia robocza kodu kodera
    sklucz = "";
    for(i = 0; i < 4; i++)
      if(sk[i] == slamacz[i])
      {
        sklucz += 'x';
        sk[i] = '#';      // wartownik w1
        slamacz[i] = '$'; // wartownik w2
      }
    for(i = 0; i < 4; i++)
      if(sk[i] != '#')
        for(j = 0; j < 4; j++)
          if(sk[i] == slamacz[j])
          {
            sklucz += 'o';
            slamacz[j] = '$'; // wartownik w2
            break;
          }

    // wyświetlamy kod klucza
    cout << "               : "
         << sklucz << endl;

  // jeśli odgadnięto kod kodera, kończymy
    if(sklucz == "xxxx") break;
  }
  cout << "KOD     : "
       << skoder
       << endl << endl;
  return 0;
}

Basic

' MasterMind-komputer <-> człowiek
' Data: 13.08.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------------

Dim As String skoder, slamacz, sklucz, sk
Dim As Integer i, j, runda

' generujemy kod kodera
Randomize
skoder = ""
For i = 1 To 4
  skoder += Chr(65+Cint(Rnd*5))
Next

' rozpoczynamy rozgrywkę
For runda = 1 To 6

  ' odczytujemy kod łamacza
  Print "Runda";runda;": ";
  Line Input slamacz

  ' normalizujemy kod łamacza
  While Len(slamacz) < 4
    slamacz += "$"
  Wend

  ' generujemy kod klucza
  sk = skoder ' kopia robocza kodu kodera
  sklucz = ""
  For i = 1 To 4
    If Mid(sk, i, 1) = Mid(slamacz, i, 1) Then
      sklucz += "x"
      Mid(sk, i, 1)      = "#" ' wartownik w1
      Mid(slamacz, i, 1) = "$" ' wartownik w2
    End If
  Next
  For i = 1 To 4
    If Mid(sk, i, 1) <> "#" Then
      For j = 1 To 4
        If Mid(sk, i, 1) = Mid(slamacz, j, 1) Then
          sklucz += "o"
          Mid(slamacz, j, 1) = "$" ' wartownik w2
          Exit For
        End If
      Next 
    End If
  Next

  ' wyświetlamy kod klucza
  Print "               : ";sklucz

  ' jeśli odgadnięto kod kodera, kończymy
  If sklucz = "xxxx" Then Exit For
Next
Print "KOD     : ";skoder
Print

End

Python (dodatek)

# MasterMind-komputer <-> człowiek
# Data: 23.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------

import random

# generujemy kod kodera
skoder = ""
for i in range(4):
    skoder += chr(random.randrange(65, 70))
# rozpoczynamy rozgrywkę
for runda in range(1, 7):
    # odczytujemy kod łamacza
    print("Runda", runda, ": ", end="")
    slamacz = input()
    # normalizujemy kod łamacza
    while len(slamacz) < 4:
        slamacz += "$"
    # generujemy kod klucza
    sk = skoder[:] # kopia robocza kodu kodera
    sklucz = ""
    for i in range(4):
        if sk[i] == slamacz[i]:
            sklucz += "x"
            sk = sk[:i]+"#"+sk[i+1:]
            slamacz = slamacz[:i]+"$"+slamacz[i+1:]
    for i in range(4):
        if sk[i] != "#":
            for j in range(4):
                if sk[i] == slamacz[j]:
                    sklucz += 'o'
                    slamacz = slamacz[:j]+"$"+slamacz[j+1:]
                    break
    # wyświetlamy kod klucza
    print("               :", sklucz)
    # jeśli odgadnięto kod kodera, kończymy
    if sklucz == "xxxx":
        break
print("KOD     :", skoder)
print()

Wynik:

Runda 1 : ABCD
               : oo
Runda 2 : BCAF
               : xxx
Runda 3 : DCAF
               : xxx
Runda 4 : FCAF
               : xxx
Runda 5 : ECAF
               : xxxx
KOD     : ECAF

JavaScript

<html>
  <head>
    <title>
      MasterMind
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <span
          style="color:
                 White;
                 background-color:
                 #800000">
          <b>&nbsp;MasterMind</b>
          </span><br/>
          &nbsp;
          (C)2026 mgr Jerzy Wałaszek
          &nbsp;<hr>
          <input
          type="button"
          value="Nowa gra"
          name="B1"
          onclick="mmstart();">
          <hr>
          <b>
          człowiek kontra komputer:
          </b>
          <div align="center">
            <table
            border="0"
            cellpadding="0"
            style="border-collapse:
                   collapse"
            bgcolor="#F0F0F0">
              <tr>
                <td valign="top"
                nowrap
                bgcolor="#000000">
                  <pre
                  id="out"
                  style="color:
                         White">.</pre>
                </td>
              </tr>
              <tr>
                <td
                valign="top">
                  <input
                  type="text"
                  name="inp_lamacz"
                  size="6"
                  style="font-family:
                         Courier New">
                  <input
                  type="button"
                  value="Gotowe"
                  onclick="mmplay();"
                  name="B2">
                </td>
              </tr>
            </table>
          </div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// MasterMind człowiek komputer
// Data: 13.08.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

let gra = false;
let runda;
let skoder;

function mmstart()
{
  var i;
 
  skoder = "";
  for(i = 0; i < 4; i++)
  skoder += String.fromCharCode(
            65 + Math.floor(
            Math.random() * 6));
  gra = true;
  runda = 1;
  document.getElementById("out")
  .innerHTML = "Runda 1 : ";
  document.frm
  .inp_lamacz.value = "";
}

function mmplay()
{
  var sk,slamacz,i,j,t;
 
  if(gra)
  {

    // odczytujemy
    // kod łamacza
    slamacz = document.frm
              .inp_lamacz.value;

    // normalizujemy
    // kod łamacza
    slamacz += "    ";
    slamacz = slamacz.substr(0, 4);
    slamacz = slamacz.toUpperCase();

    t = document.getElementById("out")
        .innerHTML;
    t += slamacz+" : ";

    // generujemy kod klucza
    sk = skoder;
    sklucz = "";
    for(i = 0; i < 4; i++)
      if(sk.charAt(i) ==
         slamacz.charAt(i))
      {
        sklucz += 'x';
        sk = sk.substr(0, i) +
             '#' + sk.substr(i + 1);
        slamacz = slamacz.substr(0, i) +
                  '.' + slamacz
                  .substr(i + 1);
      }
    for(i = 0; i < 4; i++)
      if(sk.charAt(i) != '#')
        for(j = 0; j < 4; j++)
          if(sk.charAt(i) ==
             slamacz.charAt(j))
          {
            sklucz += 'o';
            slamacz = slamacz
                      .substr(0, j) +
                      '.' + slamacz.
                      substr(j + 1);
            break;
          }

    // wyświetlamy kod klucza
    t += sklucz +" <br/>";

    // jeśli odgadnięto kod
    // kodera, kończymy
    if((sklucz == "xxxx") ||
       (runda == 6))
    {
      t += "KOD     : " + skoder;
      gra = false;
    }
    else
    {
      runda++;
      t += "Runda " + runda +
           " : ";
    }
    document.getElementById("out")
    .innerHTML = t;
  }
}

</script>

  </body>
</html>

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

MasterMind - komputer kontra człowiek