// Board_AI.cpp: implementation of the Board_AI class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "Board.h"
#include "Board_AI.h"
#include "stdlib.h"
#include "Pair_Board_Heu.h"



#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

int validate(int x,int y,int incx, int incy,short State,Board *BOut);

Board_AI::Board_AI()
{

}

Board_AI::~Board_AI()
{

}
POSITION Board_AI::CreateChild(Board *B, short State,CList<Board, Board&> &Array_Child)
{
        short border=B->bGetStates();
        POSITION pos;
        int i,j;
        unsigned char valid;
        int hecho;
        Board *ChildCopy;
        ChildCopy=NULL;
        CPoint *pila;
        pila=NULL;
        if((pila= new CPoint [100])==NULL) {AfxMessageBox("Problemes allotjant la pila");}
        short read_p,write_p;
        read_p=write_p=0;
        for(i=0;i<B->bGetY();i++)
                for(j=0;j<B->bGetX();j++)
                        if((OPONENT(State)!=border)&&(B->bGetCell(j,i)==0))
                        {
                                hecho=0;
                                if(B->bGetCell(j-1,i-1)==OPONENT(State)) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j,i-1)==OPONENT(State)   && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j+1,i-1)==OPONENT(State) && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j-1,i)==OPONENT(State)   && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j+1,i)==OPONENT(State)   && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j-1,i+1)==OPONENT(State) && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j,i+1)==OPONENT(State)   && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                                if(B->bGetCell(j+1,i+1)==OPONENT(State) && !hecho) 
{pila[write_p].x=j;pila[write_p].y=i;write_p++;hecho=1;}
                        }
        
        read_p=--write_p;

        
        while(read_p>=0)
                        {
                        ChildCopy=NULL;
                        ChildCopy= new Board(*B);
                        j=pila[read_p].x;
                        i=pila[read_p].y;
						valid=0;
                        if(validate(j,i,1,1,State,ChildCopy))   {valid=1;}
                        if(validate(j,i,0,1,State,ChildCopy))   {valid=1;}
                        if(validate(j,i,-1,1,State,ChildCopy))  {valid=1;}
                        if(validate(j,i,1,0,State,ChildCopy))   {valid=1;}
                        if(validate(j,i,-1,0,State,ChildCopy))  {valid=1;}
                        if(validate(j,i,1,-1,State,ChildCopy))  {valid=1;}
                        if(validate(j,i,0,-1,State,ChildCopy))  {valid=1;}
                        if(validate(j,i,-1,-1,State,ChildCopy)) {valid=1;}
                        if(valid){   
                                ChildCopy->bSetCell(j,i,State);         
                                pos=Array_Child.AddTail(*ChildCopy);
                                valid=0;
                        }
                        if(ChildCopy!=NULL) delete ChildCopy;
                        read_p--;
                        }

        if(pila!=NULL) delete pila;
        return pos;

}

int validate(int x,int y,int incx,int incy,short State, Board *BOut)
{
        int value;
        if(BOut->bGetCell(x,y)==State) { return 0;}
        value=0;
        if(BOut->bGetCell(x+incx,y+incy)!=0 && BOut->bGetCell(x+incx,y+incy)==OPONENT(State))
        {
                value=validate(x+incx,y+incy,incx,incy,State,BOut);
        }
        if(BOut->bGetCell(x,y)==OPONENT(State) && BOut->bGetCell(x+incx,y+incy)==State)
        {
                BOut->bSetCell(x,y,State);
                value=1;
        }
        return value;
}


CPair_Board_Heu Board_AI::AlphaBeta(Board &B, short jugador, short prof_actual, short prof_maxima,double alpha,double beta, short torn)
{
	
	CPair_Board_Heu pBH;


	if (prof_actual == prof_maxima)
	{
		pBH.B==B;
		//pBH.heu=Heuristica(&B,jugador,jugador);
		pBH.heu=Heuristica1(B,jugador);
		return pBH;
	}

	CList <Board,Board&> lista ;
	POSITION pos ;
	


	if (jugador == NEGRA) // XXX que sea NEGRA siempre minimizador
	{
		

		//pos = Board_AI::CreateChild(Board *B, short State,CList<Board, Board&> &Array_Child)
		Board_AI::CreateChild(&B, BLANCA,lista);
		pBH.B=B;

		while (  ( (pos=lista.GetHeadPosition()) != NULL ) &&  (alpha < beta)  ) 
		{
			pBH = AlphaBeta( lista.GetNext(pos) , OPONENT(jugador), prof_actual+1, prof_maxima, alpha, beta, OPONENT(jugador) );
			

			if (pBH.heu < beta ) 
			{
				beta = pBH.heu;

				pBH.B=lista.RemoveHead();

			}
			else 
			{
				lista.RemoveHead();		
			}


		}

	
		pBH.heu=beta;

	}
	else // XXX sea  BLANCA siempre maximizador
	{
			//pos = Board_AI::CreateChild(Board *B, short State,CList<Board, Board&> &Array_Child)
		Board_AI::CreateChild(&B, BLANCA,lista);
		pBH.B=B;

		while (  ( (pos=lista.GetHeadPosition()) != NULL ) &&  (alpha < beta)  ) 
		{
			pBH = AlphaBeta( lista.GetNext(pos) , OPONENT(jugador), prof_actual+1, prof_maxima, alpha, beta, OPONENT(jugador) );
			

			if (pBH.heu > alpha ) 
			{
				alpha = pBH.heu;

				pBH.B=lista.RemoveHead();

			}
			else 
			{
				lista.RemoveHead();		
			}


		}

		pBH.heu=alpha;
	}

	return pBH;


}




double Board_AI::Heuristica1(Board & B, short jugador)
{
	
	// 1
	// buscamos lineas diagonales,horizontales o verticales
	// que pueden ser cerradas del un jugador 
	// contamos el numero de las piedras que pueden ser cencerradas
	// del oponente, calculamos la proportion 

	// 2
	// tambien contamos las piedras de los dos jugadores y calcuamos
	// la proportion

	// ponderamos los resultados de 1 por la variable weight (10) y
	// los accumulamos con 2

	short dimens = B.bGetX();
	short weight = 10;
	
	int i,j,nnegras,nblancas;
	nnegras=nblancas=0;
	for(i=0;i<dimens;i++)
	{
		for(j=0;j<dimens;j++)
		{
			if(B.bGetCell(j,i)==NEGRA) nnegras++;
			if(B.bGetCell(j,i)==BLANCA) nblancas++;
		}
	}



	short line[8];

	
	// fill array with analyse data, luego passa to Analyze Funcion

	int potblanca,potnegra;
	potblanca=potnegra=0;

	//analyze rows
	for (i=0;i<dimens;i++)
	{
		for (j=0;j<dimens;j++)
		{
			line[j]=B.bGetCell(i,j);
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens);

	}

	//analyze columns
	for (i=0;i<dimens;i++) 
	{
		for (j=0;j<dimens;j++)
		{
			line[j]=B.bGetCell(j,i);
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens);
	}


	//analyze diagonals

	for (i=0;i<dimens-2;i++)
	{
		for (j=0;j+i<dimens;j++)
		{
			line[j]=B.bGetCell(j,i+j);
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens-i);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens-i);

	}
			
	for (i=1;i<dimens-2;i++)
	{
		for (j=0;j+i<dimens;j++)
		{
			line[j]=B.bGetCell(i+j,j);
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens-i);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens-i);

	}

	for (i=0;i<dimens-2;i++)
	{
		for (j=0;j+i<dimens;j++)
		{
			line[j]=B.bGetCell((dimens-1)-j,(dimens-1)-(i+j));
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens-i);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens-i);

	}
	
	
	for (i=1;i<dimens-2;i++)
	{
		for (j=0;j+i<dimens;j++)
		{
			line[j]=B.bGetCell((dimens-1)-i+j,(dimens-1)-j);
		}
		potblanca+=HeuristicaAnalyzeLine(BLANCA,line,dimens-i);
		potnegra +=HeuristicaAnalyzeLine(NEGRA,line,dimens-i);

	}



	if(jugador==NEGRA) return (nnegras*1.0)/(nblancas*1.0)  + weight * ( (potnegra*1.0)/(potblanca*1.0) ) ;
	return (nblancas*1.0)/(nnegras*1.0) + weight * ( (potblanca*1.0)/(potnegra*1.0) ) ;
}

int Board_AI::HeuristicaAnalyzeLine(short jugador, short line[] , short size)
{

	int result;
	result=0;


	short i;
	short open=0;
	short field,close;
	field=close=0;

	//FORWARD 

	for (i=0;i<size;i++)
	{
		field=line[i];

		if ( field != EMPTY )
		{
			if (field==jugador)
			{
				open=1;
			}
			else  // field== OPONENT(jugador)
			{
				if (open==1)
				{
					close=+1;
				}
			}
	
		}
		else // XXX optimization posible!
		{
			if ( open!=0 && close!=0 )
			{
				result=+close;
			}
			open=close=0;
			
		}
	}

	//BACKWARD ( double code, minimize function call overhead )

	open=close=0;

	for (i=size-1;i==0;i--)
	{
		field=line[i];

		if ( field != EMPTY )
		{
			if (field==jugador)
			{
				open=1;
			}
			else  // field== OPONENT(jugador)
			{
				if (open==1)
				{
					close=+1;
				}
			}
	
		}
		else // XXX optimization posible!
		{
			if ( open!=0 && close!=0 )
			{
				result=+close;
			}
			open=close=0;
			
		}
	}

	return result ;
}


// A continuació se us dóna un codi d'una posible heuristica que dona un valor 
// proporcional al nombre de fitxes d'un color que tenim. Per tant quantes més
// fitxes del nostre color aconseguim millor serà la puntuació 
// Aquest cas és per a que veieu un exemple d'heurística.

double Board_AI::Heuristica2(Board & B, short jugador)
{
	int i,j,nnegras,nblancas;
	nnegras=nblancas=0;
	for(i=0;i<B.bGetY();i++)
		for(j=0;j<B.bGetX();j++)
		{
			if(B.bGetCell(j,i)==NEGRA) nnegras++;
			if(B.bGetCell(j,i)==BLANCA) nblancas++;
		}
		if(jugador==NEGRA) return (nnegras*1.0)/(nblancas*1.0);
		return (nblancas*1.0)/(nnegras*1.0);
}

double Board_AI::Heuristica(Board * B, short torn,short jugador)
{
	double a;
	CString aa;
	switch (torn)
	{case BLANCA:
		 a=Heuristica1(*B,jugador);
		 break;
			 
	 case NEGRA:
		 a=Heuristica2(*B,jugador);
		 break;
		
	 default:
		 
			 aa.Format("Problemes d'heuristica");
			 AfxMessageBox(aa);		
			 return 0.0;
		 
	}
	return a;
}