MasterMind - człowiek kontra komputer


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Podstawowe operacje na tablicach

 

Problem

Opracować algorytm gry MasterMind – człowiek kontra komputer.


 

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 sklucz 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 sklucz2 i porównujemy go z sklucz 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 zn, 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[zn - 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 zn 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}, zn = 10, usuwamy element 5:

 

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

 

Widzimy, iż fizycznie tablica dalej posiada 10 elementów. Ponieważ jednak zn 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 i1 i i2 na element Z[0]. Następnie przeglądamy indeksem i1 kolejne elementy tablicy od Z[0] do Z[zn - 1]. Jeśli element Z[i1] ma pozostać w tablicy, to kopiujemy go do Z[i2], po czym i2 zwiększamy o 1. Na końcu do zn wprowadzamy i2. W efekcie ze zbioru zostaną usunięte pominięte przez i1 elementy.

 

Przykład:

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

 

Lp. Operacja Opis
1.
 0 1 2 3 4 5 6 7 8 9 
 i1
 i2 
Ustawiamy oba indeksy na pierwszy element zbioru.
Za pomocą indeksu i1 przeglądamy kolejne elementy zbioru.
2.
 0 1 2 3 4 5 6 7 8 9 
 i1
 i2 
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 
   i1
   i2 
1 kopiujemy, zwiększamy o 1 oba indeksy.
4.
 0 1 2 3 4 5 6 7 8 9 
     i1
     i2 
2 kopiujemy, zwiększamy o 1 oba indeksy.
5.
 0 1 2 3 4 5 6 7 8 9 
       i1
       i2 
3 pomijamy. Indeks i2 nie jest zwiększany.
6.
 0 1 2 4 4 5 6 7 8 9 
        i1
       i2 
4 kopiujemy na miejsce 3, zwiększamy o 1 oba indeksy.
7.
 0 1 2 4 5 5 6 7 8 9 
          i1
         i2 
5 kopiujemy na miejsce 4, zwiększamy o 1 oba indeksy.
8.
 0 1 2 4 5 5 6 7 8 9 
            i1
           i2 
6 pomijamy
9.
 0 1 2 4 5 5 6 7 8 9 
              i1
           i2 
7 pomijamy
10.
 0 1 2 4 5 5 6 7 8      i1
           i2 
8 pomijamy
11.
 0 1 2 4 5 9 6 7 8
                i1
           i2 
9 kopiujemy na miejsce 5, zwiększamy i2.
12
 0 1 2 4 5 9 6 7 8 9 
                  i1
             i2 
Koniec. W zbiorze pozostało i2 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.
zn  – przechowuje liczbę elementów zbioru Z. zn N
słamacz  –  kod łamacza wygenerowany przez komputer
sklucz  – kod klucza wprowadzony przez człowieka
sklucz2  – kod klucza wygenerowany przez komputer
i1,i2  – indeksy, i1, i2 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: zn ← 1296 ; początkowa liczba kodów w tablicy
K03: Dla runda = 1,2,...,6 wykonuj K04...K17 ; rozpoczynamy rozgrywkę
K04:     Jeśli zn = 0, to idź do K18 ; jeśli zbiór Z jest pusty, kończymy – błędne dane człowieka
K05:     i2 ← losowa(zn) ; losujemy słówko kodowe
K06:     słamacz ← Z[i2] ; umieszczamy je w łańcuchu słamacz
K07:     Usuń kod Z[i2] ze zbioru Z;   znzn - 1 ; usuwamy wylosowane słowo i zmniejszamy zn o 1
K08:     Pisz runda, słamacz ; wyświetlamy słowo kodowe dla człowieka
K09:     Czytaj sklucz ; odczytujemy klucz
K10:     Jeśli sklucz = "xxxx", to idź do K18 ; słowo odgadnięte? Jeśli tak, to kończymy
K11:     i2 ← 0 ; przeglądamy zbiór Z i usuwamy z niego
K12:     Dla i1 = 0,1,...,zn - 1 wykonuj K13...K16 ; elementy nie pasujące do otrzymanego klucza
K13:         Oblicz sklucz2 dla słamacz i Z[i1] ; algorytm obliczania klucza podaliśmy w poprzednim rozdziale
K14:         Jeśli sklucz2sklucz, to następny obieg pętli K12 ; słowa kodowe nie pasujące do klucza pomijamy
K15:         Z[i2] ← Z[i1] ; słowa pasujące do klucza kopiujemy pod i2
K16:         i2i2 + 1  
K17:     zn i2 ; korygujemy liczbę elementów zbioru Z
K18: Jeśli sklucz = "xxxx", to zakończ  
K19: Dla i1 = 0,1,...,zn-1: pisz Z[i1] ; wypisujemy pozostałe w zbiorze Z kody
K20: Zakończ  

 

Program

Ważne:

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.

 

Lazarus
// MasterMind - komputer <-> człowiek
// Data: 17.08.2008
// (C)2012 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.
Code::Blocks
// MasterMind - komputer <-> człowiek
// Data: 17.08.2008
// (C)2012 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;
}
Free Basic
' MasterMind - komputer <-> człowiek
' Data: 17.08.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


.

          

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.