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

// 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();
}