//---------------------------------------------------------------------
//  Sýnislausn á Aukaverkefni hluta 2 í Tölvunarfræði 2, vor 2005
//
//    Það hefur ekki tekist að gera forritið mjög öflugt.  Það reynir
//  þó að koma hundunum fyrir refinn, en það er tiltölulega auðvelt
//  sjá við þeim. 
//
//  Hjálmtýr Hafsteinsson, mars 2005
//---------------------------------------------------------------------
#include <iostream>
#include <string>
using namespace std;


enum teg { MAX, MIN };
const int HAESTAGILDI = 1000000;		// Þetta er "+óendanlegt"


struct reitur {
	int rod;
	int dalk;
	reitur( int r=0, int d=0 ): rod(r), dalk(d) { };
};


// Gagnagrindin leikur samanstendur af frá-reit og til-reit
struct leikur {
	reitur fra;
	reitur til;
	leikur( ) {};
	leikur( reitur f, reitur t ): fra(f), til(t) {};
	friend ostream& operator<< ( ostream& straum, leikur& leik )
	{
		straum << "(" << (char)(leik.fra.dalk+'A') << leik.fra.rod+1 << ", " <<  (char)(leik.til.dalk+'A') << leik.til.rod+1 << ") ";
		return straum;
	}
};



class VeidiBord { 
  public:
  	// Smiðurinn býr til borðið og setur hunda og ref á upphafsreiti
	VeidiBord();
	
	~VeidiBord() {};
	
	// Birtir núverandi stöðu leiksins á staðalúttaki
	void PrentaBord();

	// Framkvæmir leik með hundi, skila ósatt ef ólöglegur leikur
	bool FaeraHund( int nrHund, reitur til );

	// Framkvæmir leik með ref, skilar ósatt ef ólöglegur leikur
	bool FaeraRef( reitur til );

	bool LeikaLeik( leikur leik );

	// Skilar því hvort refurinn á leik
	bool RefurALeik( );

	// Skilar því hvort hundarnir eiga leik
	bool HundarEigaLeik( );

	// Skilar því hvort löglegt sé að leika ref til reitsins til
	bool LoglegurLeikurRefs( reitur til );

	// Skilar því hvort löglegt sé að leika hundi nrHund til reitsins til
	bool LoglegurLeikurHunds( int nrHund, reitur til );

	// Skilar því hvort reiturinn r sé löglegur auður reitur
	bool VeidiBord::audurReitur( reitur r );

	// Skilar staðsetningu tiltekins hunds
	reitur StadaHunds( int nrHund );

	// Skilar staðsetningu refs
	reitur StadaRefs();

	// Skilar satt ef leiknum er lokið
	bool LeikLokid();

	// Skilar satt ef hundarnir hafa sigrað
	bool HundarSigra();

	// Skilar satt ef refurinn hefur sigrað
	bool RefurSigrar();
  private:

	char bord[8][8];
	reitur stadaHund[4];
	reitur stadaRefur;
	bool HundarHafaSigrad;
	bool RefurHefurSigrad;
	bool RLeikur;			// Satt ef refurinn á næst leik
}; 


VeidiBord::VeidiBord()
{
	int i, j;

	for( i=0; i<8; i++ )
		for( j=0; j<8; j++ )
			bord[i][j] = ' ';	// ' ' táknar auðan reit

	bord[0][4] = 'R';			// R táknar refinn
	bord[7][1] = '1';			// 1 táknar hund nr. 1
	bord[7][3] = '2';			// 2 táknar hund nr. 2
	bord[7][5] = '3';			// 3 táknar hund nr. 3
	bord[7][7] = '4';			// 4 táknar hund nr. 4

	stadaRefur.rod = 0;
	stadaRefur.dalk = 4;
	for( i=0; i<4; i++ ) {
		stadaHund[i].rod = 7;
		stadaHund[i].dalk = 2*i+1;
	}

	HundarHafaSigrad = false;
	RefurHefurSigrad = false;

	RLeikur = true;
}


void VeidiBord::PrentaBord()
{
	int i, j;

	cout << endl;
	cout << "    A  B  C  D  E  F  G  H    " << endl;
	cout << "   +--+--+--+--+--+--+--+--+  " << endl;

	for( i=7; i>=0; i-- ) {
		cout << " " << i+1 << " |";
		for( j=0; j<8; j++ ) {
			if( bord[i][j] == ' ' ) 
				if( (i+j) % 2 == 0) cout << "..|";
				else cout << "  |";
			else if( bord[i][j] == 'R' ) cout << "RR|";
			else cout << "H" << bord[i][j] << "|";
		}
		cout << " " << i+1 << endl;
		cout << "   +--+--+--+--+--+--+--+--+  " << endl;
	}
	cout << "    A  B  C  D  E  F  G  H    " << endl;
	cout << endl;
}


bool VeidiBord::FaeraHund( int nrHund, reitur til )
{
	// Ef hundarnir eiga ekki leik þá hætta...
	if( RLeikur )
		return false;

	if( !audurReitur( til ) )
		return false;

	// Ef hundurinn fer ekki niður í næstu röð þá hætta...
	if( til.rod != stadaHund[nrHund-1].rod - 1 ) return false;

	// Ef hundurinn fer ekki á ská til vinstri eða hægri (á næsta svarta reit) þá hætta...
	if( (til.dalk != stadaHund[nrHund-1].dalk - 1) && (til.dalk != stadaHund[nrHund-1].dalk + 1) )
		return false;

	// Framkvæma leik...
	bord[til.rod][til.dalk] = '0' + nrHund;
	bord[stadaHund[nrHund-1].rod][stadaHund[nrHund-1].dalk] = ' ';
	stadaHund[nrHund-1] = til;

	// Ef refurinn hefur engan reit, þá hafa hundarnir sigrað...
	if( !audurReitur( reitur(stadaRefur.rod-1, stadaRefur.dalk-1) ) &&
		!audurReitur( reitur(stadaRefur.rod-1, stadaRefur.dalk+1) ) &&
		!audurReitur( reitur(stadaRefur.rod+1, stadaRefur.dalk+1) ) &&
		!audurReitur( reitur(stadaRefur.rod+1, stadaRefur.dalk-1) ) )
			HundarHafaSigrad = true;

	RLeikur = true;

	return true;
}


bool VeidiBord::FaeraRef( reitur til )
{
	// Ef refurinn á ekki leik þá hætta...
	if( !RLeikur )
		return false;

	if( !audurReitur( til ) )
		return false;

	// Ef refurinn fer ekki á ská til vinstri eða hægri (á næsta svarta reit) þá hætta...
	if( (til.dalk != stadaRefur.dalk - 1) && (til.dalk != stadaRefur.dalk + 1) )
		return false;

	// Ef refurinn fer ekki á upp eða niður um einn þá hætta...
	if( (til.rod != stadaRefur.rod - 1) && (til.rod != stadaRefur.rod + 1) )
		return false;

	// Ef refurinn er kominn í efstu röð þá hefur hann sigrað...
	if( til.rod == 7 )
		RefurHefurSigrad = true;

	// Framkvæma leik...
	bord[til.rod][til.dalk] = 'R';
	bord[stadaRefur.rod][stadaRefur.dalk] = ' ';
	stadaRefur = til;

	RLeikur = false;

	return true;
}


bool VeidiBord::LeikaLeik( leikur leik )
{
	if( RLeikur )
		return FaeraRef( leik.til );
	else
		if( bord[leik.til.rod][leik.til.dalk] == ' ' )
			return FaeraHund( bord[leik.fra.rod][leik.fra.dalk] - '0', leik.til );
		else
			return false;
}


bool VeidiBord::audurReitur( reitur r )
{
	// Ef reiturinn er ekki á borðinu þá er hann ekki auður(!)...
	if( (r.rod < 0) || (r.rod > 7) || (r.dalk < 0) || (r.dalk > 7) )
		return false;

	// Ef eitthvað annað þarna en eyða þá er þar hundur eða refur...
	if( bord[r.rod][r.dalk] != ' ' )
		return false;

	return true;
}


bool VeidiBord::RefurALeik( )
{
	return RLeikur;
}


bool VeidiBord::HundarEigaLeik( )
{
	return !RLeikur;
}


reitur VeidiBord::StadaHunds( int nrHund )
{
	return stadaHund[nrHund-1];
}


reitur VeidiBord::StadaRefs()
{
	return stadaRefur;
}


bool VeidiBord::LeikLokid()
{
	return ( HundarHafaSigrad || RefurHefurSigrad );
}


bool VeidiBord::HundarSigra()
{
	return HundarHafaSigrad;
}


bool VeidiBord::RefurSigrar()
{
	return RefurHefurSigrad;
}



// Klasinn Leikmadur reiknar út næsta leik miðað við stöðuna á leikborðinu
class Leikmadur {
	public:
		Leikmadur( );
		leikur NaestiLeikur( VeidiBord );
	private:

		// Falin föll, sem notuð eru við útreikning á besta leik
		void finnaBesta( VeidiBord, int, teg, int&, leikur& );
		int gildisfall( VeidiBord );
		int buaTilAllaLeiki( VeidiBord, leikur[] );
		int fjoldiAudraAframGranna( VeidiBord, reitur );
		int fjoldiAudraNagranna( VeidiBord, reitur );
		int stadsetnRefs( VeidiBord );
		int fjarlaegdHunda( VeidiBord );
		VeidiBord leikaLeik( VeidiBord, leikur );
		bool betraGildi( int, int, teg );
};


// Smiðurinn gerir ekkert
Leikmadur::Leikmadur( )
{ }


// Þessi útfærsla á leikmanni notar Minimax leit til að finna besta leik
leikur Leikmadur::NaestiLeikur( VeidiBord S )
{
	int bestgildi;
	leikur bestleikur;

	// Förum niður á dýpi 8 í Minimax
	finnaBesta( S, 8, MIN, bestgildi, bestleikur );
	cout << "Tolva velur " << bestleikur << " [" << bestgildi << "]" << endl;

	return bestleikur;
}


// Gildisfallið samanstendur af fjórum þáttum sem hafa mismikið vægi
int Leikmadur::gildisfall( VeidiBord S )
{
	return 5.0 * fjoldiAudraAframGranna( S, S.StadaRefs() )	// Fjöldi auðra reita uppá við fyrir ref
			+ 1.0 * fjoldiAudraNagranna( S, S.StadaRefs() )	// Heildarfjöldi auðra reita fyrir ref
			+ 0.5 * stadsetnRefs( S )						// Númerið á röð refs (hærra = betra)
			+ 0.1 * fjarlaegdHunda( S );					// Fjarlægð hundanna frá refnum
}


// Fjöldi auðra reita í röðinni fyrir ofan (0, 1 eða 2)
int Leikmadur::fjoldiAudraAframGranna( VeidiBord S, reitur r )
{
	int k = 0;

	if( S.audurReitur( reitur( r.rod+1, r.dalk-1) ) ) k++;
	if( S.audurReitur( reitur( r.rod+1, r.dalk+1) ) ) k++;
	
	return k;
}


// Fjöldi auðra reita í kring (0 til 4), skilað mjög lítilli tölu ef enginn auður reitur
int Leikmadur::fjoldiAudraNagranna( VeidiBord S, reitur r )
{
	int k = 0;

	if( S.audurReitur( reitur( r.rod-1, r.dalk-1) ) ) k++;
	if( S.audurReitur( reitur( r.rod-1, r.dalk+1) ) ) k++;
	if( S.audurReitur( reitur( r.rod+1, r.dalk+1) ) ) k++;
	if( S.audurReitur( reitur( r.rod+1, r.dalk-1) ) ) k++;

	// Ef enginn auður reitur fyrir ref þá skila mjög lítilli tölu
	if( k == 0 )
		return -HAESTAGILDI;
	else
		return k;
}


// Skilar því hversu hátt refurinn er í borðinu (stór tala ef í efstu röð)
int Leikmadur::stadsetnRefs( VeidiBord S )
{
	if( S.StadaRefs().rod == 7 )
		return HAESTAGILDI;
	else
		return S.StadaRefs().rod;
}


// Reiknar fjarlægð hundanna frá refnum í öðru veldi og skilar summu þess
//   þ.e.  d(h1,r)^2 + d(h2,r)^2 + d(h3,r)^2 + d(h4,r)^2
int Leikmadur::fjarlaegdHunda( VeidiBord S )
{
	int d = 0;
	int Rrod = S.StadaRefs().rod;
	int Rdalk = S.StadaRefs().dalk;

	for( int i=1; i<=4; i++ ) {
		int Hrod = S.StadaHunds( i ).rod;
		int Hdalk = S.StadaHunds( i ).dalk; 
		d += (Hrod - Rrod) * (Hrod - Rrod)
			+ (Hdalk - Rdalk) * (Hdalk - Rdalk);
	}

	return d;
}


// Setur alla löglega leiki í stöðunni S í fylkið moguLeikir og skilar fjölda leikja
int Leikmadur::buaTilAllaLeiki( VeidiBord S, leikur moguLeikir[] )
{
	reitur til;
	int fjoldi = 0;

	if( S.RefurALeik() ) {
		til = reitur(S.StadaRefs().rod-1, S.StadaRefs().dalk-1);
		if( S.audurReitur( til ) )
			moguLeikir[fjoldi++] = leikur( S.StadaRefs(), til );

		til = reitur(S.StadaRefs().rod-1, S.StadaRefs().dalk+1);
		if( S.audurReitur( til ) )
			moguLeikir[fjoldi++] = leikur( S.StadaRefs(), til );

		til = reitur(S.StadaRefs().rod+1, S.StadaRefs().dalk+1);
		if( S.audurReitur( til ) )
			moguLeikir[fjoldi++] = leikur( S.StadaRefs(), til );

		til = reitur(S.StadaRefs().rod+1, S.StadaRefs().dalk-1);
		if( S.audurReitur( til ) )
			moguLeikir[fjoldi++] = leikur( S.StadaRefs(), til );
	} else {
		for( int h=1; h<=4; h++ ) {
			til = reitur(S.StadaHunds( h ).rod-1, S.StadaHunds( h ).dalk-1);
			if( S.audurReitur( til ) )
				moguLeikir[fjoldi++] = leikur( S.StadaHunds( h ), til );

			til = reitur(S.StadaHunds( h ).rod-1, S.StadaHunds( h ).dalk+1);
			if( S.audurReitur( til ) )
				moguLeikir[fjoldi++] = leikur( S.StadaHunds( h ), til );
		}
	}
	return fjoldi;
}


// Skilar nýrri stöðu eftir leiknum L hefur verið leikið í stöðunni S
VeidiBord Leikmadur::leikaLeik( VeidiBord S, leikur L )
{
	VeidiBord nyttS = S;
	nyttS.LeikaLeik( L );
	return nyttS;
}



// Venjuleg Minimax leit
void Leikmadur::finnaBesta( VeidiBord S, int dypi, teg tegund, int &bestagildi, leikur &bestileikur )
{
	teg naestategund;
	int nyttgildi;
	leikur nyrleikur;
	leikur moguLeikir[16];


	if( dypi == 0 ) {
		bestagildi = gildisfall( S );
		return;
	}

	int fjLeikja = buaTilAllaLeiki( S, moguLeikir );

	if( fjLeikja == 0 ) {
		bestagildi = gildisfall( S );
		return;
	}

	if( tegund == MAX ) {
		naestategund = MIN;
		bestagildi = -HAESTAGILDI;
	} else {
		naestategund = MAX;
		bestagildi = HAESTAGILDI;
	}

	for( int i=0; i<fjLeikja; i++ ) {
		leikur L = moguLeikir[i];
		VeidiBord SeftirL = leikaLeik( S, L );
		finnaBesta( SeftirL, dypi-1, naestategund, nyttgildi, nyrleikur );
		if( betraGildi( nyttgildi, bestagildi, tegund ) ) {
			bestagildi = nyttgildi;
			bestileikur = L;
		}

	}

}



// Fallið skilar því hvort gildið 'nytt' sér betra en gildið
//  'besta' eftir því hvort 'tegund' sé MAX eða MIN.
bool Leikmadur::betraGildi( int nytt, int besta, teg tegund )
{
	if( tegund == MAX )
		if( nytt > besta )
			return true;
		else
			return false;
	else
		if( besta > nytt )
			return true;
		else
			return false;
}


reitur BreytaIReit( string leikur )
{
	reitur r;

	// Breyta dálk í hástaf ef þarf
	if( leikur[0] >= 'a' && leikur[0] <= 'h' )
		leikur[0] += ('A' - 'a');
	r.dalk = leikur[0] - 'A';

	r.rod = leikur[1] - '1';

	return r;
}



// Aðalforritið lætur notandann leika fyrir refinn og tölvuna fyrir hundana
int main()
{
	VeidiBord B;
	Leikmadur Tolva;
	string leik;

	B.PrentaBord();

	while( ! B.LeikLokid() ) {
	
		do {
			cout << "Faera ref til: ";
			cin >> leik;
		} while( ! B.FaeraRef( BreytaIReit( leik ) ) );

		B.PrentaBord();

		if( B.LeikLokid() ) break;

		B.LeikaLeik( Tolva.NaestiLeikur( B ) );

		B.PrentaBord();
	}

	if( B.RefurSigrar() )
		cout << "Refurinn hefur sigrad!" << endl;
	else
		cout << "Hundarnir hafa sigrad!" << endl;

	return 0;
}