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