#include "types.h"
#include "ArbreCL.h"
#include "Grille.h"
#include "MinMax.h"




void ValuerListe(ArbreCL &Arbre,CL *pere,Grille &grille,int &joueur)
//Valuation de liste de coups légaux à profondeur maximale
{
  CL *courant;
  int eval,victoire;
  
  //cout<<"Evaluation position joueur"<<joueur<<endl;
  
  courant=Arbre.AdressePremierFils(pere);
  while (courant!=NULL)
    {
      grille.Jouer(joueur,courant->coup);
      courant->victoire=grille.TesterVictoire(joueur);
      if (!courant->victoire) 
	{courant->valeur=grille.Evaluer(joueur);
	courant->nvterminal=0;
	}  //souhaitable
      
      grille.DeJouer(joueur,courant->coup);
      courant=Arbre.AdresseFrerePuine(courant);
    }  
}




CL* Selection(ArbreCL &Arbre,CL *pere)
  //Renvoie la référence du coup légal le plus opportun dans la liste 
  //testée en victoire et évaluée (au niveau n ou >n...)
  //en pratique: effectue une sélection sur 3 critères : victoire/défaite, niveau de v/d , valuation
{
  CL *courant,*max;
  if (pere==NULL) {cout<<"Pas de pere!"<<endl;return(NULL);}
  courant=Arbre.AdressePremierFils(pere);max=courant;
  if (courant==NULL) {cout<<"Liste vide!"<<endl;return(NULL);}  // a virer
  while (courant!=NULL)
    {
      //si on trouve une valeur de victoire supérieure à ce niveau on la garde sans discuter
      if (courant->victoire > max->victoire) {max=courant;}  //cas (0 > -1) 
      else //courant<=max
	{
	  if (courant->victoire == max->victoire)
	    {
	      switch (courant->victoire)
		{
		case 0:  //on a le choix entre deux états normaux: on prend le plus valué  
		  if (courant->valeur > max->valeur)  {max=courant;}
		  break;
		case 1: //on a le choix entre deux victoires : on prend la plus proche 
		  if (courant->nvterminal < max->nvterminal) {max=courant;}
		  break;
		case -1:  //on a le choix entre deux défaites : repousser l'échéance 
		  if (courant->nvterminal > max->nvterminal) {max=courant;}
		  break;
		default: cout<<"Probleme switch!"<<endl;
		}//fin switch
	    }//fin if 
	}//fin else
      courant=Arbre.AdresseFrerePuine(courant);
    }
  return(max);
}



void GenererListeCL(ArbreCL &Arbre,CL *pere,Grille &grille,int &joueur)
  //crée une liste de coups légaux
  //la remplit de tous les coups légaux du camp choisi
  //la retourne pour manipulations
{
  int col,correct;
  //cout<<"Génération liste coups légaux:"<<joueur<<" ";
  Arbre.ViderFils(pere);
  for (col=0;col<7;col++)
    {
      correct=grille.Tester(joueur,col);
      if (correct) { Arbre.InsererPremierFils(pere,col); }
    }
}




//*****************************************************************************
//Ceci est l'algorithme qui détermine le coup le plus judicieux d'après un développement au niveau n
int MinMax(Grille &grille,int &joueur,int &profmax)
  //Renvoie le coup de niveau 1 amenant à la meilleure situation possible au niveau N
{ 
  int prof,coup,j,victoire;
  ArbreCL Arbre; CL *pere,*courant,*choisi;
  
  j=joueur;
  prof=1;pere=Arbre.AdresseRacine();courant=pere;
  
  cout<<"MinMax(): vous y etes"<<endl;
  GenererListeCL(Arbre,pere,grille,joueur);
  Arbre.AfficherFils(pere);
  
  while(prof>=1)
    {
      while  ( Arbre.AdresseFilsSuivant(pere,courant)!=NULL )
	{ 
	  //"while"
	  if (prof!=profmax)
	    {
	      //"prof!=profmax:"
	      courant=Arbre.AdresseFilsSuivant(pere,courant);
	      //
	      grille.Jouer(j,courant->coup);
	      courant->victoire=grille.TesterVictoire(j);
	      if (!courant->victoire)
		//s'il n'y a pas de victoire sur ce coup: on fait comme si de rien 
		//n'était et on continue à développer l'arbre à partir du coup
		{
		  prof++;pere=courant;
		  grille.InverseJoueur(j);
		  GenererListeCL(Arbre,pere,grille,j);
		}
	      else {//"Victoire Constatée sur le coup courant:on ne développe pas"
		courant->valeur=grille.Evaluer(j);courant->victoire=1;courant->nvterminal=prof;
		grille.DeJouer(j,courant->coup);
		Arbre.Fratricide(courant); 
		//"Suppression de tous les freres réalisée"
	      }
	      
	    }
	  else //***********************************************************************
	    {
	      //prof==profmax 
	      ValuerListe(Arbre,pere,grille,j);
	      
	      choisi=Selection(Arbre,pere);
	      if (choisi->victoire) {choisi->nvterminal=prof;} 
	      else {pere->valeur=-choisi->valeur;}
	      pere->nvterminal=choisi->nvterminal;pere->victoire=-choisi->victoire;
	      
	      //on remonte!
	      if (prof>1){
		grille.InverseJoueur(j);
		grille.DeJouer(j,courant->coup);
		//grille.Afficher();
		Arbre.ViderFils(pere);
		pere=Arbre.AdressePere(pere); 
		prof--;
	      }
	      else
		{
		  //point de sortie du cas particulier ou prof=1
		  //cout<<"Point de sortie prof=1:"<<endl;
		  pere->coup=Selection(Arbre,pere)->coup; 
		  
		  Arbre.ViderFils(pere);
		  //grille.Afficher();
		  return(pere->coup);
		}
	      
	    }
	  
	}//fin  while ( Arbre.AdressePremierFils(pere)=!NULL )
      
      //Point de reprise: 
      
      //Une sous-liste entière est valuée par des valuations corrigées (ie "remontées" de fils) 
      //transmettons à son père le MAX() et effaçons-la
      if (Selection(Arbre,pere)==NULL) 
	{
	  //cas carticulier: la liste des CL du pere est vide
	  cout<<endl<<"Cas Particulier!"<<endl;
	  pere->valeur=grille.Evaluer(j);
	  //on ne peut pas lui donner de valeur corrigée (ie venant d'un de ses fils)
	  //passqu'il en a plus: on lui attribue donc sa valeur immédiate non-corrigée
	}
      else  //cas général
	{
	  choisi=Selection(Arbre,pere); 
	  if (!choisi->victoire) {pere->valeur=-choisi->valeur;}
	  pere->nvterminal=choisi->nvterminal;pere->victoire=-choisi->victoire;
	}
      
      //on remonte au niveau supérieur et on repart
      if (prof==1)  { cout<<endl<<"sorti"<<endl; return( Selection(Arbre,pere)->coup ); }
      grille.InverseJoueur(j);grille.DeJouer(j,pere->coup);//pere!! et non courant
      Arbre.ViderFils(pere);
      courant=pere;pere=Arbre.AdressePere(pere);
      prof--;
      
    }//fin while(prof>=1)
  
  cout<<"Point de sortie général"<<endl;
  
  
}//fin MinMax()  

//*************************************************************************************














//**************************************************************************************

CL* Max(ArbreCL &Arbre,CL *pere)
  //renvoie la ref. du Coup Légal de plus haute valuation dans la liste 
{
  CL *courant,*max; 
  if (pere==NULL) {cout<<"Pas de pere!"<<endl;return(NULL);}
  courant=Arbre.AdressePremierFils(pere);
  max=courant;
  if (courant==NULL) {cout<<"Liste vide!"<<endl;return(NULL);}
  while (courant!=NULL)
    {
      //cout<<courant->coup+1<<":"<<courant->valeur<<" ; ";
      if (courant->valeur>max->valeur) {max=courant;}
      courant=Arbre.AdresseFrerePuine(courant);
    }
  //cout<<endl;
  return(max);
}








//***************************************************************************************
//implémentation provisoire et non effective de l'AlphaBeta


int AlphaBeta(ArbreCL &Arbre,CL *som)
{
  int condpere,derniere;
  derniere=(som->frere==NULL);
  if ((som==NULL)||(som->pere==NULL)) {return(0);} else {condpere=som->pere->cond;}

  int profinit=0;int prof=0;

  while (condpere==0)
    {
      //on donne au pere les valeurs cond et valcond
      som->pere->cond=1;som->pere->valcond=-som->pere->valeur;
      //on remonte
      som=som->pere;prof--;
      if (som==NULL) {return(0);} else {condpere=som->pere->cond;}
    }
  //a ce stade, on arrive jusqu'au sommet dont le pere porte une condition

  while (som!=NULL)
    {
      if ( ConditionRemplie(Arbre,som) )
	{
	  MajGdPere(Arbre,som);
	  som->pere->valeur=-som->valeur;
	  som->pere->valcond=-som->pere->valeur;
	  som=som->pere;prof--;
	}
      else
	{
	  if ( derniere|| (profinit-prof<=1) ) {Arbre.Elaguer(som);}
	  else {return(0);}
	}
    }
}



int ConditionRemplie(ArbreCL &Arbre,CL *som)
{
  if ( som->pere->valcond >= som->valeur ) {return(1);} else {return(0);}
}


void MajGdPere(ArbreCL &Arbre,CL *som)
{
  if (som->pere->pere!=NULL)
    {
      if (som->pere->valeur==-som->pere->pere->valeur)
	{som->pere->pere->valeur=som->valeur;
	som->pere->pere->valcond=-som->pere->pere->valeur;}
    }
}