// © Copyright 1995, Joseph Bergin.  All rights reserved. 

#include <iostream.h>
#include <fstream.h>

#include "Array2.h"
#include "Array.h"
#include "FMG.h"

// French Military Game
// The board looks like this
//
//			1----4----7					// Looks correct in Geneva font
//		    /	 |  \    |    /  |   \
//		  /     |     \ |  /    |     \
//		0----2----5----8----10
//		  \     |    /  |  \    |     /
//		    \   |  /    |    \  |   /
//			 3----6----9

//		   1--4--7		// looks correct in a Fixed font(monaco). 
//		  /|\ | /|\
//		 / | \|/ | \
//		0--2--5--8--10
//		 \ | /|\ | /
//		  \|/ | \|/
//		   3--6--9

//
//  Initially "The Fox" has a piece at 5.  It may move along the arcs.
// Initially "The Police" have pieces at 0,1,3.  
// The Police plays first and may move only to the right or vertically along arcs. 
// The fox wants to get to cell 0 (Escaped with the secrets).  The Police wants to trap
// the fox by denying it a move.  The Police accomplishes this if it completely hems in
// the fox, say at 3,5,9 with the fox at 6.  The Fox wins, however, if the game exceeds
//  20 moves.  
// The person plays the Police and moves first.  The computer plays the fox.  It initially
// plays quite badly, but learns from its mistakes.  

// There are two files required.  "fmg2.memory" is initially 165 rows of 11 zeros each.
// "fmg.board" is always as follows.  2 means a legal move for the police. Non-zero means
//  a legal move for theFox. 

//	0 2 2 2 0 0 0 0 0 0 0
//	1 0 2 0 2 2 0 0 0 0 0
//	1 2 0 2 0 2 0 0 0 0 0
//	1 0 2 0 0 2 2 0 0 0 0
//	0 1 0 0 0 2 0 2 0 0 0
//	0 1 1 1 2 0 2 2 2 2 0
//	0 0 0 1 0 2 0 0 0 2 0
//	0 0 0 0 1 1 0 0 2 0 2
//	0 0 0 0 0 1 0 2 0 2 2
//	0 0 0 0 0 1 1 0 2 0 2
//	0 0 0 0 0 0 0 1 1 1 0

//  The game has exactly 165 legal positions for the Police. 

// The user may resign a game by typing 0 0 for a move.  

static const int maxMoves = 20;

static Array2 <int>layout(11,11);
static Array <int>allMoves(165);
static Array2 <int>thisGame(maxMoves,2);
static Array2<int> board(165,11); // Memory of all games.
static Array <int>policePosition(3); // Position of the police.
static int theFox; // Position of the fox.
static Array<char> boardCells(11); // What is displayed in each cell when drawing.

long pwr(int x)  // Computes 2 to the (x).  
{	long result = 1;
	for (int i = 0; i < x; i++)
		result *=2;
	return result;	
}

void setup()
{  	int i = 0;
	int L;
	for ( L = 0; L<9; ++L)
	{	int L1 = pwr(L);
		for (int M = L+1; M<10; ++M)
		{	int M1 = pwr(M);
			for (int R = M+1; R<11; R++)
				allMoves[i++] = L1 + M1 + pwr(R);
		}
	}
	for(L = 0; L<maxMoves; ++L)
	for(int M = 0; M<2; ++M)
		thisGame(L,M) = 0;
	theFox = 5;
	policePosition[0] = 0;
	policePosition[1] = 1;
	policePosition[2] = 3;
}

void readFiles(Boolean smart)
{	ifstream boardFile("fmg.board");
	ifstream memoryFile("fmg2.memory");
	int i;
	for (i = 0; i<11; ++i)
	for (int j = 0; j<11; ++j)
		boardFile >> layout(i,j);
	for (i = 0; i<165; ++i)
	for (int j = 0; j<11; ++j)
		if(smart)memoryFile >> board(i,j);
		else board(i,j) = 0;
}

Boolean legalWhite(int x, int y)
{	if (theFox == y) return FALSE; // Already occupied by theFox.
	int here = -1;
	int i;
	for(i = 0; i<3; ++i)
		if(policePosition[i] == x) here = i;
	if(here<0) return FALSE; // Police not at x now.
	for (i = 0; i<3; ++i)
		if(policePosition[i] == y) return FALSE; // Already Police.
	if (layout(x,y) != 2) return FALSE; // No such move for the police.
	policePosition[here] = y;
	return true;
}

int genWhiteValue()
{	int a = pwr(policePosition[0]) 
			+ pwr(policePosition[1]) 
			+ pwr(policePosition[2]);
	for(int s = 0; s<165; ++s)
		if (allMoves[s] == a) return s;
	return 0; // Never here.
}

void summarize(int moves, int outcome)
{ 	for(int i = 0; i<moves; ++i)
	{	int s = thisGame(i,0);
		int m = thisGame(i,1);
		board(s,m) = board(s,m) + outcome;	
	}
}

int optimalBlack(int policeEntry)
{	int result = -1;
	int i,j;
	for (i = 0; i<11; ++i) // Check each position.
	{	if(layout(theFox,i) != 0) // Legal move.
		{	Boolean occupied = FALSE;
			for(j = 0; j<3; ++j) // See if policeEntry is already there.
				if(policePosition[j] == i) occupied = true; 
			if(!occupied)
			{	if (result < 0) result = i; // Prime the search.
				else if(board(policeEntry,result) < board(policeEntry,i))
							result = i;// New best move.
			}
		}
	}
	return result;
}

void drawBoard() // Output formatting assumes a mono width font.  
{	int i; 
	for(i = 0; i<11; i++)
	{	boardCells[i] = char(i+'0'); // Slot 10 is a ":".  
	}
	for(i = 0; i<3; i++)
	{	boardCells[policePosition[i]] = 'P';
	}
	boardCells[theFox] = 'F';
	cout << "      "<<boardCells[1]<<"--"<<boardCells[4]<<"--"<<boardCells[7]<<endl;
	cout << "     /|\\ | /|\\"<<endl;
	cout << "    / | \\|/ | \\"<<endl;
	cout << "   "<<boardCells[0]<<"--"<<boardCells[2]<<"--"<<boardCells[5]<<"--"<<
				boardCells[8]<<"--"<<boardCells[10]<<endl;
	cout << "    \\ | /|\\ | /"<<endl;
	cout << "     \\|/ | \\|/"<<endl;
	cout << "      "<<boardCells[3]<<"--"<<boardCells[6]<<"--"<<boardCells[9]<<endl;

}

void play()
{	int x,y; // Police's move: from, to.  
	int moves = 0; // Move number.
	int winValue = 1; // 1 for Fox win, -1 for Police win. 
	Boolean resigned = false, won = false, lost = false;
	do 
	{	drawBoard();
		cout << "Police at " << policePosition[0]<< ' '<< policePosition[1]<< ' '<< policePosition[2]<< endl;
		cout << "Fox is at " << theFox << endl <<endl;
		cout << "Your move from x to y. ";
		cin >> x >> y;
		if(x == 0 && y == 0) resigned = true; // User resigns.  
		if(moves >= maxMoves) 
		{	resigned = true;
			cout << maxMoves << "  move limit exceeded."<<endl;
		}
		if(!resigned)
			if(legalWhite(x,y))
			{	int policeMove = genWhiteValue();
				int theFoxMove = optimalBlack(policeMove);
				cout << "Machine moves to "<<theFoxMove<<endl;
				if(theFoxMove < 0) lost = true; // Machine loses.
				else
				{	thisGame(moves,0) = policeMove;
					thisGame(moves,1) = theFoxMove;
					theFox = theFoxMove;
					moves++;
				}
			}
			else cout << "Illegal."<<endl;
			if(theFox == 0) won = true; // Machine wins. 
	}while (!resigned && !won && !lost);
	moves--;
	if (resigned || won) 
		cout << "Machine wins."<<endl;
	else
	{	cout << "You win."<<endl;
		winValue = -1;
	}
	summarize(moves, winValue);		
}

void writeFiles()
{	ofstream memoryFile("fmg2.memory");
	for (int i = 0; i<165; ++i)
	{	for (int j = 0; j<11; ++j)
			memoryFile << board(i,j)<<' ';
		memoryFile << endl;
	}
}

void FMGMain (Boolean smart, Boolean learn)
{ 	Boolean moregames = TRUE;
	readFiles(smart);
	do
	{	setup();
		play();
		cout <<endl<< "Play again? 0 = no" <<endl;
#ifdef __intBOOL__
		cin >> moregames;  // BORLAND chanage to: cin >> int(moregames);
#else
		cin >> int(moregames);
#endif 
	}while (moregames);
	if(learn)writeFiles(); // Omit this to prevent learning between sessions.
}