Kółko i krzyżyk Minimax Alfa Beta

1

Witam,
mam problem z moim programem, a dokładniej z algorytmem minimax. Algorytm wybiera dziwne ruchy, nie prowadzące do wygranej. Nie robi też ruchów po kolei, ruchy wydają się jakby losowe. Proszę o jakieś sugestie.

#include <iostream>

using namespace std;

void plansza(char p[])
{
    for(int i=1;i<=9;i++)
    {
        cout<<" "<<p[i]<<" ";
        if(i%3) 
        cout<<"|";
        else if(i==3||i==6)
        cout<<"\n---+---+---\n";
        else
        cout<<endl;
    }
}

// Funkcja zwraca true, jeśli ktoś wygrał
bool wygrana(char t[], char g, bool cisza)
{
  bool test;
  int i;

  test = false; 

//wiersze

  for(i = 1; i <= 7; i += 3) test |= ((t[i] == g) && (t[i+1] == g) && (t[i+2] == g));

//kolumny  

  for(i = 1; i <= 3; i++)    test |= ((t[i] == g) && (t[i+3] == g) && (t[i+6] == g));

//przekątną 1-5-9

  test |= ((t[1] == g) && (t[5] == g) && (t[9] == g));

//przekątną 3-5-7

  test |= ((t[3] == g) && (t[5] == g) && (t[7] == g));

  if(test)
  {
    if(!cisza)
    {
      plansza(t);
      cout << "\nGRACZ " << g << " WYGRYWA!!!\n\n";
    }
    return true;
  }
  return false;
}

bool remis(char t[], bool cisza)
{

  for(int i = 1; i <= 9; i++) if(t[i] == ' ') return false;

  if(!cisza)
  {
    plansza(t); cout << "\nREMIS !!!\n\n";
  }
  return true;     
}

int minimax(char t[],int glebokosc, char gracz,int alfa, int beta)
{
  int eval, mineval,maxeval;

  if(wygrana(t,gracz,true))
  return (gracz == 'X') ? 10 : -10;

  if(remis(t,true)) 
  return 0;

if(gracz == 'O')
{
  maxeval=-1000;
  for(int i = 1; i <= 9; i++)
    {
      if(t[i] == ' ')
      {
        t[i] = gracz;
        eval = minimax(t,glebokosc+1,gracz,alfa,beta);
        t[i] = ' ';
        maxeval=max(maxeval,eval);
        alfa=max(alfa,maxeval);
        if(beta<=alfa)
        break;
      } 
    }
    return maxeval;
}
else if(gracz == 'X')
{
  mineval=999;
  for(int i = 1; i <= 9; i++)
    {
      if(t[i] == ' ')
      {
        t[i] = gracz;
        eval = minimax(t,glebokosc+1,gracz,alfa,beta);
        t[i] = ' ';
        mineval=min(mineval,eval);
        beta=min(beta,mineval);
        if(beta<=alfa)
        break;
      } 
    }
  return mineval;
}
}

int komputer(char t[],int alfa, int beta)
{
  int ruch, i, m, mmx;

  mmx = -999;
  for(i = 1; i <= 9; i++)
  {
    if(t[i] == ' ')
    {
      t[i] = 'X';
      m = minimax(t,0,'X',alfa,beta);
      t[i] = ' ';
      alfa=max(alfa,mmx);
      if(beta<=alfa)
      {
      break;
      }
      if(m > mmx)
      {
        mmx = m; 
        ruch = i;     
      }        
    }   
  } 
  return ruch;
}

void ruch(char t[], char &gracz)
{
  int r;

  plansza(t);
  if(gracz == 'O')
  {
    cout << "\nWybier wolne pole : ";
    cin >> r;
  }
  else
  {
    r = komputer(t,-999,999);
    cout << "\nKOMPUTER : wybiera ruch : " << r << endl;
  }

  cout << "---------------------------\n\n";
  if((r >= 1) && (r <= 9) && (t[r] == ' '))
  {
  t[r] = gracz;
  gracz = (gracz == 'O') ? 'X' : 'O';//zmiana zawodnika
  }
  else 
  {
  cout<<"To nie jest wolne pole!"<<endl;
  }

}

main()
{
  char t[10],gracz,wybor,wybor2;

  do
  {
    cout << "Gra w Kolko i Krzyzyk dla gracza i komputera\n"
            "============================================\n\n"
            "Kto zaczyna?\n"
            "g-gracz\n"
            "k-komputer\n\n";

    cin>>wybor2;

    if (wybor2=='g')
    {
    for(int i = 1; i <= 9; i++) t[i] = ' ';
    gracz = 'O';
    }
    else if (wybor2=='k')
    {
    for(int i = 1; i <= 9; i++) t[i] = ' ';
    gracz = 'X';
    }

    while(!wygrana(t,'X',false) && !wygrana(t,'O',false) && !remis(t,false)) ruch(t,gracz);

    cout << "Jeszcze raz ? (T = TAK) : ";
    cin >> wybor; 
    cout << "\n\n\n";

  } while((wybor == 'T') || (wybor == 't'));
}
4

Nie mam jak to lepiej skomentować oprócz ostatnią repliką z ostatniego odcinku serialu Lucyfera: - O my me!
Radzę wszystko wywalić, przemyśleć i napisać od nowa!

0

Niestety nie za bardzo mam czas, na napisanie nowego. W programowaniu jestem dość nowy i sam program wydawał mi się okej. Czy nie można tu nic zmienić żeby działał poprawnie?

1

Może zmień rozmiar planszy bo nie od dziś wiadomo ze 3x3 jest nierozstrzygalne.
Poza tym zdefiniuj planszę jako dwu-wymiarową tablicę.
https://www.geeksforgeeks.org/pass-2d-array-parameter-c/
https://www.geeksforgeeks.org/dynamically-allocate-2d-array-c/

Coś do poczytania:
https://www.geeksforgeeks.org[...]-toe-ai-finding-optimal-move/

0
vpiotr napisał(a):

Może zmień rozmiar planszy bo nie od dziś wiadomo ze 3x3 jest nierozstrzygalne.

3x3 jest oczywiście rozstrzygalne i rozstrzygnięciem jest remis... To miał na myśli @vpiotr? :)

@Maren -- duży bałagan w kodzie, magiczne liczby, czasem masz -999 a czasem -1000 i co one znaczą?

0
Maren napisał(a):

Witam,
mam problem z moim programem, a dokładniej z algorytmem minimax. Algorytm wybiera dziwne ruchy, nie prowadzące do wygranej. Nie robi też ruchów po kolei, ruchy wydają się jakby losowe. Proszę o jakieś sugestie.

Nie rób tego, niewiele przyśpieszy:

        if(beta<=alfa)
        break;

Te wiersze można zrobić po pętle:

        beta=min(beta,mineval);
        alfa=max(alfa,maxeval);
0

Moje rozwiązanie Tic-Tac-Toe.rar. Po testuj i przeanalizuj plik o nazwie silnik :).

0

Bardzo dziękuję za wszystkie odpowiedzi, udało mi się to naprawić :)

0

W ramach podziękowania byś pokazał kod :). Niech inni też z niego skorzystają ;).

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0