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

#include <iostream>
using namespace std;     

struct mossa
{
	int from;
	int to;
	struct mossa *nextEat;
	struct mossa *next;
};

class dama
{
	public:
		
		dama();                  //k
		~dama();                 //k
		void show();             //k
		
		int go(struct mossa move);                   //k
		int can_eat(int ng);                          //k
		int can_go(int from, int to, bool must_eat);  //k
		
		void get_move(int ng);   //k--
		
		void save_game();        //k---
		void load_game();        //k---

		void *find_moves(int ng, bool must_eat);
		void minmax(int ng);
		int bestmove(int ng, int time);

		void findWinner();
		
		char map[32];
};

dama::dama()         //costruttore: inizializza la scacchiera
{
	for(int i=0;i<32;i++)
	{
		if(i<12 && i>=0)
			map[i]=1;
		if(i<20 && i>=12)
			map[i]=0;
		if(i<32 && i>=20)
			map[i]=-1;
	}
}  //fine costruttore

dama::~dama()    //distruttore
{
	system("cls");
	printf("\n\n\t\tFINE");
	Sleep(1000);
}

void dama::show()
{    
	char mappa[32]; //array che contiene la mappa in formato "grafico"
	system("cls");
	printf("\n\t\tDAMA\n\n");
	
	for(int i=0,m=31;;i+=4,m-=4) //ciclo che sposta la mappa "di numeri"
	{                            //in quella "grafica"
		mappa[m-0]=map[i+3];     //sono al contrario: mappa[32]=map[1]
		mappa[m-1]=map[i+2];
		mappa[m-2]=map[i+1];
		mappa[m-3]=map[i+0];
		
		if(m-3==0)
			break;
	}
	
	for(int i=0;i<32;i++)
	{
		if (i%4==0)
		{
			printf("\n\t");
		}
			
		if (i%8==0)
			putchar(' ');

		switch (mappa[i])
		{
			case 1:
				putchar('o');
				putchar(' ');
				break;
			case 2:
				putchar('@');
				putchar(' ');
				break;
			case -1:
				putchar('x');
				putchar(' ');
				break;
			case -2:
				putchar('%');
				putchar(' ');
				break;
			case 0:
				putchar('#');
				putchar(' ');
				break;
			default:
				printf("\n\fatal nerror in function show() \n");
				system("pause");
				exit(0);
		}
		
	}
	
}

void dama::get_move(int ng)
{
	struct mossa* move=new struct mossa;
	struct mossa* first=move;
	
	*move= {-1,-1,NULL,NULL};
	
	bool must_eat=can_eat(ng);       //must_eat=obbligo di mangiare
	cout<<"\n\n\tmust eat:"<<(must_eat?"yes":"no");
	fflush(stdin); 
	printf("\n\n  giocatore %i, che cosa muovi?\n",ng<0?2:1);
	
	scanf("%d",&move->from);
	if(move->from==666)
		save_game();
	move->from--;
	
	while(1)
	{
		if (scanf("%i",&move->to)==0)
		move->to--;
		
		if(can_go(move->from,move->to,must_eat))
		{
			move.nextEat=new struct mossa;  
			move.from=move.to;
			must_eat=1;
			if(getchar()==' ')      //se ha sbagliato il punto di partenza...
				continue;
			break;
		}
	}
	go(*first);    
	return;
}

int dama::go(struct mossa move)
{
	int line_from=move.from/4;
	int line_to=move.to/4;
	int distance=move.to-move.from;
	int killed=0;
	int ng=map[move.from]%2;
	
	if (!((line_to-line_from)/2))  //senza presa
	{
		map[move.to]=map[move.from];
		map[move.from]=0;
		//cout<<"\nspostamento";
	}
	
	if ((line_to-line_from)/2)  //con 1 presa
	{
		map[move.to]=map[move.from];

		int line_num=(line_from%2==0)? 0 : 1;      //se linea pari

		if(distance>0)
			map[move.from+distance/2+line_num-0]=0;
		if(distance<0)
			map[move.from+distance/2+line_num-1]=0; 
		
		map[move.from]=0;
		//cout<<"\npresa";
		killed++;
	}
	
	//promozione
	
	if(line_to==7 && ng==1 || line_to==0 && ng==-1)
		map[move.to]=ng%2*2;

	return killed + move.nextEat==NULL?0:go(*move.nextEat);
}

int dama::can_eat(int ng)
{
	for(int i=0;i<32;i++)      //controllatutte le caselle una per una
	{
		if(map[i]!=ng && map[i]/2!=ng)
			continue;
		//pedina:
		if(can_go(i,i+9*ng,1) || can_go(i,i+7*ng,1))
			return 1;
		//pedone:
		if(map[i]%2==0 && (can_go(i,i+9*-ng,1) || can_go(i,i+7*-ng,1)))
			return 1;	
	}
	return 0;
}                

int dama::can_go(int from, int to, bool must_eat)     // WORK!
{

	//printf("\nfrom: %2i  to: %2i",from,to);
	if(from< 0 && to > 31 || map[from]==0||map[to]!=0) 
		return 0;
	
	int line_from=from/4;
	int line_to=to/4;
	int ng=map[from]%2?map[from]:map[from]/2;  //numero giocatore
	int power=abs(map[from]);     //se pedina =1, se pedone =2
	
	// eat
	if((to==from+9*ng || to==from+7*ng)|| power==2 && (to==from+9*-ng || to==from+7*-ng)) 
	{                           
		if (line_to==line_from+2*ng ||             //controlla la linea
			power==2 && line_to==line_from+2*-ng)
		{
			int mezzo=(from+(to-from)/2+       //è casella in mezzo in diagonale
			(from>to?(line_from%2==0?-1:0):(line_from%2==0?0:1)));

			if((map[mezzo]%2?map[mezzo]:map[mezzo]/2)==-ng)             //controlla il numero di posizione

				return 1;	 //ha superato tutti i controlli
		}
	}                   

	//don't eat
	if(!must_eat && abs(line_from-line_to)==1)              
	{	
		int n=(line_from%2==0?0:1)+(from>to?-1:0);
		
		//avanti
		if(to==from+(3)*ng+n||to==from+(4)*ng+n)
			return 1;	  

		//indietro
		if(power==2 && (to==from+(3)*-ng+n||to==from+(4)*-ng+n))
			return 1;
	}
	//se arriva fin qui mossa non valida!
	return 0; 
}

void dama::save_game()
{
	FILE *save=fopen("save.txt","w");

	cout<<"\nsalvataggio...";
	
	for (int i=0;i<32;i++)
		fputc(map[i],save);

	fclose(save);
		
}

void dama::load_game()
{
	FILE *save;

	if((save=fopen("save.txt","r"))==NULL)
		return;	
	
	
	cout<<"\ncaricamento...";
	
	for (int i=0;i<32;i++)
		map[i]=fgetc(save);

	fclose(save);
}

void* dama::find_moves(int ng, bool must_eat)
{         
	int *poss,n;  //poss= array mosse possibili, n= num. mosse possibili
	
	if(must_eat)
	{
		n=2;
		poss=(int*) malloc(sizeof(int)*n);
		int t_poss[]={7,9};
		memcpy(poss,t_poss,n*4);
	}
	else
	{
		n=5;
		poss=(int*) malloc(sizeof(int)*n);
		int t_poss[]={3,4,5,7,9};
		memcpy(poss,t_poss,n*4);
	}

	struct mossa *first=new struct mossa;
	struct mossa *temp=first;
	temp->next=NULL;
                   //
		for(int i=0; i<32; i++)
		{
			if(map[i]!=ng && map[i]!=2*ng)  
				continue;

			for(int m=0; m < n; m++)
			{
				int to=i + poss[m]*ng;
				if(can_go(i, to , must_eat) && to < 32) //not king
				{
					temp->from = i ;
					temp->to = to ;
					temp=temp->next=new struct mossa;
					temp->next=NULL;
					//printf("\nFROM: %2i  TO: %2i", i,to); 
				}

				to= i - poss[m]*ng;
				if(map[i]==ng*2 && can_go(i , to , must_eat) && to>=0)//king
				{
					temp->from=i;
					temp->to= to;
					temp=temp->next=new struct mossa;
					temp->next=NULL;
					//printf("\nFROM: %2i  TO: %2i", i,to); 
				}
			}
		}

	return first;	 
}
				
int dama::bestmove(int ng, int time)
{
	time++;
	int best_value=-1000;
	int temp_value;
	char backup[32];
	memcpy(backup,map,32*sizeof(char));
	
	bool must_eat=can_eat(ng);
	struct mossa *poss=(struct mossa*)find_moves(ng, can_eat(ng));

	while(poss->next!=NULL)
	{
		
		temp_value=go(*poss)*100;

		//temp_value-=bestmove(-ng);

		if(temp_value >= best_value)
		{
			best_value=temp_value;
		}
		
		memcpy(map,backup,32*sizeof(char));
		poss=poss->next;
	}
	
	return best_value;
}

void dama::minmax(int ng)
{
	struct mossa best={-1,-1,NULL};
	//struct mossa temp;
	int best_value=-1000;
	int temp_value;
	char backup[32];
	memcpy(backup,map,32*sizeof(char));
	
	struct mossa *poss=(struct mossa*)find_moves(ng, can_eat(ng));

	while(poss->next!=NULL)
	{
		
		temp_value=go(*poss)*100;

		temp_value-=bestmove(-ng, 0);

		if(temp_value >= best_value)
		{
			best_value=temp_value;
			best=*poss;
		}
		
		memcpy(map,backup,32*sizeof(char));
		poss=poss->next;
	}
	
	go(best);
	printf("%i %i",best.from,best.to);
	Sleep(1000);
}

void dama::findWinner()
{
	int p1=0,p2=0;
	for(int i=0; i<32; i++)
	{
		switch(map[i])
		{
			case 1:
			case 2:
				p1++;
				break;	
			case -1:
			case -2:
				p2++;
				break;
        }
    }

	if(p1==0)
	{
		Sleep(1000);
		system("cls");
		
		printf("\ngiocatore 2 vince!");
		system("pause");
		exit(0);
	}
	if(p2==0)
	{
		Sleep(1000);
		system("cls");
		
		printf("\ngiocatore 1 vince!");
		system("pause");
		exit(0);
	}
	
}

int main()
{
	class dama partita;
	partita.load_game();
	  
	while(1)
	{
		partita.show();
		//partita.minmax(1);
		//partita.save_game();
		
		partita.show();
		partita.findWinner();
		partita.get_move(-1);
		partita.save_game();
		Sleep(100);
		
	}
}