0

Estou codificando um jogo de xadrez apenas no C puro. O jogo em si está pronto, estou a algum tempo tentando desenvolver o algoritmo de minimax. Atualmente o algoritmo está quase pronto, porém ainda não está retornando e eu acho que o problema está na função do minimax.

Atual código abaixo, eu tentei rodar ele, mas quando a IA tenta jogar, simplesmente o jogo termina, aparenta ser um loop novamente, mas não identifiquei ele.

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

Informações adicionais que pediram para me ajudarem no problema.

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

OBS: o for está correto, eu havia me esquecido mas o tabuleiro é uma matriz 10x10 onde as bordas servem apenas para orientar o jogador de onde jogar, como uma batalha naval... A, B, C, D... e 1, 2, 3, 4... etc.

15
  • "Ele da erro e fecha"... Qual erro? 22/05/2018 às 2:30
  • Aparentemente ele entra em um loop, pois erro mesmo não aparece nenhum, ele só diz que o programa não está mais respondendo.
    – dfop02
    22/05/2018 às 3:10
  • Não entrando no mérito da semântica do programa: a condição de terminação da recursão de minimax está retornando um ponteiro de Jogadas sem estar inicializado. Talvez se retornasse NULL fosse melhor? Só acho. 22/05/2018 às 20:03
  • Um erro claro é o tamanho do tabuleiro for(int i = 0; i <=9; i++) deveria ser i < 8. Coloca alguns logs dentro desses loop para achar onde esta travando, olhando assim fica complicado se quer dizer o que esta acontecendo. 22/05/2018 às 20:34
  • 1
    Poderia dizer a qual profundidade sua busca vai? Quando estava na faculdade fiz um jogo de xadrez tbm, e como quase não existia otimização no código e o algoritmo de avaliação de posição era extremamente lento, se colocasse ele pra procurar qualquer coisa mais funda do que 5, ele facilmente passava de 15 minuto buscando uma jogada. 22/05/2018 às 20:42

1 Resposta 1

1

Primeiro de tudo você precisa implementar o analisador de posição. Ele é a real inteligência do seu jogo. Quanto melhor você fizer ele, melhor serão as decisões na hora de realizar a jogada.

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

Quanto a lista que eu tinha falado era algo assim.

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

Adicionei uma função de limpeza, porque no xadrez a quantidade de nós que seu minimax vai correr não é pouco. Como ele não realiza a "poda", ele percorrera todos os nós. Então deve analisar no mínimo 3 ou 4 milhão de nós em uma busca de profundidade 5. Após o sexto turno isso deve ir bem além, só caindo no final de jogo.

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

E por fim refiz o método minmax para fazer sentido com a função de start. Acredito que deve estar 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;
    }
}
8
  • Já corrigi os erros apontados, mas ainda há algo atrapalhando seu funcionamento. As jogadas_possiveis retorna uma lista de struct Jogadas com todas as jogadas possiveis com aquele tabuleiro, de um player. O algoritmo como um todo, olhando o psudocódigo que encontro na wikipedia, não consigo ver diferença, só a adaptação pro jogo. Esse algoritmo é meio complicado de se utilizar, pelo menos eu estou sentido essa dificuldade. Se estiver disponível para conversarmos mais sobre o assunto me mande uma msg.
    – dfop02
    23/05/2018 às 1:48
  • Eu fiz algumas alterações, no fim me sobrou uma duvida, como eu devo chamar então a função? Só jogar = IniciarMinimax(parametros)?
    – dfop02
    3/06/2018 às 19:12
  • Exatamente, quanto as jogadas serem ruins/suicidas, ai depende do seu analisador de posição. Ele é quem vai dizer pro seu minimax qual é a melhor jogada. 4/06/2018 às 14:01
  • Eu não tenho esse analisador de posição, eu calculo só o valor de cada peça e se matar ela ganha essa pontuação, foi só até ai que consegui pensar, mas ainda assim não roda, tem algo de errado no minimax eu acho. Se puder me add no discord ou skype pra eu poder tirar mais algumas duvidas, até lhe mostro o programa inteiro, talvez ajude a entender se há algum erro.
    – dfop02
    4/06/2018 às 19:08
  • Para vc testar, da para usar esse sistema de de somente contar os pontos de cada jogador. Peças Branco - Peças Preto = Quem esta na vantagem. Isso seria apenas para testar. As jogadas começariam a fazer algum sentido. Mas ainda estariam bem ruins. Porque o valor de cada peça varia dependendo da situação/posição, e se você simplesmente der um valor fixo a ele, ele quase sempre vai ignorar jogadas boas, pela vantagem material. 7/06/2018 às 1:38

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .