Problem creating Minimax in chess game

Asked

Viewed 274 times

0

I am coding a chess game only in pure C. The game itself is ready, I am for some time trying to develop the algorithm of Minimax. Currently the algorithm is almost ready, but it is not returning and I think the problem is in the function of Minimax.

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 you requested 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 matrix 10x10 where the edges serve only to guide the player from where to play, as a naval battle... A, B, C, D... and 1, 2, 3, 4... etc.

c algorithm games artificial-intelligence

  • "It fails and closes"... What mistake?

  • Apparently it enters a loop, because even error does not appear any, it only says that the program is no longer responding.

  • Not entering the merit of the program semantics: the ending condition of the recursion minimax is returning a pointer of Jogadas without being initialized. Perhaps it would be returned NULL was it better? I just think.

  • A clear mistake is the size of the board for(int i = 0; i <=9; i++) should be i < 8. Put some logs inside that loop to find where you’re locking, looking so it gets tricky if you mean what’s going on.

  • 1

    Could you tell how deep your search goes? When I was in college I did a game of chess tbm, and since there was almost no optimization in the code and the position evaluation algorithm was extremely slow, if I put him to look for something deeper than 5, he would easily spend 15 minutes looking for a move.

  • The depth at first is 5 too. About for and other logical errors I have corrected, but is the structure itself of Minimax correct? It doesn’t work at all.

  • What the pointer prox of Jogadas does? Does it point to the next move, or to other possible moves in the same turn? Your for that calls recursion does not seem to make sense. The tmp What’s it for? Where does he check the current "score" to compare which is the best move? There’s a lot that doesn’t make sense yet. Posta sua struct Jogadas and the function verificar_jogadas_possiveis to see if it helps to understand some things.

  • I added the information you asked for. The Prox pointer points to the next move within the list of moves of the same player. The tmp there serves to get a pass through all the moves within the list of structs Moves, I can not do in a simpler way. The score is made based on who you kill in the simulation, pawn are 10 points, horse 30, etc...

  • take a look now if the code I got from some help.

  • I made all the modifications and the agr code seems to be more optimized, but I’m still in doubt about where "Play" should be. It still doesn’t work but I think we’re on the right track, I did some tests and it returns some moves but things have nothing unfortunately, I posted the current code to re-analyze.

  • You should not perform the moves on tabuleiro but rather in the copia. Before returning to novaJogada you must assign the value of the current position of the board to it. The free within its function verificar_jogadas_possiveis time or another will cause inexplicable errors, why go release a valid move. Now to play you just need to create a list of moves Lista_ia before calling Minimax, and passing one by one to him, and then choosing the best.

  • I fixed the part of performing the simulated move, and on the check_moves I already corrected, only n edited here on the site. Can you explain better the final part you said about making a new List_ia, or give an example? I feel we are close to finally solving.

  • I still haven’t been able to come up with a plausible test result despite countless attempts, someone else can help?

  • What exactly would it be Ainda não consegui chegar a um resultado plausivel?

  • The chosen moves are not yet good... he kills himself or plays badly, it seems even random despite my efforts =/

Show 10 more comments

1 answer

1


First of all you need to implement the position analyzer. It is the real intelligence of your game. The better you make 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 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 knots that your Minimax will run is not little. Since he did not perform the "pruning", he went through all of us. Then it should analyze at least 3 or 4 million nodes in a depth search 5. After the sixth round this should go well beyond, only falling at the end of 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 remade the minmax method to make sense with the start function. I believe 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;
    }
}

  • I have corrected the errors pointed out, but there is still something hindering its functioning. The possible moves returns a list of Plays struct with all possible moves with that board, from a player. The algorithm as a whole, looking at the psudocode I find on wikipedia, I can’t see any difference, only the adaptation for the game. This algorithm is kind of complicated to use, at least I’m feeling this difficulty. If you are available to talk more about the subject send me a text.

  • I made some changes, in the end I left a doubt, as I should call then the function? Only play = Start)?

  • Exactly, when the plays are bad/suicidal, that depends on your position analyzer. He is the one who will tell your Minimax what is the best move.

  • I don’t have this position analyzer, I calculate only the value of each piece and if it kills it wins this score, it was only until then that I was able to think, but still does not rotate, there is something wrong with Minimax I think. If you can add me to Discord or skype so I can answer some more questions, I’ll even show you the whole program, maybe it will help you understand if there are any errors.

  • To test, you can use this system to only count the points of each player. White pieces - Black pieces = Who is in the advantage. That would just be for testing. The moves would start to make some sense. But they’d still be pretty bad. Because the value of each piece varies depending on the situation/position, and if you simply give it a fixed value, it will almost always ignore good moves, by material advantage.

  • What other things could I analyze besides the eliminated piece? Do I need to say "ready" or already known moves and see if he recognizes it in one of the Minimax standards, for example? The code doesn’t work yet, but this weekend I will devote myself entirely to make it run. It must be some nonsense leaving you a loop.

  • The position of each piece, for example, a horse on A3 on almost every occasion is worse than C3. Then the horse on A3 would be worth -0.01; The bishop pair tends to be stronger than a pair of horses. So bishop’s pair +0.1; Performing the Roque on is often better than leaving the king standing in the middle of the board. King protected in the +0.1 corner; You need to look at the board and think, "Who’s winning? What led me to this conclusion?" Then implement this to your chess. Often the sum of the pieces is equal, but it is easy to identify that this in advantage.

  • Got it, I haven’t even been able to make the code run yet, I found out that Minimax is in a loop pq when it reaches the depth 0 it doesn’t end the function, I don’t know why, I’m trying to understand pq if there is the new Return.

Show 3 more comments

Browser other questions tagged c algorithm games artificial-intelligence

You are not signed in. Login or sign up in order to post.