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

©2022 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 ponad 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.

Zmienne 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:
wykonuj kroki K03...K19
łamacz ma maksymalnie 6 podejść
K03:     Czytaj s łamacz odczytujemy kod łamacza
K04:     Dopóki | s łamacz | < 4,
    wykonuj:
        s łamacz  ←  s łamacz  + w 2
kod łamacza musi być co najmniej
; 4-ro znakowy, w 2 – wartownik
K05:     s k  ← s koder kopiujemy kod kodera
K06:     s klucz  ← '' zerujemy kod klucza
K07:     Dla i  = 1, 2, ..., 4:
    wykonuj kroki K08...K11
szukamy znaków zgodnych co do typu i pozycji
K08:         Jeśli s k [ i  ] ≠ s lamacz [ i  ], to
        następny obieg pętli K07
znaki niezgodne pomijamy
K09:         s klucz   ← s klucz  + "x" w kluczu umieszczamy znak x
K10:         s k [ i  ]  ← w 1 znaki zastępujemy wartownikami,
K11:         s łamacz [ i  ]  ← w 2 aby nie były później zaliczane
K12:     Dla i  = 1, 2, ..., 4:
    wykonuj kroki K13...K18
szukamy znaków zgodnych co do pozycji
K13:         Jeśli s k [ i  ] + w 1,
        to następny obieg pętli K12
znaki usunięte pomijamy
K14:         Dla j  = 1, 2, ..., 4:
        wykonuj kroki K15...K18
znak kodera porównujemy z kolejnymi znakami łamacza
K15:             Jeśli s k [ i  ] ≠ s łamacz [ j  ],
            to następny obieg pętli K14
pomijamy znaki różne
K16:             s klucz  s klucz  + "o" w kluczu umieszczamy znak o
K17:             s łamacz [ j  ] ← w 2 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",
    to idź do kroku K21
kończymy pętlę K02, 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 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 <time.h>

using namespace std;

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

// generujemy kod kodera

  srand ( ( unsigned )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 += 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
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
©2022 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.