TicTacToe с алгоритмом MiniMax 4x4 - PullRequest
Новая
       45

TicTacToe с алгоритмом MiniMax 4x4

3 голосов
/ 08 января 2020

Может кто-нибудь сказать, почему программа TicTacToe застревает, когда дело доходит до оборота процессора в таблице 4x4?

Когда я играю в версию 3x3, она работает правильно, я играю, затем CPU играет, даже старается изо всех сил, чтобы выиграть. Но когда я играю за столом 4х4, я могу играть, но когда наступает очередь процессора, программа почему-то зависает. Я пытался отладить, но это занимает слишком много времени, так много циклов, я не могу найти проблему. 

#include<iostream>
#include<limits>
using namespace std;

int index1,tablechoice=1,board_size=1;
char* board= new char[board_size];

int isFull()
{
    for(int i =0; i<board_size; i++)
    {
        if(board[i]!='X' && board[i]!='O')
        {
            return 0;
        }
    }
    return 1;
}

int user_won()
{
    if(tablechoice==1)
    {
        for(int i=0; i<9; i+=3)
        {
            if((board[i]==board[i+1])&&(board[i+1]==board[i+2])&&(board[i]=='X'))
                return 1;
        } //checking horizontally
        for(int i=0; i<3; i++)
        {
            if((board[i]==board[i+3])&&(board[i+3]==board[i+6])&&(board[i]=='X'))
                return 1;
        } // checking vertically
        if((board[0]==board[4])&&(board[4]==board[8])&&(board[0]=='X'))
        {
            return 1;
        } //checking diagonal
        if((board[2]==board[4])&&(board[4]==board[6])&&(board[2]=='X'))
        {
            return 1;
        } //checking diagonal
        return 0;
    }
    if(tablechoice==2)
    {
        for(int i=0; i<16; i+=4)
        {
            if((board[i]==board[i+1])&&(board[i+1]==board[i+2])&&(board[i]=='X'))
                return 1;
        } //checking horizontally
        for(int i=0; i<4; i++)
        {
            if((board[i]==board[i+4])&&(board[i+4]==board[i+8])&&(board[i]=='X'))
                return 1;
        } // checking vertically
        if((board[0]==board[5])&&(board[5]==board[10])&&(board[10]==board[15])&&(board[0]=='X'))
        {
            return 1;
        } //checking diagonal
        if((board[3]==board[6])&&(board[6]==board[9])&&(board[9]==board[12])&&(board[3]=='X'))
        {
            return 1;
        } //checking diagonal
    }
}

int cpu_won()
{
    if(tablechoice==1)
    {
        for(int i=0; i<9; i+=3)
        {
            if((board[i]==board[i+1])&&(board[i+1]==board[i+2])&&(board[i]=='O'))
                return 1;
        } //checking horizontally
        for(int i=0; i<3; i++)
        {
            if((board[i]==board[i+3])&&(board[i+3]==board[i+6])&&(board[i]=='O'))
                return 1;
        } // checking vertically
        if((board[0]==board[4])&&(board[4]==board[8])&&(board[0]=='O'))
        {
            return 1;
        } //checking diagonal
        if((board[2]==board[4])&&(board[4]==board[6])&&(board[2]=='O'))
        {
            return 1;
        } //checking diagonal
        return 0;
    }
    if(tablechoice==2)
    {
        for(int i=0; i<16; i+=4)
        {
            if((board[i]==board[i+1])&&(board[i+1]==board[i+2])&&(board[i]=='O'))
                return 1;
        } //checking horizontally
        for(int i=0; i<4; i++)
        {
            if((board[i]==board[i+4])&&(board[i+4]==board[i+8])&&(board[i]=='O'))
                return 1;
        } // checking vertically
        if((board[0]==board[5])&&(board[5]==board[10])&&(board[10]==board[15])&&(board[0]=='O'))
        {
            return 1;
        } //checking diagonal
        if((board[3]==board[6])&&(board[6]==board[9])&&(board[9]==board[12])&&(board[3]=='O'))
        {
            return 1;
        } //checking diagonal
        return 0;
    }
}

void displayBoard()
{
    if(tablechoice==1)
    {
        cout<<"\n-----------------------------TIC TAC TOE------------------------------";
        cout<<"                 ### Created by Fuad Shahmuradov ###";
        cout<<"\n\n\n\n[1][2][3]\n"
            <<"[4][5][6]\n"
            <<"[7][8][9]\n";
        cout<<"\t\t-------------\n"
            <<"\t\t| "<<board[0]<<" | "<<board[1]<<" | "<<board[2]<<" |\n"
            <<"\t\t-------------\n"
            <<"\t\t| "<<board[3]<<" | "<<board[4]<<" | "<<board[5]<<" |\n"
            <<"\t\t-------------\n"
            <<"\t\t| "<<board[6]<<" | "<<board[7]<<" | "<<board[8]<<" |\n"
            <<"\t\t-------------\n";
    }
    if(tablechoice==2)
    {
        cout<<"\n-----------------------------TIC TAC TOE------------------------------";
        cout<<"                 ### Created by Fuad Shahmuradov ###";
        cout<<"\n[1 ][2 ][3 ][4 ]\n"
              <<"[5 ][6 ][7 ][8 ]\n"
              <<"[9 ][10][11][12]\n"
              <<"[13][14][15][16]\n";
        cout<<"\t\t-----------------\n"
            <<"\t\t| "<<board[0]<<" | "<<board[1]<<" | "<<board[2]<<" | "<<board[3]<<" | \n"
            <<"\t\t-----------------\n"
            <<"\t\t| "<<board[4]<<" | "<<board[5]<<" | "<<board[6]<<" | "<<board[7]<<" | \n"
            <<"\t\t-----------------\n"
            <<"\t\t| "<<board[8]<<" | "<<board[9]<<" | "<<board[10]<<" | "<<board[11]<<" | \n"
            <<"\t\t-----------------\n"
            <<"\t\t| "<<board[12]<<" | "<<board[13]<<" | "<<board[14]<<" | "<<board[15]<<" | \n"
            <<"\t\t-----------------\n";
    }
    else return;
}

int minimax(bool flag)
{
    int max_val=-1000, min_val=1000;
    int i,j,value=1;
    if (cpu_won() == 1)
    {
        return 10;
    }
    else if (user_won() == 1)
    {
        return -10;
    }
    else if (isFull() == 1)
    {
        return 0;
    }
    int score[board_size];
    for(int i=0;i<board_size;i++)
    {
        score[i]=1; //if score[i]=1 then it is empty
    }
    for(i=0; i<board_size; i++)
    {
        if(board[i] == ' ')
        {
            if(min_val>max_val)
            {
                if(flag == true)
                {
                    board[i] = 'O';
                    value = minimax(false);
                }
                else
                {
                    board[i] = 'X';
                    value = minimax(true);
                }
                board[i] = ' ';
                score[i] = value;
            }
        }
    }
    if(flag == true)
    {
        max_val = -1000;
        for(j=0; j<board_size; j++)
        {
            if(score[j] > max_val && score[j] != 1)
            {
                max_val = score[j];
                index1 = j;
            }
        }
        return max_val;
    }
    if(flag == false)
    {
        min_val = 1000;
        for(j=0; j<board_size; j++)
        {
            if(score[j] < min_val && score[j] != 1)
            {
                min_val = score[j];
                index1 = j;
            }
        }
        return min_val;
    }
}

void playGame()
{
        for(int i=0;i<board_size;i++)
        {
            board[i]=' ';
        }
        int player,choice;
        cout<<endl<<"\nUSER--->(X)      CPU------>(O)";
        cout<<endl<<"\nSELECT:\n1-> Player first \n2-> CPU first\t\t";
        cin>>choice;
        cout<<"\n\n";
        if(choice==1)
        {
            displayBoard();
            up:cout<<endl<<"Enter your move: ";
            cin>>player;
            if(board[player-1]==' '&& cin)
            {
                board[player-1] = 'X';
                displayBoard();
            }
            else
            {
                cin.clear();
                cin.ignore(numeric_limits<streamsize>::max(), '\n');
                cout<<endl<<"Invalid move. Try different one.";
                goto up;
            }
        }
        while(true)
        {
            minimax(true);
            board[index1] = 'O';
            displayBoard();
            if(cpu_won()==1)
            {
                cout<<endl<<"CPU won!\n\n";
                break;
            }
            if(isFull()==1)
            {
                cout<<endl<<"Tie!\n\n";
                break;
            }
            again:cout<<endl<<"Enter your move: ";
            cin>>player;
            if(board[player-1]==' ')
            {
                board[player-1] = 'X';
                displayBoard();
            }
            else
            {
                cout<<endl<<"Invalid move. Try different one!\n";
                goto again;
            }
            if(user_won()==1)
            {
                cout<<endl<<"You won!\n\n";
                break;
            }
            if(isFull() == 1)
            {
                cout<<endl<<"Tie!\n\n";
                break;
            }
        }
}
int main()
{
    cout<<"-----------------------------TIC TAC TOE------------------------------";
    cout<<"                 ### Created by Fuad Shahmuradov ###";
    while(1)
    {
        cout<<endl<<"\nSelect game mode:\n1-> 3X3 \n2-> 4X4\t\t\t";
        cin>>tablechoice;
        while(tablechoice==1 || tablechoice ==2)
        {
            if(tablechoice==1)
            {
                board_size=9;
                playGame();
                return 0;
            }
            if(tablechoice==2)
            {
                board_size=16;
                playGame();
                return 0;
            }
        }
    }
}

. , , .

1 Ответ

2 голосов
/ 08 января 2020

Вы установили board_size путь вниз main. Но board уже выделено в то время. Вам нужно выделить board после изменения board_size.

Кроме того, это очень странно: 

    cin>>tablechoice;
    while(tablechoice==1 || tablechoice ==2)

Какова цель этого while? Код внутри него ничего не сделает, если tablechoice не равно 1 или 2. И каждый путь кода внутри него возвращается, поэтому он никогда не будет l oop.

...