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 zupełnie 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 zbyt 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.

Elementy 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

sklucz = ''
# 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

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