MasterMind - kompuer kontra człowiek


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
Podstawowe operacje na tablicach

 

Problem

Opracować algorytm gry MasterMind w wersji: komputer kontra człowiek.


 

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.

Elementy pomocnicze:
skoder  –  kod kodera
sk  – kopia kodu kodera
sklucz  – kod klucza
i,j  – indeksy, i,j N
runda  – numer rundy, runda N
Lista kroków:
K01: Generuj skoder ; generujemy 4-znakowy kod kodera
K02: Dla runda = 1,2,...,6: wykonuj K03...K19 ; łamacz ma maksymalnie 6 podejść
K03:     Czytaj słamacz ; odczytujemy kod łamacza
K04:     Dopóki |słamacz| < 4 wykonuj:
        słamaczsłamacz + w2
; kod łamacza musi być co najmniej
; 4-ro znakowy, w2 – wartownik
K05:     skskoder ; kopiujemy kod kodera
K06:     sklucz ← '' ; zerujemy kod klucza
K07:     Dla i = 1,2,...,4 wykonuj K08...K11 ; szukamy znaków zgodnych co do typu i pozycji
K08:         Jeśli sk[i] ≠ slamacz[i], to
        następny obieg pętli K07
; znaki niezgodne pomijamy
K09:         skluczsklucz + "x" ; w kluczu umieszczamy znak x
K10:         sk[i] ← w1 ; znaki zastępujemy wartownikami,
K11:         słamacz[i] ← w2 ; aby nie były później zaliczane
K12:     Dla i = 1,2,...,4, wykonuj K13...K18 ; szukamy znaków zgodnych co do pozycji
K13:         Jeśli sk[i] = w1, to
        następny obieg pętli K12
; znaki usunięte pomijamy
K14:         Dla j = 1,2,...,4, wykonuj K15...K18 ; znak kodera porównujemy z kolejnymi znakami łamacza
K15:             Jeśli sk[i] ≠ słamacz[j], to
            następny obieg pętli K14
; pomijamy znaki różne
K16:             sklucz sklucz + "o" ; w kluczu umieszczamy znak o
K17:             słamacz[j] ← w2 ; znak łamacza zastępujemy wartownikiem
K18:             Następny obieg pętli K12 ; przechodzimy do następnego znaku kodera
K19:     Pisz sklucz ; wyprowadzamy kod klucza
K20:     Jeśli sklucz = "xxxx", to idź do K21 ; kończymy pętlę K02, jeśli kod kodera odgadnięty
K21: Pisz skoder ; wyprowadzamy kod kodera
K22: 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 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.

 

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