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 - człowiek kontra komputer

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy opracować algorytm gry MasterMind – człowiek kontra komputer.

Rozwiązanie

obrazek

Zasady gry MasterMind opisaliśmy w poprzednim rozdziale. Tym razem zadanie jest nieco trudniejsze – kod wymyśla człowiek. Komputer komunikuje się z człowiekiem za pomocą kodów kodera, które sam tworzy oraz kodów klucza wprowadzanych przez człowieka na podstawie kodów kodera. Zadaniem algorytmu jest odgadnięcie wymyślonego przez człowieka kodu w co najwyżej 6 ruchach. Dla uproszczenia zakładamy, iż człowiek nie będzie popełniał błędów – w rzeczywistości należałoby je uwzględnić.

Zastanówmy się nad tym z jak dużym zbiorem mamy do czynienia. Kod kodera składa się z 4 liter należących do alfabetu {A, B, C, D, E, F}, z których każda może pojawić się na dowolnej pozycji kodu. Wszystkich możliwych do utworzenia słów kodowych będzie:

6 × 6 × 6 × 6 = 1296

Jeśli nie znasz kombinatoryki, to wyjaśnienie tego wzoru jest następujące:

Na pierwszej pozycji może pojawić się jedna z 6 liter – A, B, C, D, E lub F. Daje to 6 różnych możliwości:

Axxx, Bxxx, Cxxx, Dxxx, Exxx, Fxxx, gdzie x – pozycja jeszcze nie zajęta

W każdej z tych 6 kombinacji drugą literę możemy wybrać również na 6 różnych sposobów. Na przykład dla Cxxx otrzymamy:

CAxx, CBxx, CCxx, CDxx, CExx, CFxx

Zatem ze względu na dwie pierwsze litery kodu otrzymujemy 6 × 6 = 36 kombinacji. W każdej z nich trzecią literę również możemy wybrać na 6 różnych sposobów. Na przykład dla BFxx otrzymamy:

BFAx, BFBx, BFCx, BFDx, BFEx, BFFx

Ze względu na 3 pierwsze litery kodu otrzymamy 6 × 6 × 6 = 216 kombinacji. W każdej z nich pozostała ostatnia pozycja, w której możemy znów umieścić znak na 6 różnych sposobów i ostatecznie otrzymujemy wzór wyjściowy.

Nie jest to zbiór specjalnie duży dla współczesnego komputera Pentium – możemy zastosować metodę naiwną, która polega na tym, iż tworzymy zbiór Z wszystkich możliwych słówek kodowych. Następnie w pętli wykonującej się maksymalnie 6 razy losujemy ze zbioru Z jedno słowo kodowe s łamacz,  usuwamy je ze zbioru Z i prezentujemy człowiekowi. W odpowiedzi człowiek zwraca nam kod klucza s klucz  zbudowany z liter x i o wg zasad gry MasterMind (ważne jest, aby litery x poprzedzały w kodzie litery o ). Jeśli otrzymamy kod xxxx, to kończymy, gdyż słowo kodera zostało odgadnięte. W przeciwnym przeglądamy kolejno pozostałe w zbiorze Z słowa kodowe. Dla przeglądanych słów kodowych oraz dla wylosowanego wcześniej słowa s łamacz  obliczamy nowy kod kluczowy s klucz2  i porównujemy go z s klucz  wprowadzonym przez człowieka. Jeśli kody się różnią, to dane słowo kodowe usuwamy ze zbioru, gdyż nie może ono być poszukiwanym słowem kodera. W ten sposób zbiór możliwych słów kodowych się zmniejsza. Jeśli jest niepusty, to wracamy na początek pętli i kontynuujemy losowanie kolejnego słowa. Jeśli zbiór jest pusty, to nastąpiła sprzeczność – człowiek popełnił gdzieś pomyłkę przy wprowadzaniu kodów kluczy. Zatem kończymy. Jeśli kod człowieka nie zostanie odgadnięty w 6 ruchach, to algorytm kończy się wypisaniem wszystkich pozostałych w zbiorze słów kodowych.

Pomimo swojej prostoty algorytm ten całkiem dobrze radzi sobie z odgadywaniem kodów kodera w 6 ruchach. Oczywiście, z uwagi na losowy charakter typowania przez komputer swoich ruchów, istnieje mała szansa, iż komputer przegra wybierając nieefektywne posunięcia (tzn. takie, które eliminują ze zbioru Z małą liczbę kodów ).

Zanim przystąpimy do tworzenia algorytmu, musimy rozwiązać kilka problemów. Pierwszym z nich jest reprezentacja zbioru Z, który musi posiadać właściwość usuwania elementów. Użyjemy do tego celu tablicy Z oraz dodatkowej zmiennej z n, która będzie przechowywała liczbę elementów pozostałych w tablicy. Aby system ten był efektywny, pozostałe elementy muszą być umieszczone w kolejnych komórkach od Z [ 0 ] do Z [ z n  - 1 ].

Teraz musimy określić operację usuwania elementu z tej struktury danych. Z tablicy nie można tak po prostu usunąć komórki. Dlatego przez usunięcie będziemy rozumieli zmniejszenie zawartości z n  oraz przesunięcie o jedną pozycję wstecz zawartości wszystkich komórek za komórką, z której usuwamy dane.

Przykład:

 Z = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, z n = 10, usuwamy element 5:

Z [ ] przed operacją, z n = 10 0 1 2 3 4 5 6 7 8 9
Usuwanie           X
Z [ ] po operacji, z n = 9 0 1 2 3 4 6 7 8 9 9

Widzimy, iż fizycznie tablica dalej posiada 10 elementów. Ponieważ jednak z n zostało zmniejszone, to pod uwagę bierzemy teraz tylko 9 pierwszych elementów tablicy. Element 5 został nadpisany i nie występuje już w tym obszarze tablicy – usunęliśmy go.

Operacja usuwania jest nam potrzebna po wylosowaniu kodu – aby nie był ponownie losowany. Ze zbioru Z musimy dodatkowo usuwać kody, które nie zgadzają się z otrzymanym kluczem. Zastosujemy tutaj nieco inną operację usuwania ze względu na liniową złożoność obliczeniową ( zastosowanie zwykłej operacji usuwania prowadziłoby do złożoności kwadratowej ). Polega ona na tym, iż ustawiamy dwa indeksy i 1 i i 2 na element Z [ 0 ]. Następnie przeglądamy indeksem i 1 kolejne elementy tablicy od Z [ 0 ] do Z [ z n  - 1 ]. Jeśli element Z [ i 1 ] ma pozostać w tablicy, to kopiujemy go do Z [ i 2 ], po czym i 2 zwiększamy o 1. Na końcu do z n  wprowadzamy i 2. W efekcie ze zbioru zostaną usunięte pominięte przez i 1 elementy.

Przykład:

 Z = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, z n  = 10, usuwamy elementy 3, 6, 7, 8:

Lp. Operacja Opis
1.
 0 1 2 3 4 5 6 7 8 9 
 i 1
 i 2 
Ustawiamy oba indeksy na pierwszy element zbioru.
Za pomocą indeksu i 1 przeglądamy kolejne elementy zbioru.
2.
 0 1 2 3 4 5 6 7 8 9 
 i 1
 i 2 
0 kopiujemy (na siebie, co nie jest szkodliwe ). Oba indeksy są zwiększane o 1.
3.
 0 1 2 3 4 5 6 7 8 9 
   i 1
   i 2 
1 kopiujemy, zwiększamy o 1 oba indeksy.
4.
 0 1 2 3 4 5 6 7 8 9 
     i 1
     i 2 
2 kopiujemy, zwiększamy o 1 oba indeksy.
5.
 0 1 2 3 4 5 6 7 8 9 
       i 1
       i 2 
3 pomijamy. Indeks i 2 nie jest zwiększany.
6.
 0 1 2 4 4 5 6 7 8 9 
       ↑ i 1
       i 2 
4 kopiujemy na miejsce 3, zwiększamy o 1 oba indeksy.
7.
 0 1 2 4 5 5 6 7 8 9 
         ↑ i 1
         i 2 
5 kopiujemy na miejsce 4, zwiększamy o 1 oba indeksy.
8.
 0 1 2 4 5 5 6 7 8 9 
           ↑ i 1
           i 2 
6 pomijamy
9.
 0 1 2 4 5 5 6 7 8 9 
           ↑   i 1
           i 2 
7 pomijamy
10.
 0 1 2 4 5 5 6 7 8 9 
           ↑     i 1
           i 2 
8 pomijamy
11.
 0 1 2 4 5 9 6 7 8 9 
           ↑       i 1
           i 2 
9 kopiujemy na miejsce 5, zwiększamy i 2.
12
 0 1 2 4 5 9 6 7 8 9 
             ↑     i 1
             i 2 
Koniec. W zbiorze pozostało i 2 elementów, wśród których nie ma już elementów pominiętych.

Kolejnym problemem jest sposób wygenerowania 1296 łańcuchów kodowych. Zadanie można rozwiązać na wiele sposobów. Jednym z nich jest potraktowanie każdego kodu jako 4 cyfrowej liczby szóstkowej. W systemie szóstkowym jest 6 cyfr {0, 1, 2, 3, 4, 5}. Numer kodu od 0 do 1295 traktujemy jako wartość liczby. Kolejne cyfry zapisu otrzymamy biorąc reszty z dzielenia liczby przez 6. Za nową liczbę bierzemy wynik dzielenia. Operację tę powtarzamy 4 razy i otrzymujemy 4 kolejne cyfry, które następnie zamieniamy na litery alfabetu od A do F.

Przykład:

Obliczymy wg tej metody wyraz o numerze 545:
545 : 6 =  90  i reszta 5 → F
90 : 6 =  15  i reszta 0 → A
15 : 6 =  2  i reszta 3 → D
2 : 6 =  0  i reszta 2 → C

Otrzymaliśmy wyraz kodowy FADC. W podobny sposób otrzymujemy pozostałe wyrazy.

Algorytm gry MasterMind – człowiek kontra komputer

Wejście:

4 znakowe kody klucza

Wyjście:

4 znakowe kody łamacza

Zmienne pomocnicze:

Z  – tablica kodów. Elementy są 4 znakowymi łańcuchami. Indeksy od 0 do 1295.
z n  – przechowuje liczbę elementów zbioru Z. z n  ∈ N
s łamacz  –  kod łamacza wygenerowany przez komputer
s klucz  – kod klucza wprowadzony przez człowieka
s klucz 2  – kod klucza wygenerowany przez komputer
i 1, i 2  – indeksy, i 1, i 2  ∈ N
runda  – numer rundy, runda  ∈ N
losowa ( x  )  – funkcja zwracająca liczbę pseudolosową od 0 do x - 1

Lista kroków:

K01: Utwórz kody w tablicy Z tablicę Z wypełniamy 1296 kodami 4 znakowymi
K02: z n  ← 1296 początkowa liczba kodów w tablicy
K03: Dla runda  = 1, 2, ..., 6:
wykonuj kroki K04...K17
rozpoczynamy rozgrywkę
K04:     Jeśli z n  = 0,
    to idź do kroku K18
jeśli zbiór Z jest pusty, kończymy – błędne dane człowieka
K05:     i 2 ← losowa ( z n  ) losujemy słówko kodowe
K06:     s łamacz  ← Z [ i 2 ] umieszczamy je w łańcuchu s łamacz
K07:     Usuń kod Z [ i 2 ] ze zbioru Z
    z n  ← z n  - 1
usuwamy wylosowane słowo i zmniejszamy z n o 1
K08:     Pisz runda, s łamacz wyświetlamy słowo kodowe dla człowieka
K09:     Czytaj s klucz odczytujemy klucz
K10:     Jeśli s klucz  = "xxxx",
    to idź do kroku K18
słowo odgadnięte? Jeśli tak, to kończymy
K11:     i 2 ← 0  
K12:     Dla i 1 = 0, 1, ..., z n - 1:
    wykonuj kroki K13...K16
przeglądamy zbiór Z i usuwamy z niego elementy nie pasujące do otrzymanego klucza
K13:         Oblicz s klucz2  dla s łamacz  i Z [ i 1 ] algorytm obliczania klucza podaliśmy w poprzednim rozdziale
K14:         Jeśli s klucz 2s klucz,
        to następny obieg pętli
K12
słowa kodowe nie pasujące do klucza pomijamy
K15:         Z [ i 2 ] ← Z [ i 1 ] słowa pasujące do klucza kopiujemy pod i 2
K16:         i 2i 2 + 1  
K17:     z n  ← i 2 korygujemy liczbę elementów zbioru Z
K18: Jeśli s klucz  = "xxxx",
to zakończ
 
K19: Dla i 1 = 0, 1, ..., z n - 1:
wykonuj: pisz Z [ i 1 ]
wypisujemy pozostałe w zbiorze Z kody
K20: 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 prowadzi rozgrywkę MasterMind z człowiekiem. Człowiek wymyśla 4-ro literowy kod zbudowany z liter od A do F. Następnie komputer w co najwyżej 6 rundach stara się ten kod odgadnąć. Prezentuje on człowiekowi swoje kody wraz z liczbą pozostałych w zbiorze Z kodów. W odpowiedzi człowiek powinien wprowadzić odpowiednie kody kluczy. Jeśli kod człowieka nie zostanie odgadnięty w ostatniej, szóstej rundzie, to komputer wypisuje wszystkie pozostałe w zbiorze Z kody.
Pascal
// MasterMind - komputer <-> człowiek
// Data: 17.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  Z : array [ 0..1295 ] of string;
  skoder, slamacz, sklucz, sklucz2, sl : string;
  zn, i, i1, i2, j, runda : integer;

begin

  randomize;

// tworzymy zbiór Z

  for i := 0 to 1295 do
  begin
    Z [ i ] := ''; i2 := i;
    for j := 1 to 4 do
    begin
      Z [ i ] := Z [ i ] + chr ( 65 + ( i2 mod 6 ) );
      i2 := i2 div 6;
    end;
  end;
  zn := 1296; // liczba kodów w Z

// rozgrywka

  for runda := 1 to 6 do
    if zn > 0 then
    begin
      i2 := random ( zn );
      slamacz := Z [ i2 ];

// usuwamy wylosowane słowo ze zbioru Z

      for i := i2 + 1 to zn - 1 do Z [ i - 1 ] := Z [ i ];
      dec ( zn );

// wylosowane słowo prezentujemy człowiekowi

      write ( 'Runda ', runda, ' : ', slamacz, zn:5, ' : ' );

// odczytujemy kod klucza

      readln ( sklucz );

// analizujemy dane

      if sklucz = 'xxxx' then break;

// ze zbioru Z wyrzucamy nie pasujące kody

      i2 := 0;
      for i1 := 0 to zn - 1 do
      begin
        skoder  := Z [ i1 ];
        sl      := slamacz;
        sklucz2 := '';
        for i := 1 to 4 do
          if skoder [ i ] = slamacz [ i ] then
          begin
            sklucz2   := sklucz2 + 'x';
            skoder [ i ] := '#'; // wartownik w1
            sl [ i ]     := '$'; // wartownik w2
          end;
        for i := 1 to 4 do
          if skoder [ i ] <> '#' then
            for j := 1 to 4 do
              if skoder [ i ] = sl [ j ] then
              begin
                sklucz2 := sklucz2 + 'o';
                sl [ j ]   := '$'; // wartownik w2
                break;
              end;
        if sklucz = sklucz2 then
        begin
          Z [ i2 ] := Z [ i1 ];
          inc ( i2 );
        end;
      end;
      zn := i2;
    end
    else break;

// wyświetlamy pozostałe kody w Z

  writeln;
  if sklucz <> 'xxxx' then
  begin
    for i := 1 to zn do write ( Z [ i-1 ], ' ' );
    writeln; writeln;
  end;
end.
C++
// MasterMind - komputer <-> człowiek
// Data: 17.08.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

int main( )
{
  string Z [ 1296 ], skoder, slamacz, sklucz, sklucz2, sl;
  int zn, i, i1, i2, j, runda;

  srand ( ( unsigned )time ( NULL ) );

// tworzymy zbiór Z

  for( i = 0; i < 1296; i++ )
  {
    Z [ i ] = ""; i2 = i;
    for( j = 0; j < 4; j++ )
    {
      Z [ i ] += char ( 65 + ( i2 % 6 ) );
      i2 /= 6;
    }
  }
  zn = 1296; // liczba kodów w Z

// rozgrywka

  for( runda = 1; runda < 6; runda++ )
    if( zn > 0 )
    {
      i2 = rand( ) % zn;
      slamacz = Z [ i2 ];

// usuwamy wylosowane słowo ze zbioru Z

      for( i = i2 + 1; i < zn; i++ ) Z [ i - 1 ] = Z [ i ];
      zn--;

// wylosowane słowo prezentujemy człowiekowi

      cout << "Runda " << runda << ": " << slamacz
           << setw ( 5 )  << zn    << ": ";

// odczytujemy kod klucza

      cin >> sklucz;

// analizujemy dane

      if( sklucz == "xxxx" ) break;

// ze zbioru Z wyrzucamy nie pasujące kody

      for( i2 = i1 = 0; i1 < zn; i1++ )
      {
        skoder  = Z [ i1 ];
        sl      = slamacz;
        sklucz2 = "";
        for( i = 0; i < 4; i++ )
          if( skoder [ i ] == slamacz [ i ] )
          {
            sklucz2     += 'x';
            skoder [ i ] = '#'; // wartownik w1
            sl [ i ]     = '$'; // wartownik w2
          }
        for( i = 0; i < 4; i++ )
          if( skoder [ i ] != '#' )
            for( j = 0; j < 4; j++ )
              if( skoder [ i ] == sl [ j ] )
              {
                sklucz2  += 'o';
                sl [ j ]  = '$'; // wartownik w2
                break;
              }
        if( sklucz == sklucz2 ) Z [ i2++ ] = Z [ i1 ];
      }
      zn = i2;
    }
    else break;

// wyświetlamy pozostałe kody w Z

  cout << endl;
  if( sklucz != "xxxx" )
  {
    for( i = 1; i <= zn; i++ ) cout << Z [ i-1 ] << " ";
    cout << endl << endl;
  }
  return 0;
}
Basic
' MasterMind - komputer <-> człowiek
' Data: 17.08.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String Z ( 1295 ), skoder, slamacz, sklucz, sklucz2, sl
Dim As Integer zn, i, i1, i2, j, runda

Randomize

' tworzymy zbiór Z

For i = 0 To 1295
  Z ( i ) = "": i2 = i
  For j = 1 To 4
    Z ( i ) += Chr ( 65 + ( i2 Mod 6 ) )
    i2 \= 6
  Next
Next
zn = 1296 ' liczba kodów w Z

' rozgrywka

For runda = 1 To 6
  If zn > 0 Then
    i2 = Cint ( Rnd * ( zn - 1 ) )
    slamacz = Z ( i2 )

' usuwamy wylosowane słowo ze zbioru Z

    For i = i2 + 1 To zn - 1: Z ( i - 1 ) = Z ( i ): Next
    zn -= 1

' wylosowane słowo prezentujemy człowiekowi

    Print Using "Runda # : &##### : ";runda;slamacz;zn;

' odczytujemy kod klucza

    Line Input sklucz

' analizujemy dane

    If sklucz = "xxxx" Then Exit For

' ze zbioru Z wyrzucamy nie pasujące kody

    i2 = 0
    For i1 = 0 To zn - 1
      skoder  = Z ( i1 )
      sl      = slamacz
      sklucz2 = ""
      For i = 1 To 4
        If Mid ( skoder, i, 1 ) = Mid ( slamacz, i, 1 ) Then
          sklucz2  += "x"
          Mid ( skoder, i, 1 ) = "#" ' wartownik w1
          Mid ( sl, i, 1 )     = "$" ' wartownik w2
        End If
      Next
      For i = 1 To 4
        If Mid ( skoder, i, 1 ) <> "#" Then
          For j = 1 To 4
            If Mid ( skoder, i, 1 ) = Mid ( sl, j, 1 ) Then
              sklucz2    += "o"
              Mid ( sl, j, 1 ) = "$" ' wartownik w2
              Exit For
            End If
          Next
        End If
      Next
      If sklucz = sklucz2 Then
        Z ( i2 ) = Z ( i1 )
        i2 += 1
      End If
      zn = i2
    Next
  Else
    Exit For
  End If
Next

' wyświetlamy pozostałe kody w Z

Print
If sklucz <> "xxxx" Then
  For i = 1 To zn: Print Z ( i - 1 );" ";: Next
  Print: Print
End If
End
Wynik:
Runda 1 : EBAC 1295 : oo
Runda 2 : ADCF  311 : x
Runda 3 : AAEA   21 : xx
Runda 4 : AABB    1 : xxxx
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.