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; }
|