Algoritmo Minimax para Conecta 4

[bruxo]

Gente, pesquisei por muitos lugares, e não achei quase nada.

Gostaria de uma ajuda de como seria uma heuristica boa para o jogo Conecta4

E se alguém tem algum exemplo ou possa me dar uma mao para implementar um algoritmo desses.

Não sei se tá certo, mas eu acredito que o minimax possa ser implementado como uma BFS certo? E após chegar ao fundo maximo, eu retorno atualizando os valores dos nodos até chegar na raiz?

Se alguém tiver um exemplo em C, ou um pseudo-algoritmo decente eu agradeceria(não entendi nada daquele da wikipedia)

[Bob Joe]

Cara, eu tenho um exemplo de execução do minimax em um caderno meu da graduação, se eu achar aqui posto.

[bruxo]

Opa, valeu BoB

O que eu fiz até agora:

Criei o básico, inicialização da raíz, do tabuleiro, regra pra quando acaba, como joga.

Meu problema tá no conceito mesmo, implementar nunca é o difícil, o difícil é descobrir o que implementar hehe. E em pensar numa heuristica boa.

Eu criei uma heuristica que ele pesquisa todo tabuleiro em busca de 1's(ou 2).

Quando ele encontra o 1, ele procura verticalmente e horizontalmente(num raio 4) por outros 1's e soma, se encontrar um 2, ele descarta toda a soma.

No final essas somas darão o valor da heuristica, ficou meio difícil de explicar, mas aqui vai o código:

int calculaHeuristica(Tabuleiro *p,int minimax){
int i, j, valor, z, soma;
//1 é max
//2 é min
if(verificaVitoria(p)==minimax && minimax==1) return 9999;
if(verificaVitoria(p)==minimax && minimax==2) return -9999;
valor = 0;
for(i=0;i<7;i++){
for(j=0;j<10;j++){

if(j<=6){
soma =0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i][j+1]==minimax && z==0){
soma++;

}else if(p->tab[i][j+1]!=minimax && p->tab[i][j+1]!=0){
z++;
}

if(p->tab[i][j+2]==minimax && z==0){
soma++;
}else if(p->tab[i][j+2]!=minimax && p->tab[i][j+2]!=0){
z++;
}

if(p->tab[i][j+3]==minimax && z==0){
soma++;
}else if(p->tab[i][j+3]!=minimax && p->tab[i][j+3]!=0){
z++;
}

if(z==0){
valor = valor+soma;
//printf("hor - %d %d %d\n", valor, i, j);
}

}
if(i<=3){
soma = 0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i+1][j]==minimax && z==0){
soma++;

}else if(p->tab[i+1][j]!=minimax && p->tab[i+1][j]!=0){
z++;
}

if(p->tab[i+2][j]==minimax && z==0){
soma++;

}else if(p->tab[i+2][j]!=minimax && p->tab[i+2][j]!=0){
z++;
}

if(p->tab[i+3][j]==minimax && z==0){
soma++;

}else if(p->tab[i+3][j]!=minimax && p->tab[i+3][j]!=0){
z++;
}
if(z==0){
//printf("vert - %d %d %d\n", valor, i, j);
valor = valor+soma;
}
}




if(i-4>=0 && j+4<=9){
soma =0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i-1][j+1]==minimax && z==0){
soma++;

}else if(p->tab[i-1][j+1]!=minimax && p->tab[i-1][j+1]!=0){
z++;
}

if(p->tab[i-2][j+2]==minimax && z==0){
soma++;

}else if(p->tab[i-2][j+2]!=minimax && p->tab[i-2][j+2]!=0){
z++;
}

if(p->tab[i-3][j+3]==minimax && z==0){
soma++;

}else if(p->tab[i-3][j+3]!=minimax && p->tab[i-3][j+3]!=0){
z++;
}
if(z==0){
//printf("sup dir - %d %d %d\n", valor, i, j);
valor = valor+soma;
}
}

if(i-4>=0 && j-4>=0){
soma =0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i-1][j-1]==minimax && z==0){
soma++;

}else if(p->tab[i-1][j-1]!=minimax && p->tab[i-1][j-1]!=0){
z++;
}

if(p->tab[i-2][j-2]==minimax && z==0){
soma++;

}else if(p->tab[i-2][j-2]!=minimax && p->tab[i-2][j-2]!=0){
z++;
}

if(p->tab[i-3][j-3]==minimax && z==0){
soma++;

}else if(p->tab[i-3][j-3]!=minimax && p->tab[i-3][j-3]!=0){
z++;
}
if(z==0){
//printf("sup esq - %d %d %d\n", valor, i, j);
valor = valor+soma;
}
}

/*if(i+4<=7 && j-4>=0){
soma =0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i+1][j-1]==minimax && z==0){
soma++;

}else if(p->tab[i+1][j-1]!=minimax && p->tab[i+1][j-1]!=0){
z++;
}

if(p->tab[i+2][j-2]==minimax && z==0){
soma++;

}else if(p->tab[i+2][j-2]!=minimax && p->tab[i+2][j-2]!=0){
z++;
}

if(p->tab[i+3][j-3]==minimax && z==0){
soma++;

}else if(p->tab[i+3][j-3]!=minimax && p->tab[i+3][j-3]!=0){
z++;
}
if(z==0){
printf("inf esq - %d %d %d\n", valor, i, j);
valor = valor+soma;
}
}

if(i+4<=7 && j+4<=9){
soma =0;
z=0;
if(p->tab[i][j]==minimax && z==0){
soma++;

}else if(p->tab[i][j]!=minimax && p->tab[i][j]!=0){
z++;
}

if(p->tab[i+1][j+1]==minimax && z==0){
soma++;

}else if(p->tab[i+1][j+1]!=minimax && p->tab[i+1][j+1]!=0){
z++;
}

if(p->tab[i+2][j+2]==minimax && z==0){
soma++;

}else if(p->tab[i+2][j+2]!=minimax && p->tab[i+2][j+2]!=0){
z++;
}

if(p->tab[i+3][j+3]==minimax && z==0){
soma++;

}else if(p->tab[i+3][j+3]!=minimax && p->tab[i+3][j+3]!=0){
z++;
}
if(z==0){
printf("Inf dir - %d %d %d\n", valor, i, j);
valor = valor+soma;
}
}*/
}
}
if(minimax==2) return -valor;
return valor;
}

Tem uma parte comentada, porque percebi que não era necessário calcular o valor de duas diagonais iguais, visto que não tem direção.



Edit:

Olha o que eu pensei, não sei se o conceito tá certo.

Mas eu poderia implementar uma BFS, abrir todos os filhos até uma determinada profundidade, colocá-los num vetor, calcular o max e o min, comparar 7 a 7, e jogar o valor max e min para cima, até chegar no topo, não sei se o conceito tá certo, mas acho que é isso né?

Copiei e colei do outro forum que participo hehe

Melhor ainda, eu tenho uma busca iterativa já implementada, acho que vou transformar ela no minimax, será que tem como?