Foro de elhacker.net

Buenas noches a todos ustedes, estamos haciendo un trabajo sobre un ajedrez implementando inteligencia artificial. Por ahora hemos empezado con el juego Tic Tac Toe o gato, a la hora de crear los arboles, es decir, todas las jugadas posibles, nuestro codigo debe crear aproximadamente 250 mil nodos pero nos crea 3 millones. Ojalá alguien nos pueda ayudar a detectar el error.



#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define true 1
#define false 0
#define EQUIS 1
#define CIRCULO -1

struct nodo
{
   char mapa[3][3];//={{0,0,0},{0,0,0},{0,0,0}};
   struct nodo *padre;
   struct nodo *sigNivel;
   //sigNivel=NULL;
   //padre=NULL;
};

//global hijos creados
unsigned long hijos=1;

//Funciones auxiliares

// creaHijo : nodo, char[3][3], nodo
//Recibe apuntadores al nodo anterior del nivel, al padre del nodo a crear y el mapa del padre
struct nodo *creaHijo(struct nodo *antNivel, char mapa[3][3], struct nodo *padre,char turno)
{
   struct nodo *nuevo;
   nuevo=calloc(1,sizeof(struct nodo));
   hijos++;
   //Copiamos mapa
   memcpy((nuevo->mapa),mapa,9*(sizeof(char)));
   (*nuevo).padre=padre;
   (*nuevo).sigNivel=NULL;
   
   if(antNivel!=NULL)
   {
      (*antNivel).sigNivel=nuevo;
     
   }
   //printf("El mapa es:\n");
   //printf("Turno:%d\n",turno);
   //for(i=0;i<3;i++)
   //{
     // for(j=0;j<3;j++)
       //  printf("%d ",nuevo->mapa[j]);
      //putchar('\n');
   //}
         //fflush(stdin);
      //getchar();
   return nuevo;
 
}

char puedeTirar(char ren, char col, char mapa[3][3])
{
   if(mapa[ren][col]==0)
      return true;
   return false;
}

//Ganador : -> numero
//Funcion que regresa 0 si nadie ha ganado, 1 si gana 'x' y -1 si gana 'o'
char ganador(char mapa[3][3], char turno)
{
   //solo es necesario comprobar la tirada anterior pot lo tanto
   //turno=-turno
   
   //tiradas laterales xxx
   if((mapa[0][0]==turno)&&(mapa[0][1]==turno)&&(mapa[0][2]==turno))
      return -turno;

   if((mapa[1][0]==turno)&&(mapa[1][1]==turno)&&(mapa[1][2]==turno))
      return -turno;
    
   if((mapa[2][0]==turno)&&(mapa[2][1]==turno)&&(mapa[2][2]==turno))
      return -turno;

   //tiradas verticales
   if((mapa[0][0]==turno)&&(mapa[1][0]==turno)&&(mapa[2][0]==turno))
      return -turno;
    
   if((mapa[0][1]==turno)&&(mapa[1][1]==turno)&&(mapa[2][1]==turno))
      return -turno;
    
   if((mapa[0][2]==turno)&&(mapa[1][2]==turno)&&(mapa[2][2]==turno))
      return -turno;
    
   //tiradas diagonales
   if((mapa[0][0]==turno)&&(mapa[1][1]==turno)&&(mapa[2][2]==turno))
      return -turno;
    
   if((mapa[0][2]==turno)&&(mapa[1][1]==turno)&&(mapa[2][0]==turno))
      return -turno;

   return 0;
}

int main(void)
{
struct nodo *iniNiv;
struct nodo *barrido;
struct nodo *antNiv;
unsigned long creados=1;
char turno=EQUIS;
char i,j;

//indices de arreglo
char ren, col;

//FILEPOINTER PARA DEBUGEO
//FILE* fp;
//fp=fopen("tabla.txt","w");


//-----------------LO PRINCIPAL-----------------------------------------------------------------------
//Creamos el primer nodo el cual es el tablero vacio
barrido=calloc(1,sizeof(struct nodo));

//Fragmento del codigo mas importante, se usan 2 apuntadores
// 1 para el barrido(nodo al q le creamos hijos), 1 para apuntar al nodo inicial de cada nivel y 1 para
// apuntar al anterior en el mismo nivel: barrido, iniNivel y antNiv

//Este while lidia con los cambios de nivel
//mientras haya un elemento en el nuevo nivel se le puede intentar crear hijos

while(iniNiv!=NULL)
{
   antNiv=NULL;
   iniNiv=NULL;
   //Esta while lidia con hacer hijos para todos los de un nivel
   //mientras haya padres que puedan crear hijos, luego pasamos a hacer hijos de hijos
   while(barrido!=NULL)
   {
      //ahora creamos los hijos donde sea posible
     for(ren=0;ren<3;ren++)
     {
        for(col=0;col<3;col++)
       {
          //preguntamos si ya ganamos y si se puede tirar, si si entonces creamos
         //hijo y luego pintamos el disparo
         if((ganador((*barrido).mapa,turno)==false)&&(puedeTirar(ren,col,(*barrido).mapa)==true))
         {
            antNiv=creaHijo(antNiv,(*barrido).mapa,barrido,turno);
            //creados++;
            //se posiciona iniNiv sobre el primer elemento de este nivel
            if(iniNiv==NULL)
            {
               iniNiv=antNiv;
            }
            
            //ahora pintamos el disparo
            antNiv->mapa[ren][col]=turno;
            
            //DEBUGEO-------------------------------------------------
              //fprintf(fp,"El mapa es:\n");
//              fprintf(fp,"Turno:%d\n",turno);
//              for(i=0;i<3;i++)
//              {
//                 for(j=0;j<3;j++)
//                    fprintf(fp,"%d ",antNiv->mapa[j]);
//                 fputc('\n',fp);
//              }
              //fflush(stdin);
              //getchar();
             
           //DEBUGEO--------------------------------------------------
         }
       }
     }    
     //pasamos al siguiente nodo del mismo nivel
     barrido=(*barrido).sigNivel;
   }
   
   //pasamos al siguiente nivel si es posible
   barrido=iniNiv;
   //cambiamos de tirador
   turno=-turno;
}

printf("El numero de nodos creados es: %ul",hijos);
getchar();
return 0;
}