Algorytm Minimax - Gra w Kółko i Krzyżyk

Zapoznaj się z materiałami przedstawionymi na poprzednich zajęciach koła:

 

Utwórz nowy katalog projektowy. Skopiuj do niego pliki biblioteki:

newconio.cpp  -  plik źródłowy biblioteki
newconio.h  - plik nagłówkowy dla biblioteki

Utwórz nowy projekt konsoli w Dev-C++. Do projektu dodaj plik źródłowy newconio.cpp z twojego katalogu projektowego.

 

Minimax

Minimax jest algorytmem stosowanym w prostych grach logicznych do wyznaczania optymalnych ruchów. Jest algorytmem rekurencyjnym, który wywołuje sam siebie do analizy kolejnych ruchów w grze. Zasada działania dla dwóch graczy jest następująca:

Algorytm dokonuje oceny stanu gry na danym poziomie. Poziom zero oznacza bezpośrednio wykonywany ruch, poziomy wyższe służą do analizy ruchu na poziomie 0.

  1. Jeśli bieżący gracz wygrywa, to algorytm zwraca 1, dla gracza A i -1 dla gracza B. Jeśli poziom jest równy zero, to gracz wykonuje ruch wygrywający.

  2. Jeśli jest remis, to zwracane jest 0. Przy poziomie zero wykonywany jest ruch.

  3. Algorytm stawia dla danego gracza wszystkie możliwe ruchy, a następnie wywołuje sam siebie rekurencyjnie z wyższym poziomem dla drugiego gracza. Algorytm zapamiętuje te ruchy, które maksymalizują dla danego gracza wartość stanu gry otrzymaną z wyższego poziomu. Jeśli graczem dla bieżącego poziomu jest A, to szuka on ruchów dających wartość większą od -1 (co jest wygraną dla gracza B). Jeśli graczem jest B, to szuka on ruchów dających wartość mniejszą od 1 (co jest wygraną dla gracza A). Po wyznaczeniu najlepszego ruchu zwracana jest jego wartość. Jeśli poziom jest równy zero, to znaleziony ruch jest wykonywany.

Gra w Kółko i Krzyżyk

Typowym wykorzystaniem algorytmu Minimax jest znana gra w kółko i krzyżyk. Gra toczy się na planszy zbudowanej z 9 pól ułożonych w 3 wiersze i 3 kolumny. Gracze wpisują naprzemian w pola swoje znaki - jeden wpisuje kółka, a drugi krzyżyki. Wygrywa ten z graczy, który jako pierwszy postawi trzy swoje znaki w wierszu, w kolumnie lub po przekątnych. Remis występuje wtedy, gdy pola planszy zostaną zapełnione, a żaden z graczy nie osiągnie zwycięstwa.

W naszej grze zawsze rozpoczyna człowiek stawiając kółka. Komputer stawia krzyżyki. Pola planszy wybieramy klawiszami na tabliczce numerycznej

 

Program

// Kółko i Krzyżyk - algorytm Minimax
// (C)2009 Koło informatyczne w I LO w Tarnowie
// Kurs programowania w C++ dla początkujących
//--------------------------------------------

#include "newconio.h"

// Zmienne globalne
//-----------------
char xo[3][3];  // przechowuje planszę gry

// Czyści pole gry
//----------------
void czysc_xo()
{
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++) xo[i][j] = ' ';     
}

// Inicjuje bibliotekę, ekran i wyświetla
// planszę tytułową gry
//---------------------------------------
void start()
{
  _cinit();

  fullscreen(true); cursoroff(); textattr(0x2f); clrscr();
  fillframe(FRAME_SINGLE,0xe9,20,19,59,29);
  
  textattr(0xe4);
  center(21,_pl("(C)2009 I Liceum Ogólnokształcące"));
  center(22,_pl("im. Kazimierza Brodzińskiego"));
  center(23,"w Tarnowie");
  textattr(0xe0);
  center(25,_pl("KOŁO NAUKOWE INFORMATYKI"));
  textattr(0xe1);
  center(27,_pl("G-R-A  w  K-Ó-Ł-K-O i K-R-Z-Y-Ż-Y-K"));

  fillrectattr(0,0,49,79,49);
  textattr(0x0f);
  center(49,_pl("Naciśnij dowolny klawisz, aby rozpocząć grę..."));

  while(!getch());
}

// Sprawdza, czy gracz chce grac dalej
//------------------------------------
bool jeszcze_raz()
{
  textattr(0x4e);
  center(49,"Jeszcze raz? (T = TAK)");
  
  char klawisz;
  
  while(!(klawisz = getch()));
  
  return (klawisz == 'T') || (klawisz == 't');     
}

// Plansza gry
//------------
void plansza()
{
  textattr(0); clrscr();
  
  fillrectattr(0x40,0,49,79,49);
  
  frame(FRAME_DOUBLE,0x09,30,15,48,33);
  
  fillrect(196,0x09,31,21,47,21);    
  fillrect(196,0x09,31,27,47,27);
  fillrect(179,0x09,36,16,36,32);
  fillrect(179,0x09,42,16,42,32);
  
  putxy(197,0x09,36,21);
  putxy(197,0x09,36,27);
  putxy(197,0x09,42,21);
  putxy(197,0x09,42,27);
  
  int licznik = 1;
  
  for(int w = 2; w >= 0; w--)
    for(int k = 0; k < 3; k++)
      putxy(48 + licznik++, 0x01, 31 + 6 * k, 16 + 6 * w);
}

// Wyświetla tablicę xo
//---------------------
void pokaz_xo()
{
  for(int w = 0; w < 3; w++)
    for(int k = 0; k < 3; k++)
      putxy(xo[w][k], 0x0f, 33 + 6 * k, 18 + 6 * w);     
}

// Ruch człowieka
//---------------
void ruch_cz()
{
  char klawisz;
  bool ruch_zly;
  
  do
  {
    ruch_zly = true;
    
    while(!(klawisz = getch()));
    
// sprawdzamy, czy gracz nacisnął właściwy klawisz

    if((klawisz >= '1') && (klawisz <= '9'))
    {
      int w,k,v;
      
      v = klawisz - 48;
      k = (v - 1) % 3;
      w = 2 - (v - 1) / 3;

// sprawdzamy, czy wybrana pozycja planszy jest wolna

      if(xo[w][k] == ' ')
      {
        xo[w][k] = 'o';
        ruch_zly = false;
      }
    }
  } while(ruch_zly);
}

// Sprawdza, czy gracz wygrał
//---------------------------
bool wygrana(char gracz)
{
  // przekątne

  if((xo[0][0] == gracz) && (xo[1][1] == gracz) && (xo[2][2] == gracz)) return true;

  if((xo[0][2] == gracz) && (xo[1][1] == gracz) && (xo[2][0] == gracz)) return true;
     
  // wiersze i kolumny
  
  for(int i = 0; i < 3; i++)
  {
  
    if((xo[i][0] == gracz) && (xo[i][1] == gracz) && (xo[i][2] == gracz)) return true;
       
    if((xo[0][i] == gracz) && (xo[1][i] == gracz) && (xo[2][i] == gracz)) return true;
  }       
  return false;          
}

// sprawdza wolne pola w xo
//-------------------------
bool wolne()
{
  for(int w = 0; w < 3; w++)
    for(int k = 0; k < 3; k++)
      if(xo[w][k] == ' ') return true;
  return false;     
}

// Algorytm MiniMax
//-----------------
int minimax(char gracz, int poziom)
{
  int licznik = 0;
  int w,k;
  
  // sprawdzamy, czy jest wygrana
  
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
      if(xo[i][j] == ' ')
      {
        xo[i][j] = gracz;
        w = i; k = j;  // gdyby był remis
        licznik++;     // zliczamy wolne pola

        bool test = wygrana(gracz);
        
        xo[i][j] = ' ';
        if(test)
        {
          if(!poziom) xo[i][j] = gracz;
          return gracz == 'x' ? -1 : 1;
        }
      }
  
  // sprawdzamy, czy jest remis
  
  if(licznik == 1)
  {
    if(!poziom) xo[w][k] = gracz;
    return 0;           
  }
  
  // wybieramy najkorzystniejszy ruch dla gracza
  
  int v;
  int vmax;
  
  vmax = gracz == 'x' ? 2 : -2;
  
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
      if(xo[i][j] == ' ')
      {
        xo[i][j] = gracz;
        v = minimax(gracz == 'x' ? 'o' : 'x', poziom + 1);
        xo[i][j] = ' ';

        if(((gracz == 'x') && (v < vmax)) || ((gracz == 'o') && (v > vmax)))
        {
          vmax = v; w = i; k = j; 
        }
      }
      
   if(!poziom) xo[w][k] = gracz;
   
   return vmax;
}

// Podświetla wygranego gracza na czerwono
//----------------------------------------
void pokaz_wygrana()
{
  // przekątna \
  
  if((xo[0][0] == xo[1][1]) && (xo[0][0] == xo[2][2]))
  {
    for(int i = 0; i < 3; i++) putattrxy(0x0c,33 + 6 * i,18 + 6 * i);
    return;
  }
  
  // przekatna /
  
  if((xo[0][2] == xo[1][1]) && (xo[0][2] == xo[2][0]))
  {
    for(int i = 0; i < 3; i++) putattrxy(0x0c,33 + 6 * (2 - i),18 + 6 * i);
    return;
  }
  
  // wiersze -
  
  for(int w = 0; w < 3; w++)
    if((xo[w][0] == xo[w][1]) && (xo[w][0] == xo[w][2]))
    {
      for(int i = 0; i < 3; i++) putattrxy(0x0c,33 + 6 * i,18 + 6 * w);
      return;        
    }
    
  // kolumny |
  
  for(int k = 0; k < 3; k++)
    if((xo[0][k] == xo[1][k]) && (xo[0][k] == xo[2][k]))
    {
      for(int i = 0; i < 3; i++) putattrxy(0x0c,33 + 6 * k,18 + 6 * i);
      return;
    }
}

// **********************
// *** START PROGRAMU ***
// **********************

main()
{
  start();
  
  do
  {
    czysc_xo(); plansza();
    do
    {
      ruch_cz(); pokaz_xo();
      
      if(wygrana('o')) break;  // to się nigdy nie zdarzy :)
      
      if(wolne())
      {
         minimax('x',0); pokaz_xo();
         if(wygrana('x')) break;
      }
      else break;
      
    } while(true);

    pokaz_wygrana();

  } while(jeszcze_raz());
  
  fullscreen(false); cursoron(); textattr(7); clrscr();
}

 



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.