Minimax para o Jogo Conecta 4

[Matheus Weber_691620]

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)

[welber91]

O que você já fez até agora?

[Matheus Weber_691620]

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 2 a 2, 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é?

[Nayuugga]

Pensando no tabuleiro, como uma matriz 7x6 temos:

#define NENHUM_GANHOU 0#define VERMELHO_GANHOU 1#define AMARELO_GANHOU 2int tabuleiro[7, 6]; //0-NENHUM 1-VERMELHO 2-AMARELOint VerificarGanhador(){     //Todos os return abaixo retornarão valores de acordo com os defines acima.     //Verificação de linhas horizontais.     for (int j = 0; j < 7; j++)         for (int i = 0; i < 3; i++)             if (tabuleiro[j, i] == tabuleiro[j, i + 1] &&                 tabuleiro[j, i] == tabuleiro[j, i + 2] &&                   tabuleiro[j, i] == tabuleiro[j, i + 3])                     if (tabuleiro[j, i] != 0)                          return (tabuleiro[j, i]);     //Verificação de linhas verticais.     for (int j = 0; j < 6; j++)         for (int i = 0; i < 4; i++)             if (tabuleiro[i, j] == tabuleiro[i + 1, j] &&                 tabuleiro[i, j] == tabuleiro[i + 2, j] &&                   tabuleiro[i, j] == tabuleiro[i + 3, j])                     if (tabuleiro[i, j] != 0)                        return (tabuleiro[i, j]);     //Verificação da diagonal.      for (int j = 3; j < 6; j++)         for (int i = 0; i < 4; i++)             if (tabuleiro[j, i] == tabuleiro[j - 1, i + 1] &&                 tabuleiro[j, i] == tabuleiro[j - 2, i + 2] &&                 tabuleiro[j, i] == tabuleiro[j - 3, i + 3])                   if (tabuleiro[j, i] != 0)                        return (tabuleiro[j, i]);     //Verificação da diagonal inversa.     for (int j = 0; j < 3; j++)         for (int i = 0; i < 4; i++)             if (tabuleiro[j, i] == tabuleiro[j + 1, i + 1] &&                 tabuleiro[j, i] == tabuleiro[j + 2, i + 2] &&                 tabuleiro[j, i] == tabuleiro[j + 3, i + 3])                    if (tabuleiro[j, i] != 0)                         return tabuleiro[j, i];          return NENHUM_GANHOU;}