Algorytmy i Struktury Danych - MasterMind człowiek kontra komputer

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 z procesorem 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₁ i i₂ na element Z[0]. Następnie przeglądamy indeksem i₁ kolejne elementy tablicy od Z[0] do Z[z_n-1]. Jeśli element Z[i₁] ma pozostać w tablicy, to kopiujemy go do Z[i₂], po czym i₂ zwiększamy o 1. Na końcu do z_n wprowadzamy i₂. W efekcie ze zbioru zostaną usunięte pominięte przez i₁ 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₁ i₂	Ustawiamy oba indeksy na pierwszy element zbioru. Za pomocą indeksu i₁ przeglądamy kolejne elementy zbioru.
2.	0 1 2 3 4 5 6 7 8 9 i₁ i₂	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₁ i₂	1 kopiujemy, zwiększamy o 1 oba indeksy.
4.	0 1 2 3 4 5 6 7 8 9 i₁ i₂	2 kopiujemy, zwiększamy o 1 oba indeksy.
5.	0 1 2 3 4 5 6 7 8 9 i₁ i₂	3 pomijamy. Indeks i₂ nie jest zwiększany.
6.	0 1 2 4 4 5 6 7 8 9 ↑ i₁ i₂	4 kopiujemy na byłe miejsce 3, zwiększamy o 1 oba indeksy.
7.	0 1 2 4 5 5 6 7 8 9 ↑ i₁ i₂	5 kopiujemy na byłe miejsce 4, zwiększamy o 1 oba indeksy.
8.	0 1 2 4 5 5 6 7 8 9 ↑ i₁ i₂	6 pomijamy
9.	0 1 2 4 5 5 6 7 8 9 ↑ i₁ i₂	7 pomijamy
10.	0 1 2 4 5 5 6 7 8 9 ↑ i₁ i₂	8 pomijamy
11.	0 1 2 4 5 9 6 7 8 9 ↑ i₁ i₂	9 kopiujemy na byłe miejsce 5, zwiększamy i₂.
12	0 1 2 4 5 9 6 7 8 9 ↑ i₁ i₂	Koniec. W zbiorze pozostało i₂ 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_klucz2 : kod klucza wygenerowany przez komputer.
i₁,i₂ : indeksy; i₁,i₂ ∈ 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: ; rozpoczynamy rozgrywkę
     wykonuj kroki K04…K18
K04:   Jeśli z_n = 0, ; jeśli zbiór Z jest pusty, kończymy – błędne dane człowieka
       to idź do kroku K19
K05:   i₂ ← losowa(z_n) ; losujemy słówko kodowe
K06:   s_łamacz ← Z[i₂] ; umieszczamy je w łańcuchu s_łamaczK07:   Usuń kod Z[i₂] ze zbioru Z
K08:   z_n ← z_n-1 ; usuwamy wylosowane słowo i zmniejszamy z_n o 1
K09:   Pisz runda,s_łamacz; wyświetlamy słowo kodowe dla człowieka
K10:   Czytaj s_klucz; odczytujemy klucz
K11:   Jeśli s_klucz = "xxxx", ; słowo odgadnięte? Jeśli tak, to kończymy
       to idź do kroku K19
K12:   i₂ ← 0
K13:   Dla i₁ = 0,1,…, z_n-1: ; przeglądamy zbiór Z i usuwamy z niego elementy
       wykonuj kroki K14…K17 ; nie pasujące do otrzymanego klucza
K14:     Oblicz s_klucz2 dla s_łamacz i Z[i₁] ; algorytm obliczania klucza
         ; podaliśmy w poprzednim rozdziale
K15:     Jeśli s_klucz2 ≠ s_klucz, ; słowa kodowe nie pasujące do klucza pomijamy
         to następny obieg pętli K13
K16:     Z[i₂] ← Z[i₁] ; słowa pasujące do klucza kopiujemy pod i₂K17:     i₂ ← i₂+1
K18:   z_n ← i₂ ; korygujemy liczbę elementów zbioru Z
K19: Jeśli s_klucz = "xxxx",
     to zakończ

K20: Dla i₁ = 0,1,…,z_n-1: ; wypisujemy pozostałe w zbiorze Z kody
     wykonuj: pisz Z[i₁]
K21: 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 <ctime>

using namespace std;

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

  srand(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

      getline(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

Python (dodatek)

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

import random

# tworzymy zbiór Z

Z = []
for i in range(1296):
    Z.append("")
    i2 = i;
    for j in range(4):
        Z[i] += chr(65+(i2%6))
        i2 //= 6

zn = 1296 # liczba kodów w Z

# rozgrywka

for runda in range(1,7):
    if zn > 0:
        i2 = random.randrange(zn)
        slamacz = Z[i2][:]

# usuwamy wylosowane słowo ze zbioru Z

        for i in range(i2+1,zn):
            Z[i-1] = Z[i][:]
        zn -= 1

# wylosowane słowo prezentujemy człowiekowi

        print("Runda",runda,":",slamacz,"%5d" % zn,":",end=" ")

# odczytujemy kod klucza

        sklucz = input()

# analizujemy dane

        if sklucz == "xxxx": break

# ze zbioru Z wyrzucamy nie pasujące kody

        i2 = 0
        for i1 in range(zn):
            skoder  = Z[i1][:]
            sl      = slamacz[:]
            sklucz2 = ""
            for i in range(4):
                if skoder[i] == slamacz[i]:
                    sklucz2  += 'x'
                    skoder = skoder[:i]+'#'+skoder[i+1:]
                    sl = sl[:i]+'$'+sl[i+1:]
            for i in range(4):
                if skoder[i] != '#':
                    for j in range(4):
                        if skoder[i] == sl[j]:
                            sklucz2 += 'o'
                            sl = sl[:j]+'$'+sl[j+1:]
                            break
            if sklucz == sklucz2:
                Z[i2] = Z[i1][:]
                i2 += 1
        zn = i2
    else: break

# wyświetlamy pozostałe kody w Z

print()
if sklucz != "xxxx":
    for i in range(1,zn+1):
        print(Z[i-1],end=" ")
print()
print()

Wynik:

Runda 1 : CBFF  1295 : o
Runda 2 : EAAB   275 : xxo
Runda 3 : EABE    14 : xx
Runda 4 : EACA     2 : xo
Runda 5 : AABB     0 : xxxx

Na początek: podrozdziału 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 - człowiek kontra komputer