Recursiveness - Why am I entering a loop?

Asked

Viewed 113 times

1

I’m trying to implement an algorithm called Minimax, but I’m finding problems in effecting its recursion, it goes into a loop that I can’t identify why. The depth of the algorithm should vary according to the moves that are tested, but the depth that occurs is: 5, 4, 3, 2, 1, 0, 0, 0, 0, ... It should return and go out of depth 0, back to 1, and so on, but persists at 0.

By default the initial depth will always be 5. The function verificar_jogadas_possiveis() serves to create a chained list with all possible player moves passed as parameter.

Jogadas *minimax(int tabuleiro[TAM][TAM], int depth, int Player, Jogadas* novaJogada){
    //Fiz esse trecho apenas para checar se o loop persiste
    printf("%d\n", depth);
    Sleep(100);
    // 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(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;
    }
}

Somebody help me figure out the mistake?

  • I don’t think this is an error. It’s just because there are several moves in sequence at depth 0; Have it show which move it is making.

  • But he never leaves zero depth, besides the fact that there are several in sequence, still he should finish the girl q will zeroing the depth and go checking the others. I’ll see which move gets stuck when it comes back

  • I found that actually, it works yes!! But unfortunately it takes about 25 seconds for him to answer... Completely unviable, q there is a way to "simplify" this code to require less processing?

  • Looking for minimax com poda

  • Another option is to redo the structure of what your chess structs look like, to optimize the methods of generating possible moves, which from what I can see are one of the great consumers of your chess time.

No answers

Browser other questions tagged

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