Ir ao conteúdo
Regras do Clube do Hardware

Ajuda com jogo da velha usando árvores

gustavoarcanjo

Por gustavoarcanjo
em C/C#/C++

 Compartilhar

Posts recomendados

gustavoarcanjo
 

gustavoarcanjo

Postado
Postado

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á.


			
		


		

		
	


	
    



	




					
					
						

  



  



					
					
				

					

					
					







	

	

	

		

			

				


	
		
gustavoarcanjo

	

				
				
			

		

		

			
  



	
		



gustavoarcanjo
	


			

			    Postado 
				
			

		

	

	
	

		




	

		

			

				
    
					
						
  • Autor
    • 
					
					
					
					
					
                  
				

			

			
		


		

		   
		   Postado 
		   
			
			
				
				
			
		

	


	

    

	

		
		

			
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.


			
		


		

		
	


	
    



	




					
						
    
							
							
								
  • 
									9 anos depois...
								
    • 
							
						

					
					
					
				

					

					
					







					
					
					
				

					

					
					







					
					
					
				
			
			




		

	

	
	
	
	
	
	
		
	

			
				
				



	
	
		

			
				
Crie uma conta ou entre para comentar

				
Você precisa ser um usuário para fazer um comentário

			
	
			

				

					

						
Criar uma conta

						
Crie uma nova conta em nossa comunidade. É fácil!

						
							
						
						Crie uma nova conta
					

					

						
Entrar

						
Já tem uma conta? Faça o login.

						Entrar agora
					

				

			

		

	


			
		

	

	
		

			

				
					


    
          Compartilhar
    

    

				
				
                

                


				
			

		

	







	

		
			
				Ir à lista de tópicos
			
		
	

	




						


	

		
	


					

					


	

		
		
        


    

    
      
    
  

  

    
      
    
  

    

    
      
    
  

      

    
      
    
  



		
		


	

		
	


        
	


					

				

			


      



		
			
				
				
				
					

						
						

							
								



	

		
Sobre  o Clube do Hardware

			

				
					

	No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais



				
				
				
				
				
				
				
		

	





							
								



	

		
Direitos autorais

			

				
					

	Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais



				
				
				
				
				
				
				
		

	





							
								



	

		
Mais

			

				
				
					

	


				
				
				
				
				
				
		

	





							
						

					

				
			
		






			
		




	

		
	

	

		
	




		
		


	

		×
		

			
				

					
				

			

			

			

			
		

	






	

		×
		

			
    
				
  • Criar novo...
    • 
				
			

		

	



		
		

	
	









































	














		
		
		
		


	

		

	LANÇAMENTO!





	eletronica2025-popup.jpg 





	

	CLIQUE AQUI E BAIXE AGORA MESMO!