gustavoarcanjo

arrumei um pouco mais e resolvi os problemas com a função libera, mas ainda n sei como fazer para o computador calcular a jogada dele... alguém tem uma ideia? #include <stdio.h> #include <stdlib.h> #include <time.h> struct noh { char tabuleiro [3][3]; int jogada; struct noh *filho; struct noh *prox; }; typedef struct noh NOH; void caminhoMiniMax(NOH *pnd, NOH *pMelhor, int *pValor); void expandirNoh (NOH* p, int pNivel,int profund); void imprimeJogo(NOH *p); NOH* gerarListaNohs(NOH *p); NOH* constroiArvore(char tab[3][3],int nivelJog, int jogada); int avaliarPosicao(char tab[3][3]); int isXO(char c); int verLinhaColuna(char tab[3][3],int i, int j, char c); int verDiagonais(char tab[3][3],int i, int j, char c); void libera (NOH *pnd); int verVitoria(NOH *p); int main(){ int escolha; char tabuleiro[3][3]; int jogada, nivelJog; int i,j,k=0; int vitoria; NOH *n,*m; srand(time(NULL)); jogada=rand()%2;/*define quem começa, 1->computador 0->jogador*/ printf("Defina o nivel de dificuldade(0-8): "); scanf("%d",&nivelJog); while(nivelJog<0 || nivelJog>8){ printf("\ndificuldade invalida!\n"); printf("\nDefina o nivel de dificuldade(0-9):\n"); scanf("%d",&nivelJog); } n = constroiArvore(tabuleiro,nivelJog,jogada); for(i=0;i<3;i++){ for(j=0;j<3;j++){ n->tabuleiro[i][j]=' '; } } imprimeJogo(n); do{ if(jogada==0){ printf("\nDigite sua escolha(0-8):\n"); scanf("%d",&escolha); while(escolha<0 || escolha>8){ printf("\nPosicao invalida!\n"); printf("\nDigite sua escolha(0-8):\n"); scanf("%d",&escolha); } for(i=0;i<3;i++){ for(j=0;j<3;j++){ if((i*3+j)==escolha){ if(n->tabuleiro[i][j]==' '){ n->tabuleiro[i][j]='X'; jogada=1; }else{ printf("\nPosicao ja foi preenchida!\n"); jogada=0; } } } }jogada=1; }else{ printf("\nJogada do computador:\n"); /*parte incompleta*/ printf("o computador escolheu %d\n",escolha); for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(k==escolha){ if(n->tabuleiro[i][j]==' '){ n->tabuleiro[i][j]='O'; jogada=0; }else{ jogada=1; } } k++; } } k=0; vitoria = verVitoria(n); if(vitoria!=0){ imprimeJogo(n); printf("\n\nVoce perdeu!\n\n"); libera(n); system("PAUSE"); return 0; } } imprimeJogo(n); for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(n->tabuleiro[i][j]==' ') escolha=-1; } } }while(escolha==-1); printf("\n\nVelha!\n\n"); libera(n); system("PAUSE"); return 0; } void imprimeJogo(NOH *p){ int i,j; for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(isXO(p->tabuleiro[i][j])){ printf("%c ",p->tabuleiro[i][j]); }else printf("%d ",i*3+j); } printf("\n"); } } void caminhoMiniMax(NOH *pnd, NOH *pMelhor, int *pValor){ NOH *p, pMelhor2; int val; if (pnd->filho == NULL) { (*pValor) = avaliarPosicao(pnd->tabuleiro); pMelhor = pnd; } else{ p = pnd->filho; caminhoMiniMax(p,pMelhor, pValor); pMelhor = p; if (pnd->jogada == 1)/*se for a vez do computador*/ *pValor = -(*pValor); p = p->prox; while (p != NULL) { caminhoMiniMax(p,&pMelhor2, &val); if (pnd->jogada == 1){ val = -val; } if (val > *pValor) { *pValor = val; pMelhor = p; } p = p->prox; } if (pnd->jogada == 1){ *pValor = -(*pValor); } } } NOH* gerarListaNohs(NOH* p){ int i,j; int k,l; NOH *q; NOH *ant; NOH *primeiro;/*primeiro da lista*/ for(i=0;i<3;i++){ for(j=0;j<3;j++){/*for's para verificar onde ja foi jogado ou nao*/ if(p->tabuleiro[i][j]!='X'||p->tabuleiro[i][j]!='O'){ q =(NOH*) malloc(sizeof(NOH));/*cria o proxima possibilidade*/ q->jogada = (p->jogada==0)? 1:0; q->prox=NULL; for(k=0;k<3;k++)/*for para copiar o conteudo do atual para a prox possibilidade*/ for(l=0;l<3;l++) q->tabuleiro[k][l]=p->tabuleiro[k][l]; if(p->jogada==1){/*caso seja a vez do jogador*/ q->tabuleiro[i][j]='X'; }else{ /*caso seja a vez do computador*/ q->tabuleiro[i][j]='O'; } if((i+j)!=0){/*conecta a lista de nohs*/ ant->prox = q; }else{ primeiro=q; } ant = q; }/*fim do if*/ } }/*fim dos for's de verificacao*/ return primeiro; } int isXO(char c){ return (c=='X'||c=='O'); } int verLinhaColuna(char tab[3][3],int i, int j, char c){ int cont=0; if(tab[i][j]==c){ if(tab[i][(j+1)% 3]==c && tab[i][(j+2)%3]==c){/*verifica espaco na mesma linha*/ cont++; } if(tab[(i+1)%3][j]==c && tab[(i+2)%3][j]==c){/*verifica espaco na mesma coluna*/ cont++; } } return cont; } int verDiagonais(char tab[3][3],int i, int j, char c){ int cont=0; if(tab[i][j]==c){ /*verifica espaco na mesma diagonal da esquerda pra direita*/ if(tab[(i+1)%3][(j+1)%3]==c && tab[(i+2)%3][(j+2)%3]==c){ cont++; } /*verifica espaco na mesma diagonal da direita pra esquerda*/ if(tab[(i+1)%3][(j+2)%3]==c && tab[(i+2)%3][(j+1)%3]==c){ cont++; } } return cont; } int avaliarPosicao(char tab[3][3]){ char c,d; int cont1=0, cont2=0, result; c='X'; d='O'; /*verifica espacos para todas as combinacoes possiveis*/ cont1+=verDiagonais(tab,1,1,c); cont2+=verDiagonais(tab,1,1,d); cont1+=verLinhaColuna(tab,0,0,c); cont2+=verLinhaColuna(tab,0,0,d); cont1+=verLinhaColuna(tab,1,1,c); cont2+=verLinhaColuna(tab,1,1,d); cont1+=verLinhaColuna(tab,2,2,c); cont2+=verLinhaColuna(tab,2,2,d); result=cont1-cont2; return (result>=0)? result : -result; } NOH* constroiArvore(char tab[3][3],int nivelJog, int jogada){ int i,j; NOH *pArvore = (NOH *) malloc(sizeof(NOH)); printf("\nAguarde\n"); /*copia as informações do tabuleiro para o novo NOH*/ for (i=0; i<3; ++i) for (j=0; j<3; ++j) pArvore->tabuleiro[i][j] = tab[i][j]; /* copia as outra informações para o novo NOH*/ pArvore->jogada = jogada; pArvore->filho= NULL; pArvore->prox= NULL; /*expande o NOH para as suas possibilidades*/ expandirNoh (pArvore, 0, nivelJog); return pArvore; } void expandirNoh (NOH* p, int pNivel,int profund){ NOH *q; if (pNivel < profund) { q = gerarListaNohs(p); p->filho = q; while (q != NULL) { if (p->jogada == 1){ q->jogada= -1; }else q->jogada =1; q->filho=NULL; expandirNoh(q, pNivel+1, profund); q = q->prox; } } } void libera(NOH *pnd){ NOH *p; if (pnd->filho == NULL) { free(pnd); } else{ p = pnd->filho; libera(p); p = p->prox; while (p != NULL) { libera(p); p = p->prox; } } } int verVitoria(NOH *n){ int vitoria=0; vitoria = verDiagonais(n->tabuleiro,1,1,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n->tabuleiro,0,0,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n->tabuleiro,1,1,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n->tabuleiro,2,2,'O'); if(vitoria!=0) return 1; return 0; } Aguardo resposta.

O programa é um jogo da velha utilizando árvores. Estou precisando de ajuda na parte em que o computador escolhe a sua jogada baseado na função MiniMax... E tem alguma coisa errada na função que libera a árvore, por isso deixei ela como comentário. #include <stdio.h> #include <stdlib.h> #include <time.h> struct noh { char tabuleiro [3][3]; int jogada; struct noh *filho; struct noh *prox; }; typedef struct noh NOH; void caminhoMiniMax(NOH *pnd, NOH *pMelhor, int *pValor); void expandirNoh (NOH* p, int pNivel,int profund); void imprimeJogo(NOH p); NOH* gerarListaNohs(NOH p); NOH constroiArvore(char tab[3][3],int nivelJog, int jogada); int avaliarPosicao(char tab[3][3]); int isXO(char c); int verLinhaColuna(char tab[3][3],int i, int j, char c); int verDiagonais(char tab[3][3],int i, int j, char c); void libera (NOH *pnd); int verVitoria(NOH p); int main(){ int escolha; char tabuleiro[3][3]; int jogada, nivelJog; int i,j,k=0; int vitoria; NOH n,*m; srand(time(NULL)); jogada=rand()%2;/*define quem começa, 1->computador 0->jogador*/ printf("Defina o nivel de dificuldade(0-8): "); scanf("%d",&nivelJog); while(nivelJog<0 || nivelJog>8){ printf("\ndificuldade invalida!\n"); printf("\nDefina o nivel de dificuldade(0-9):\n"); scanf("%d",&nivelJog); } for(i=0;i<3;i++){ for(j=0;j<3;j++){ tabuleiro[i][j]=' '; } } n = constroiArvore(tabuleiro,nivelJog,jogada); imprimeJogo(n); do{ if(jogada==0){ printf("\nDigite sua escolha(0-8):\n"); scanf("%d",&escolha); while(escolha<0 || escolha>8){ printf("\nPosicao invalida!\n"); printf("\nDigite sua escolha(0-8):\n"); scanf("%d",&escolha); } for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(k==escolha){ if(n.tabuleiro[i][j]==' '){ n.tabuleiro[i][j]='X'; jogada=1; }else{ printf("\nPosicao ja foi preenchida!\n"); jogada=0; } } k++; } } k=0; }else{ printf("\nJogada do computador:\n"); /*parte incompleta*/ vitoria = verVitoria(n); if(vitoria!=0){ imprimeJogo(n); printf("\n\nVoce perdeu!\n\n"); //libera(n); system("PAUSE"); return 0; } jogada=0; } imprimeJogo(n); for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(n.tabuleiro[i][j]==' ') escolha=-1; } } }while(escolha==-1); printf("\n\nVelha!\n\n"); //libera(n); system("PAUSE"); return 0; } void imprimeJogo(NOH p){ int i,j; for(i=0;i<3;i++){ for(j=0;j<3;j++){ if(isXO(p.tabuleiro[i][j])){ printf("%c ",p.tabuleiro[i][j]); }else printf("%d ",i*3+j); } printf("\n"); } } void caminhoMiniMax(NOH *pnd, NOH *pMelhor, int *pValor){ NOH *p, pMelhor2; int val; if (pnd->filho == NULL) { (*pValor) = avaliarPosicao(pnd->tabuleiro); pMelhor = pnd; } else{ p = pnd->filho; caminhoMiniMax(p,pMelhor, pValor); pMelhor = p; if (pnd->jogada == 1)/*se for a vez do computador*/ *pValor = -(*pValor); p = p->prox; while (p != NULL) { caminhoMiniMax(p,&pMelhor2, &val); if (pnd->jogada == 1){ val = -val; } if (val > *pValor) { *pValor = val; pMelhor = p; } p = p->prox; } if (pnd->jogada == 1){ *pValor = -(*pValor); } } } NOH* gerarListaNohs(NOH p){ int i,j; int k,l; NOH *q; NOH *ant; NOH *primeiro;/*primeiro da lista*/ for(i=0;i<3;i++){ for(j=0;j<3;j++){/*for's para verificar onde ja foi jogado ou nao*/ if(p.tabuleiro[i][j]!='X'||p.tabuleiro[i][j]!='O'){ q =(NOH*) malloc(sizeof(NOH));/*cria o proxima possibilidade*/ q->jogada = (p.jogada==0)? 1:0; q->prox=NULL; for(k=0;k<3;k++)/*for para copiar o conteudo do atual para a prox possibilidade*/ for(l=0;l<3;l++) q->tabuleiro[k][l]=p.tabuleiro[k][l]; if(p.jogada==1){/*caso seja a vez do jogador*/ q->tabuleiro[i][j]='X'; }else{ /*caso seja a vez do computador*/ q->tabuleiro[i][j]='O'; } if((i+j)!=0){/*conecta a lista de nohs*/ ant->prox = q; }else{ primeiro=q; } ant = q; }/*fim do if*/ } }/*fim dos for's de verificacao*/ return primeiro; } int isXO(char c){ return (c=='X'||c=='O'); } int verLinhaColuna(char tab[3][3],int i, int j, char c){ int cont=0; if(tab[i][j]==c){ if(tab[i][(j+1)% 3]==c && tab[i][(j+2)%3]==c){/*verifica espaco na mesma linha*/ cont++; } if(tab[(i+1)%3][j]==c && tab[(i+2)%3][j]==c){/*verifica espaco na mesma coluna*/ cont++; } } return cont; } int verDiagonais(char tab[3][3],int i, int j, char c){ int cont=0; if(tab[i][j]==c){ /*verifica espaco na mesma diagonal da esquerda pra direita*/ if(tab[(i+1)%3][(j+1)%3]==c && tab[(i+2)%3][(j+2)%3]==c){ cont++; } /*verifica espaco na mesma diagonal da direita pra esquerda*/ if(tab[(i+1)%3][(j+2)%3]==c && tab[(i+2)%3][(j+1)%3]==c){ cont++; } } return cont; } int avaliarPosicao(char tab[3][3]){ char c,d; int cont1=0, cont2=0, result; c='X'; d='O'; /*verifica espacos para todas as combinacoes possiveis*/ cont1+=verDiagonais(tab,1,1,c); cont2+=verDiagonais(tab,1,1,d); cont1+=verLinhaColuna(tab,0,0,c); cont2+=verLinhaColuna(tab,0,0,d); cont1+=verLinhaColuna(tab,1,1,c); cont2+=verLinhaColuna(tab,1,1,d); cont1+=verLinhaColuna(tab,2,2,c); cont2+=verLinhaColuna(tab,2,2,d); result=cont1-cont2; return (result>=0)? result : -result; } NOH constroiArvore(char tab[3][3],int nivelJog, int jogada){ int i,j; NOH *pArvore = (NOH *) malloc(sizeof(NOH)); printf("\nAguarde\n"); /*copia as informações do tabuleiro para o novo NOH*/ for (i=0; i<3; ++i) for (j=0; j<3; ++j) pArvore->tabuleiro[i][j] = tab[i][j]; /* copia as outra informações para o novo NOH*/ pArvore->jogada = jogada; pArvore->filho= NULL; pArvore->prox= NULL; /*expande o NOH para as suas possibilidades*/ expandirNoh (pArvore, 0, nivelJog); return *pArvore; } void expandirNoh (NOH* p, int pNivel,int profund){ NOH *q; if (pNivel < profund) { q = gerarListaNohs(*p); p->filho = q; while (q != NULL) { if (p->jogada == 1){ q->jogada= -1; }else q->jogada =1; q->filho=NULL; expandirNoh(q, pNivel+1, profund); q = q->prox; } } } void libera(NOH *pnd){ NOH *p; if (pnd->filho == NULL) { free(pnd); } else{ p = pnd->filho; libera(p); p = p->prox; while (p != NULL) { libera(p); p = p->prox; } } } int verVitoria(NOH n){ int vitoria=0; vitoria = verDiagonais(n.tabuleiro,1,1,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n.tabuleiro,0,0,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n.tabuleiro,1,1,'O'); if(vitoria!=0) return 1; vitoria = verLinhaColuna(n.tabuleiro,2,2,'O'); if(vitoria!=0) return 1; return 0; } Agradeço desde já.