Algorytm MiniMax

0

Witam,
właśnie próbuję zaprogramować grę w kółko i krzyżyk. Mój problem dotyczy zaprogramowania ruchów komputera - postawiłem na algorytm minimax, zaimplementowałem go, jednak program mi się zapętla. Chodzi tutaj o funkcje minimax oraz ruch_przeciwnika, gdzieś w tych funkcjach jest problem, jednak od dłuższego czasu nie mogę dojść co jest nie tak ...
Z góry dziękuję za wszelkie wskazówki.

#include<iostream>
#include <cstdlib>
#include <ctime>
#include<cmath>
#include <conio.h>
#include<limits>
#include<windows.h>

using namespace std;

void reset_stream()
{
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
}

char **alokuj(int rozmiar1, int rozmiar2)
{
    char **tablica;
    tablica=new char*[rozmiar1];
    for(int i=1; i<=rozmiar1; i++) tablica[i]=new char[rozmiar2];
    return(tablica);
}

void **dealokuj(char **tab, int rozmiar)
{
    for(int i=1; i<=rozmiar; i++){
        delete tab[i];
    }
    delete[] tab;
}

void wypisz(char **tab, int n){

    system("cls");
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout << tab[i][j] << " ";
        }
        cout << endl;
        cout << endl;
    }
}

int sprawdz(char **tab, int n){
    unsigned int i, j;
    int s=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tab[i][j]!='_')
            s+=1;
        }
    }
    return s;
}

bool czy_wygrana(char **tab, int n, bool cisza){
    int t=0,r=0,w=0,p=0;
    bool e=false;
    for(int i=1; i<=n; i++){
        if(tab[i][1]!='_'){
            for(int j=1; j<=n-1; j++){
                if(tab[i][j]==tab[i][j+1]){
                t+=1;
                }
            }
        }
        if(tab[1][i]!='_'){
            for(int j=1; j<=n-1; j++){
                if(tab[j][i]==tab[j+1][i]){
                r+=1;
                }
            }
        }
        if(t==n-1 || r==n-1){
            cout << "wygrana" << endl;
            //return 1;
            e=true;
        }
        t=0;
        r=0;
    }
    for(int i=1; i<=n-1; i++){
        if(tab[1][1]!='_'){
            if(tab[i][i]==tab[i+1][i+1]){
                w+=1;
            }
        }
    }
    if(w==n-1){
        cout << "wygrana" << endl;
        //return 1;
        e=true;
    }
    for(int i=1; i<=n-1; i++){
        if(tab[1][n]!='_'){
            if(tab[i][n-(i-1)]==tab[i+1][n-i]){
            p+=1;
            }
        }
    }
    if(p==n-1){
        cout << "wygrana" << endl;
        //return 1;
        e=true;
    }
    if(!cisza)
    return 0;
    else return e;
}

bool remis(char **tab, int n)
{
     for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(tab[i][j]='_')
            return false;
        }
    }
  return true;
}

char wybor_pionka(char **tab, int n){
    cout << "Wybierz krzyzyk 'X' badz kolko 'O' ..." << endl;
    string znak;
    cin >> znak;
    while(znak!="X" && znak!="O"){
        cout << "Wybrano niewlasciwy symbol, powtorz: \n" << endl;
        cin >> znak;
    }
    return znak[0];
}

int minimax(char **tab, int n, char gracz)
{
    int m, mmx;
    if(czy_wygrana(tab, n,true)) return (gracz == 'O') ? 1 : -1;
    if(remis(tab, n)) return 0;
    gracz = (gracz == 'O') ? 'X' : 'O';
    mmx = (gracz == 'X') ? n*n+1 : -n*n-1;
    for(int i=1; i<=n; i++){
        for(int j=1; i<=n; j++){
            if(tab[i][j] == '_')
            {
                tab[i][j] = gracz;
                m = minimax(tab, n, gracz);
                tab[i][j] = '_';
                if(((gracz == 'X') && (m <= mmx)) || ((gracz == 'O') && (m >= mmx))) mmx = m;
            }
        }
   }
  return mmx;
}

void ruch_przeciwnika(char **tab, int n)
{
int m, mmx,t,r;

  mmx = -n*n-1;
  for(int i=1; i <= n; i++){
    for(int j=1; j <= n; j++){
        if(tab[i][j] == '_')
        {
            tab[i][j] = 'O';
            m = minimax(tab, n, 'O');
            tab[i][j] = '_';
            if(m > mmx){
                mmx = m;
                t=i;
                r=j;
            }
        }
    }
  }
    tab[t][r]='O';
}
//    int k, l;
//    srand(time(NULL));
//
//    k=rand()%n;
//    l=rand()%n;
//
//    if(tablica[k][l]=='_')
//    tablica[k][l]='O';
//
//
//    Sleep(500); cout<<".";
//    Sleep(500); cout<<".";
//    Sleep(500); cout<<".";

void k_funkcja(char **tab, int n){
    unsigned int i, j;
    int s=0;
    wypisz(tab,n);
    while(s<n*n){
        if(s%2==0){
            cin >> i >> j;
            while(!(cin)){
                cout << "Ponado niewlasciwe wspolrzedne!" << endl;
                cin.clear();
                cin.sync();
                cin >> i >> j;
            }
            while((tab[i][j]!='_') || (i>n) || (j>n)){
                cout << "Ponado niewlasciwe wspolrzedne!" << endl;
                cin >> i >> j;
//                if(!(cin)){
//                cin.clear();
//                cin.sync();
//                }
            }
            tab[i][j]='X';
        }
        else
        ruch_przeciwnika(tab,n);

        s=sprawdz(tab,n);
        wypisz(tab,n);
        if(czy_wygrana(tab,n,true)==1){
            break;
        }
        else if(s==n*n)
        cout << "Remis!\n";
    }
}

void u_funkcja(char **tab, int n){
    unsigned int i, j;
    int s=0;
    char znak[2];
    znak[0]='O';
    znak[1]='O';
    znak[0]=wybor_pionka(tab,n);
    if(znak[0]=='O')
        znak[1]='X';
    wypisz(tab,n);
    while(s<n*n){
    cin >> i >> j;
                while(cin.fail()){
                reset_stream();
                cout << "Ponado niewlasciwe wspolrzedne!" << endl;
                //cin.clear();
                //cin.sync();
                cin >> i >> j;
            }
        while(tab[i][j]!='_' || i<1 || i>n || j<1 || j>n){
            cout << "Ponado niewlasciwe wspolrzedne!" << endl;
            cin >> i >> j;
//            if(!(cin)){
//            cin.clear();
//            cin.sync();
//            }
        }
        if(s%2==0)
            tab[i][j]=znak[0];
        else
            tab[i][j]=znak[1];

        s=sprawdz(tab,n);
        wypisz(tab,n);
        if(czy_wygrana(tab,n,true)==1){
            break;
        }
        else if(s==n*n)
            cout << "Remis!\n";
    }
}

void menu(){
    cout << "1 - Graj" << endl;
    cout << "2 - Wybierz rodzaj gry (uzytkownik-uzytkownik/uzytkownik-komputer)" << endl;
    cout << "3 - Zobacz ranking" << endl;
    cout << "4 - Zakoncz gre" << endl;
}

bool rodzaje(int n){
    bool rodzaj=true;
    cout << "1.Gra typu uzytkownik-uzytkownik (1)" << endl;
    cout << "1.Gra typu uzytkownik-komputer (2)" << endl;
    cin >> n;
    if(n==2)
    rodzaj=false;
    return rodzaj;
}

int main(){
    int i, j, n;
    while(true){
        menu();
        int opcja;
        bool rodzaj1;
        cin >> opcja;
        switch(opcja){
        case 1:
            {
                    cout << "Podaj rozmiar planszy: " << endl;
                    cin >> n;
                    char **tab=alokuj(n,n);
                    for(int i=1; i<=n; i++){
                        for(int j=1; j<=n; j++){
                            tab[i][j]='_';
                        }
                    }
                    if(rodzaj1==true)
                    u_funkcja(tab,n);
                    else
                    k_funkcja(tab,n);
            }
            break;
        case 2:
            {
                    rodzaj1=rodzaje(n);
            }
            break;
        case 3:
            break;
        case 4:
            {
                cout << "Koncze dzialanie programu" << endl;
                return 0;
            }
        default:
            break;

        }
   }
   for(; getch() != 27; );
    return 0;
}
0

Co mówi debugger?

Btw, na pierwszy rzut oka z całą pewnością masz błąd off by one w funkcji alokuj.

0

Debugger nic nie mówi, bo program się normalnie kompiluje i uruchamia, jak w menu wybiorę opcję, że chcę grać z komputerem, wpiszę pierwszy symbol (krzyżyk) to wówczas powinien być ruch komputera, jednak w tym momencie program przestaje działać - wyświetla się komunikat "program przestał działać ..." i tyle. Jak dałem jakiegoś "couta" z przykładowym napisem, żeby zobaczyć czy w tym miejscu w ogóle coś wydrukuje, to po prostu się zapętla - drukuje dany napis w nieskończoność. Jaki błąd w funkcji alokuj? Ogólnie, zanim zacząłem kombinować z dodaniem tego algorytmu minimax, program działał dobrze, również alokacja pamięci ...

0

Debugger nic nie mówi, bo program się normalnie kompiluje i uruchamia

Jesteś oczywiście świadom tego, że debuggerem możesz, za pomocą breakpointów, także sprawdzać to, co się dzieje podczas wykonywania programu, tak? Po to właśnie on powstał. I nie ma nic wspólnego z kompilacją kodu.

Jak dałem jakiegoś "couta" z przykładowym napisem (...)

Użyj debuggera.

Jaki błąd w funkcji alokuj?

Podpowiedź: pisząc int* tab = new int[n]; tworzysz tablicę o n elementach mającą indeksy 0, 1, 2, 3, (...), n-1. A spójrz teraz na licznik swojej pętli.

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