Problem creating minimax in chess game

Question

Problem creating minimax in chess game

Navigation

#1 by (1 votes)

0

I am coding a chess set only in pure C. The game itself is done, I've been trying to develop the minimax algorithm for some time. Currently the algorithm is almost ready, but it is not yet returning and I think the problem lies in the minimax function.

Current code below, I tried to run it, but when the AI tries to play, simply the game ends, it appears to be a loop again, but I did not identify it.

// liberando o lixo acumulado
void LiberarMemoria(Lista_ia* root){
    Jogadas* next = root->head;
    while(next != NULL){
        Jogadas* tmp = next;
        next = next->prox;
        free(tmp);
    }
    free(root);
}

// Simulate 5 turn ahead for choose the best current move
Jogadas *minimax(int tabuleiro[TAM][TAM], int depth, int Player, Jogadas* novaJogada){

    // Copy the board for don't change it
    int i, j, copia[TAM][TAM];
    for(i=0; i<=9; i++){
        for(j=0; j<=9; j++){
            copia[i][j] = tabuleiro[i][j];
        }
    }

    copia[novaJogada->lin_dps][novaJogada->col_dps] = copia[novaJogada->lin_atual][novaJogada->col_atual];
    copia[novaJogada->lin_atual][novaJogada->col_atual] = 0;

    if(gameover(tabuleiro) == 1){
        // Se o Player 2 (Computer) jogou e ganhou, agr seria a vez do player 1
        if (Player == 1){
            novaJogada->pontuacao = -99999;
            return novaJogada;
        }
        else{
            novaJogada->pontuacao = 99999;
            return novaJogada;
        }
    }

    if(depth == 0){
        return novaJogada;
    }

    Lista_ia *Moves = inicializarLista();

    verificar_jogadas_possiveis(copia, Moves, Player);

    Jogadas *tmp;

    // Simulating the current Player 2 (Computer) move
    if(Player == 2){
        novaJogada->pontuacao = -9999;

        for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox){

            Jogadas *BestMove = minimax(copia, depth - 1, 1, tmp);

            if(BestMove->pontuacao > novaJogada->pontuacao){
                novaJogada->pontuacao = BestMove->pontuacao;
            }
        }
        LiberarMemoria(Moves);
        return novaJogada;
    }
    // Simulating the best Player 1 move
    else{
        novaJogada->pontuacao = 9999;

        for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox){

            Jogadas *BestMove = minimax(copia, depth - 1, 2, tmp);

            if(BestMove->pontuacao < novaJogada->pontuacao){
                novaJogada->pontuacao = BestMove->pontuacao;
            }
        }
        LiberarMemoria(Moves);
        return novaJogada;
    }
}

Jogadas *IniciarMinMax(int tabuleiro[TAM][TAM], int depth, int Player){
    Lista_ia *Moves = inicializarLista();

    // Copy the board for don't change it
    int i, j, copia[TAM][TAM];
    for(i=0; i<=9; i++){
        for(j=0; j<=9; j++){
            copia[i][j] = tabuleiro[i][j];
        }
    }

    verificar_jogadas_possiveis(copia, Moves, Player);

    Jogadas* bestMove = NULL;
    Jogadas* tmp;

    for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox){
        // iniciando busca
        Jogadas *current = minimax(copia, depth, Player, tmp);
        if(bestMove == NULL || current->pontuacao > bestMove->pontuacao){
            bestMove = current;
        }
    }
    // clonando resultado para retornar antes de liberar a memoria
    Jogadas *result = (Jogadas*)malloc(sizeof(Jogadas));
    result->lin_atual = bestMove->lin_atual;
    result->col_atual = bestMove->col_atual;
    result->lin_dps = bestMove->lin_dps;
    result->col_dps = bestMove->col_dps;
    result->pontuacao = bestMove->pontuacao;

    LiberarMemoria(Moves);

    return result;
}

Additional information asked to help me with the issue.

typedef struct jogadas{
    int lin_atual;
    int col_atual;
    int lin_dps;
    int col_dps;
    int pontuacao;
    struct jogadas *prox;
}Jogadas;

typedef struct turno{
    int turn;
    struct turno *prox;
}Turno;

typedef struct lista_ia{
    struct jogadas *head;
}Lista_ia;

void verificar_jogadas_possiveis(int tabuleiro[TAM][TAM], Lista_ia *Allmoves, int Player){
    int i, j, m, n;
    Jogadas *tmp;
    for(i=1; i<9; i++){
        for(j=1; j<9; j++){
            if(checar_peca_inimiga(tabuleiro[i][j]) == Player){
                for(m=1; m<9; m++){
                    for(n=1; n<9; n++){
                        tmp = (Jogadas*)malloc(sizeof(Jogadas));
                        tmp->lin_atual = i;
                        tmp->col_atual = j;
                        tmp->lin_dps = m;
                        tmp->col_dps = n;
                        if(validar_jogada(tabuleiro, tmp) == 1){
                            //tmp->pontuacao += pontuar_jogadas(tabuleiro, m, n);
                            tmp->pontuacao = 0;
                            tmp->prox = Allmoves->head;
                            Allmoves->head = tmp;
                        }
                    }
                }
            }
        }
    }
    // Free memory space
    free(tmp);
}

NOTE: The for is correct, I had forgotten but the board is a 10x10 matrix where the borders serve only to guide the player from where to play, such as a naval battle ... A, B, C, D .. and 1, 2, 3, 4 ... etc.

c algoritmo jogos

asked by anonymous 22.05.2018 / 04:22

1 answer

Leave the CSS centralized query update error

score 1 · Accepted Answer

First of all you need to implement the position analyzer. He is the real intelligence of your game. The better you do it, the better your decisions will be when making the move.

void ValorPosicaoEstatica(int[TAM][TAM] t, Jogadas* jogada)
{
    // calcular quem esta com vantagem e de quanto e atribuir em jogada
}

How much of the list I had spoken was something like this.

// função auxiliar para dar o start no MinMax
Jogadas* IniciarMinMax(int tabuleiro[TAM][TAM], int profundidade, int player)
{
    Lista_ia *Moves = (Lista_ia*)malloc(sizeof(Lista_ia));
    Moves->head = NULL;

    int x[TAM][TAM];
    for(i=0; i< TAM; i++)
    {
        for(j=0; j < TAM; j++)
        {
            x[i][j] = tabuleiro[i][j];
        }
    }
    verificar_jogadas_possiveis(x, Moves, player);
    Jogadas* bestMove = NULL;
    for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox)
    {
        // iniciando busca
        Jogadas *current = minimax(x, profundidade, player, tmp);
        if(bestMove == NULL || current->pontuacao > bestMove->pontuacao)
        {
            bestMove = current;
        }
    }
    // clonando resultado para retornar antes de liberar a memoria
    Jogadas *result = (Jogadas*)malloc(sizeof(Jogadas));
    result->lin_atual = bestMove->lin_atual;
    result->col_atual = bestMove->col_atual;
    result->lin_dps = bestMove->lin_dps;
    result->col_dps = bestMove->col_dps;
    result->pontuacao = bestMove->pontuacao;

    LiberarMemoria(Moves);

    return result;
}

I added a cleanup function because in chess the amount of knots that your minimax will run is not small. Since he does not perform the "pruning," he has traveled all nodes. Then you should analyze at least 3 or 4 million knots on a depth 5 quest. After the sixth turn this should go well, only falling at the end of the game.

// liberando o lixo acumulado
void LiberarMemoria(Lista_ia* root)
{
    Jogadas* next = root->head;
    while(next != NULL)
    {
        Jogadas* tmp = next;
        next = next->prox;
        free(tmp);
    }
    free(root);
}

And finally I re-mode the minmax method to make sense with the start function. I think it should be ok.

Jogadas *minimax(int tabuleiro[TAM][TAM], int depth, int Player, Jogadas* novaJogada)
{

    // Clona o tabuleiro e executa a jogada pedida
    int copia[TAM][TAM];
    for(i=0; i< TAM; i++)
    {
        for(j=0; j < TAM; j++)
        {
            copia[i][j] = tabuleiro[i][j];
        }
    }
    copia[jogada->lin_dps][jogada->col_dps] = copia[jogada->lin_atual][jogada->col_atual];
    copia[jogada->lin_atual][jogada->col_atual] = 0;

    if(gameover(copia))
    {
        // voce precisa dizer como o jogo acabou
        // se o computador ganhou novaJogada->pontuacao = 99999;
        // se o jogador ganhou novaJogada->pontuacao = -99999;
        // se empatou novaJogada->pontuacao = 0;
        return novaJogada;
    }


    // se a busca ja terminou só retorna o valor da jogada
    if(depth == 0)
    {
        // aqui voce precisa criar a função para o programa saber que valor dar 
        // a posição atual, de quem esta na vantagem e por quanto;
        ValorPosicaoEstatica(copia, novaJogada);
        return novaJogada;
    }

    Lista_ia *Moves = (Lista_ia*)malloc(sizeof(Lista_ia));
    Moves->head = NULL;

    verificar_jogadas_possiveis(copia, Moves, Player);

    Jogadas *tmp;

    if(Player == 2)
    {
        novaJogada->pontuacao = -9999;
        for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox)
        {
            Jogadas *BestMove = minimax(copia, depth - 1, 1, tmp);
            if(BestMove->pontuacao > novaJogada->pontuacao)
            {
                novaJogada->pontuacao = BestMove->pontuacao;
            }
        }
        LiberarMemoria(Moves);
        return novaJogada;
    }
    else
    {
        novaJogada->pontuacao = 9999;
        for(tmp = Moves->head; tmp != NULL; tmp = tmp->prox)
        {
            Jogadas *BestMove = minimax(copia, depth - 1, 2, tmp);
            if(BestMove->pontuacao < novaJogada->pontuacao)
            {
                novaJogada->pontuacao = BestMove->pontuacao;
            }
        }
        LiberarMemoria(Moves);
        return novaJogada;
    }
}