Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

MasterMind-komputer kontra człowiek

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy opracować algorytm gry  MasterMind  w wersji: komputer kontra człowiek.

Rozwiązanie

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:

skoder : kod kodera.
sk : kopia kodu kodera.
sklucz : kod klucza.
i,j : indeksy; i,j ∈ N.
runda : numer rundy; runda ∈ N.

Lista kroków:

K01: Generuj skoder ; 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łamaczsłamacz+w2 ; 4-ro znakowy, w2 – wartownik
K05:   sk ← skoder ; kopiujemy kod kodera
K06:   sklucz ← "" ; 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 sk[i] ≠ słamacz[i], ; znaki niezgodne pomijamy
         to następny obieg pętli K07
K09:     sklucz ← sklucz+"x" ; w kluczu umieszczamy znak x
K10:     sk[i] ← w1 ; znaki zastępujemy wartownikami
K11:     słamacz[i] ← w2 ; 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 sk[i] = w1, ; 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 sk[i] ≠ słamacz[j], ; pomijamy znaki różne
         to następny obieg pętli K14
K16:     sklucz sklucz+"o" ; w kluczu umieszczamy znak o
K17:     słamacz[j] ← w2 ; znak łamacza zastępujemy wartownikiem
K18:     Następny obieg pętli K12 ; przechodzimy do następnego
         ; znaku kodera
K19:   Pisz sklucz ; wyprowadzamy kod klucza
K20: Jeśli sklucz = "xxxx", ; kończymy pętlę K02,
     to idź do kroku K21 ; jeśli kod kodera odgadnięty
K21: Pisz skoder ; 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 xo.
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

 MasterMind
(C)2020 mgr Jerzy Wałaszek

.
 

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.