/*Juego de Gato Heurístico
  Autor:Jesús M.Olivares Ceja
  Desarrollado para propósitos didácticos de Ingeniería del Conocimiento
  Su copia es libre, si lo utiliza para propósitos no lucrativos.
*/
#include "stdio.h"
#include "dos.h"
#define SI  1
#define NO  0
  // TIPOS
  typedef struct {
  char tablero[9];
  int f;
} TipoTablero;
	//VARIABLES
struct
{
  TipoTablero Tm;
  int g;
  int UTc;
  TipoTablero Tc[7];
} arbol[8];
int UTiradaMaq;
TipoTablero juego;
char Linea[100];
	// PROTOTIPOS
void desplegaTablero (void);
int esValida (int tirada);
void generaTiradasMaq (void);
void generaTiradasContrario (int iTiradaMaq);
void creaTiradaMaq (int i);
void creaTc (int iTiradaMaq, int i);
void CalculaF (TipoTablero * t);
int revisaFin (int max);
void
main (void)
{
  int fin, valida, tiradaContrario, i;
  int iTiradaMaq, iTiradaContrario;
  int min, max, cualTm, vacias;
  // INICIALIZA EL TABLERO DE JUEGO
  for (i = 0; i < 9; i++)
    juego.tablero[i] = ' ';
  // MIENTRAS NO SEA FIN JUEGA
  fin = NO;
  while (fin == NO)
    {
      desplegaTablero ();
      // TOMA LA TIRADA DEL CONTRARIO HASTA QUE SEA VALIDA
      valida = NO;
      while (valida == NO)
	{
	  printf ("¿Donde tiras? [1..9]                0 = salir?\n");
	  gets (Linea);
	  tiradaContrario = atoi (Linea) - 1;
	  valida = esValida (tiradaContrario);
	  switch (valida)
	    {
	    case 0:
	      fin = SI;
	      valida = SI;
	      break;
	    case 1:
	      valida = SI;
	      break;
	    case 2:
	      printf ("Posición Ocupada, indica otra\n");
	      valida = NO;
	      break;
	    case 3:
	      printf ("Posición Erronea, indica otra [1..9]\n");
	      valida = NO;
	      break;
	    }
	}			// SI DECIDIO  TERMINAR, SALIRSE        
      if (fin == SI)
	continue;		// COLOCA LA TIRADA DEL CONTRARIO        
      juego.tablero[tiradaContrario] = ' ';
      desplegaTablero ();
      CalculaF (&juego);
      if (juego.f < -9000)
	{
	  printf ("Ganaste\n");
	  fin = SI;
	  continue;
	}			// GENERA POSIBLES TIRADAS DE LA MAQUINA
      UTiradaMaq = 0;
      generaTiradasMaq ();
      // PARA CADA TIRADA DE LA MAQUINA
      for (iTiradaMaq = 0; iTiradaMaq < UTiradaMaq; iTiradaMaq++)
	{
	  // GENERA POSIBLES TIRADAS DEL CONTRARIO            
	  arbol[iTiradaMaq].UTc = 0;
	  generaTiradasContrario (iTiradaMaq);
	  min = 15000;
	  // PARA CADA TIRADA DEL CONTRARIO            
	  for (iTiradaContrario = 0;
	       iTiradaContrario < arbol[iTiradaMaq].UTc; iTiradaContrario++)
	    {
	      // CALCULA F                
	      CalculaF (&arbol[iTiradaMaq].Tc[iTiradaContrario]);
	      // ENCUENTRA LA F MINIMA                
	      if (min > arbol[iTiradaMaq].Tc[iTiradaContrario].f)
		min = arbol[iTiradaMaq].Tc[iTiradaContrario].f;
	    }
	  // CALCULA F'            
	  CalculaF (&arbol[iTiradaMaq].Tm);
	  // CALCULA G            
	  arbol[iTiradaMaq].g = arbol[iTiradaMaq].Tm.f + min;
	}
      max = -15000;
      // ELIGE TM MEDIANTE EL CRITERIO G MAXIMA        
      cualTm = -1;
      for (iTiradaMaq = 0; iTiradaMaq < UTiradaMaq; iTiradaMaq++)
	{
	  if (arbol[iTiradaMaq].g > max)
	    {
	      cualTm = iTiradaMaq;
	      max = arbol[iTiradaMaq].g;
	    }
	}
      // SI LA MAQUINA TIRO        
      if (cualTm > -1)
	{
	  printf ("voy a tirar...\n");
	  delay (1000);
	  // COPIA EL TABLERO CON LA JUGADA DESEADA            
	  for (i = 0; i < 9; i++)
	    juego.tablero[i] = arbol[cualTm].Tm.tablero[i];
	}
      // DETERMINA LA SITUACION ACTUAL DEL JUEGO        
      CalculaF (&juego);
      switch (revisaFin (juego.f))
	{
	case 0:
	  break;		// CONTINUA        
	case 1:
	  desplegaTablero ();
	  printf ("LO SIENTO, Gane!!!!\n");
	  fin = SI;
	  break;
	case 2:
	  desplegaTablero ();
	  printf ("Ganaste\n");
	  fin = SI;
	  break;
	case 3:
	  printf ("Quedamos   G a t o, hagamos otro intento\n");
	  fin = SI;
	  break;
	}
    }
}
 
void
desplegaTablero (void)
{
  int r, c;
  for (r = 0; r < 3; r++)
    {
      for (c = 0; c < 3; c++)
	if (juego.tablero[3 * r + c] == 32)
	  printf ("%d  ", 3 * r + c + 1);
	else
	  printf ("%c  ", juego.tablero[3 * r + c]);
      printf ("\n\n");
    }
}
 
int
esValida (int tirada)
{
  if (tirada == -1)
    return 0;			// NO CONTINUAR    
  if ((tirada > -1) && (tirada < 9))
    if (juego.tablero[tirada] == ' ')
      return 1;
    else
      return 2;
  // POSICION OCUPADA
  else
    return 3;			// POSICION INVALIDA
}
 
void
generaTiradasMaq (void)
{
  int i;
  for (i = 0; i < 9; i++)
    if (juego.tablero[i] == ' ')
      creaTiradaMaq (i);
}
 
void
generaTiradasContrario (int iTiradaMaq)
{
  int i;
  for (i = 0; i < 9; i++)
    if (arbol[iTiradaMaq].Tm.tablero[i] == ' ')
      creaTc (iTiradaMaq, i);
}
 
void
creaTiradaMaq (int i)
{
  int k;
  for (k = 0; k < 9; k++)
    arbol[UTiradaMaq].Tm.tablero[k] = juego.tablero[k];
  arbol[UTiradaMaq].Tm.tablero[i] = 'o';
  UTiradaMaq++;
}
 
void
creaTc (int iTiradaMaq, int i)
{
  int k;
  for (k = 0; k < 9; k++)
    arbol[iTiradaMaq].Tc[arbol[iTiradaMaq].UTc].tablero[k] =
      arbol[iTiradaMaq].Tm.tablero[k];
  arbol[iTiradaMaq].Tc[arbol[iTiradaMaq].UTc].tablero[i] = 'x';
  arbol[iTiradaMaq].UTc++;
}
 
void
CalculaF (TipoTablero * t)
{
  int v, h, d;
  int r, c, ctaO, ctaE, ctaX;
  // SUMA LAS VERTICALES MAQUINA
  v = 0;
  for (c = 0; c < 3; c++)
    {
      ctaO = 0;
      ctaE = 0;
      for (r = 0; r < 3; r++)
	{
	  if (t->tablero[3 * r + c] == 'o')
	    ctaO++;
	  if (t->tablero[3 * r + c] == ' ')
	    ctaE++;
	}
      if (ctaO == 3)
	{
	  t->f = 9999;
	  return;
	}
      if ((ctaO + ctaE) == 3)
	v++;
    }
  h = 0;
  for (r = 0; r < 3; r++)
    {
      ctaO = 0;
      ctaE = 0;
      for (c = 0; c < 3; c++)
	{
	  if (t->tablero[3 * r + c] == 'o')
	    ctaO++;
	  if (t->tablero[3 * r + c] == ' ')
	    ctaE++;
	}
      if (ctaO == 3)
	{
	  t->f = 9999;
	  return;
	}
      if ((ctaO + ctaE) == 3)
	h++;
    }				// SUMA LAS DIAGONALES MAQUINA    
  d = 0;
  ctaO = 0;
  ctaE = 0;
  for (c = 0; c < 9; c += 4)
    {
      if (t->tablero[c] == 'o')
	ctaO++;
      if (t->tablero[c] == ' ')
	ctaE++;
    }
 
  if (ctaO == 3)
    {
      t->f = 9999;
      return;
    }
  if ((ctaO + ctaE) == 3)
    d++;
  ctaO = 0;
  ctaE = 0;
  for (c = 2; c < 7; c += 2)
    {
      if (t->tablero[c] == 'o')
	ctaO++;
      if (t->tablero[c] == ' ')
	ctaE++;
    }
 
  if (ctaO == 3)
    {
      t->f = 9999;
      return;
    }
  if ((ctaO + ctaE) == 3)
    d++;
  // SUMA LAS VERTICALES CONTRARIO    
  for (c = 0; c < 3; c++)
    {
      ctaX = 0;
      ctaE = 0;
      for (r = 0; r < 3; r++)
	{
	  if (t->tablero[3 * r + c] == 'x')
	    ctaX++;
	  if (t->tablero[3 * r + c] == ' ')
	    ctaE++;
	}
      if (ctaX == 3)
	{
	  t->f = -9999;
	  return;
	}
      if ((ctaX + ctaE) == 3)
	v--;
    }
 
  // SUMA LAS HORIZONTALES CONTRARIO    
  for (r = 0; r < 3; r++)
    {
      ctaX = 0;
      ctaE = 0;
      for (c = 0; c < 3; c++)
	{
	  if (t->tablero[3 * r + c] == 'x')
	    ctaX++;
	  if (t->tablero[3 * r + c] == ' ')
	    ctaE++;
	}
      if (ctaX == 3)
	{
	  t->f = -9999;
	  return;
	}
      if ((ctaX + ctaE) == 3)
	h--;
    }
 
  // SUMA LAS DIAGXNALES CONTRARIO    
  ctaX = 0;
  ctaE = 0;
  for (c = 0; c < 9; c += 4)
    {
      if (t->tablero[c] == 'x')
	ctaX++;
      if (t->tablero[c] == ' ')
	ctaE++;
    }
 
  if (ctaX == 3)
    {
      t->f = -9999;
      return;
    }
  if ((ctaX + ctaE) == 3)
    d--;
  ctaX = 0;
  ctaE = 0;
  for (c = 2; c < 7; c += 2)
    {
      if (t->tablero[c] == 'x')
	ctaX++;
      if (t->tablero[c] == ' ')
	ctaE++;
    }
 
  if (ctaX == 3)
    {
      t->f = -9999;
      return;
    }
  if ((ctaX + ctaE) == 3)
    d--;
  // ASIGNA F    
  t->f = v + h + d;
}
 
int
revisaFin (int max)
{
  int i, vacias;
  if (max > 9000)
    return 1;
  // GANO LA MAQUINA
  if (max < -9000)
    return 2;
  // GANO EL CONTRARIO
  vacias = 0;
  for (i = 0; i < 9; i++)
    if (juego.tablero[i] == ' ')
      vacias++;
  if (vacias > 0)
    return 0;
  // PUEDEN CONTINUAR
  return 3;
  // SE ACABO EL JUEGO FUE GATO
}
 
	// fin del archivo