Problem creating minimax in chess game

I'm coding a chess game in pure C only. The game itself is ready, I have been trying for some time to develop the minimax algorithm. Currently the algorithm is almost ready, but it is not yet returning and I think the problem is 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;
}

Information additional people who asked to help me with the problem.

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 edges serve only to guide the player from where to play, like a naval battle... A, B, C, D... it's 1, 2, 3, 4... etc.

Author: dfop02, 2018-05-22

1 answers

First of all you need to implement the position parser. He is the real intelligence of your game. The better you do it, the better the 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
}

As for the list I had talked about it 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 cleaning function, because in chess the amount of nodes that your minimax will run is not little. Since he does not perform the "pruning", he went through all the nodes. So you should analyze at least 3 or 4 million from us in a depth search 5. After the sixth turn this should go well beyond, 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 rework 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;
    }
}
 1
Author: Christian Beregula, 2018-05-25 04:37:11