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.
– Christian Beregula
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
– dfop02
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?
– dfop02
Looking for
minimax com poda– Christian Beregula
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.
– Christian Beregula