// NoughtsDoc.cpp : implementation of the CNoughtsDoc class
//

#include "stdafx.h"
#include "Noughts.h"
#include "NoughtsDoc.h"
#include "Statistics.h"
#include "mmsystem.h"

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

    int Square;		// return value from Steve's code
	CString sDescription;		// description from Steve's code
	int BestScore;

/* This code is slightly modified from the :

  Tic-Tac-Toe program by Steve Chapel schapel@cs.ucsb.edu
  that I downloaded from programmersheaven.com

*/

#include <stdio.h>
#include <ctype.h>

#define String_Length 80

#define Squares 9
typedef char Square_Type;
typedef Square_Type Board_Type[Squares];
const Square_Type Empty = ' ';

const int Infinity = 10;		/* Higher value than any score */
const int Maximum_Moves = Squares;	/* Maximum moves in a game */

int Total_Nodes;			/* Nodes searched with minimax */

/* Array describing the eight combinations of three squares in a row */
#define Possible_Wins 8
const int Three_in_a_Row[Possible_Wins][3] = {
    { 0, 1, 2 },
    { 3, 4, 5 },
    { 6, 7, 8 },
    { 0, 3, 6 },
    { 1, 4, 7 },
    { 2, 5, 8 },
    { 0, 4, 8 },
    { 2, 4, 6 }
};

/* Array used in heuristic formula for each move. */
const int Heuristic_Array[4][4] = {
    {     0,   -10,  -100, -1000 },
    {    10,     0,     0,     0 },
    {   100,     0,     0,     0 },
    {  1000,     0,     0,     0 }
};

/* Structure to hold a move and its heuristic */
typedef struct {
    int Square;
    int Heuristic;
} Move_Heuristic_Type;

/* Clear the board */
void Initialize(Board_Type Board) {
    int I;
    for (I = 0; I < Squares; I++)
	Board[I] = Empty;
}

void Describe(int Score) {
    if (Score < 0)
	sDescription = "I can win now.";
    else if (Score == 0)
	sDescription = "I can force a tie.";
    else
	{
		char buffer[33];
		sDescription = "I have a guaranteed win by move ";
		sDescription += _itoa(Maximum_Moves - Score + 1, buffer, 10);
	}
}
/* If a player has won, return the winner. If the game is a tie,
   return 'C' (for cat). If the game is not over, return Empty. */
Square_Type Winner(Board_Type Board) {
    int I;
    for (I = 0; I < Possible_Wins; I++) {
	Square_Type Possible_Winner = Board[Three_in_a_Row[I][0]];
	if (Possible_Winner != Empty &&
	    Possible_Winner == Board[Three_in_a_Row[I][1]] &&
	    Possible_Winner == Board[Three_in_a_Row[I][2]])
	    return Possible_Winner;
    }

    for (I = 0; I < Squares; I++)
	if (Board[I] == Empty)
	    return Empty;

    return 'C';
}

/* Return the other player */
Square_Type Other(Square_Type Player) {
    return Player == 'X' ? 'O' : 'X';
}

/* Make a move on the board */
void Play(Board_Type Board, int Square, Square_Type Player) {
    Board[Square] = Player;
}

/* Return a heuristic used to determine the order in which the
   children of a node are searched */
int Evaluate(Board_Type Board, Square_Type Player) {
    int I;
    int Heuristic = 0;
    for (I = 0; I < Possible_Wins; I++) {
	int J;
	int Players = 0, Others = 0;
	for (J = 0; J < 3; J++) {
	    Square_Type Piece = Board[Three_in_a_Row[I][J]];
	    if (Piece == Player)
		Players++;
	    else if (Piece == Other(Player))
		Others++;
	}
	Heuristic += Heuristic_Array[Players][Others];
    }
    return Heuristic;
}

/* Return the score of the best move found for a board
   The square to move to is returned in *Square */
int Best_Move(Board_Type Board, Square_Type Player, int *Square, int Move_Nbr,
	      int Alpha, int Beta) {
    int Best_Square = -1;
    int Moves = 0;
    int I;
    Move_Heuristic_Type Move_Heuristic[Squares];

    Total_Nodes++;

    /* Find the heuristic for each move and sort moves in descending order */
    for (I = 0; I < Squares; I++) {
	if (Board[I] == Empty) {
	    int Heuristic;
	    int J;
	    Play(Board, I, Player);
	    Heuristic = Evaluate(Board, Player);
	    Play(Board, I, Empty);
	    for (J = Moves-1; J >= 0 &&
			      Move_Heuristic[J].Heuristic < Heuristic; J--) {
		Move_Heuristic[J + 1].Heuristic = Move_Heuristic[J].Heuristic;
		Move_Heuristic[J + 1].Square = Move_Heuristic[J].Square;
	    }
	    Move_Heuristic[J + 1].Heuristic = Heuristic;
	    Move_Heuristic[J + 1].Square = I;
	    Moves++;
	}
    }

    for (I = 0; I < Moves; I++) {
	int Score;
	int Sq = Move_Heuristic[I].Square;
	Square_Type W;

	/* Make a move and get its score */
	Play(Board, Sq, Player);

	W = Winner(Board);
	if (W == 'X')
	    Score = (Maximum_Moves + 1) - Move_Nbr;
	else if (W == 'O')
	    Score = Move_Nbr - (Maximum_Moves + 1);
	else if (W == 'C')
	    Score = 0;
	else
	    Score = Best_Move(Board, Other(Player), Square, Move_Nbr + 1,
			      Alpha, Beta);

	Play(Board, Sq, Empty);

	/* Perform alpha-beta pruning */
	if (Player == 'X') {
	    if (Score >= Beta) {
		*Square = Sq;
		return Score;
	    } else if (Score > Alpha) {
		Alpha = Score;
		Best_Square = Sq;
	    }
	} else {
	    if (Score <= Alpha) {
		*Square = Sq;
		return Score;
	    } else if (Score < Beta) {
		Beta = Score;
		Best_Square = Sq;
	    }
	}
    }
    *Square = Best_Square;
    if (Player == 'X')
	return Alpha;
    else
	return Beta;
}

/* Have the human or the computer move */
void Move(Board_Type Board, Square_Type Player, int Move_Nbr) {

	Total_Nodes = 0;
	BestScore = Best_Move(Board, Player, &Square, Move_Nbr, -Infinity, Infinity);
}

/////////////////////////////////////////////////////////////////////////////
// CNoughtsDoc

IMPLEMENT_DYNCREATE(CNoughtsDoc, CDocument)

BEGIN_MESSAGE_MAP(CNoughtsDoc, CDocument)
	//{{AFX_MSG_MAP(CNoughtsDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
	ON_COMMAND(ID_FILE_SEND_MAIL, OnFileSendMail)
	ON_UPDATE_COMMAND_UI(ID_FILE_SEND_MAIL, OnUpdateFileSendMail)
END_MESSAGE_MAP()

BEGIN_DISPATCH_MAP(CNoughtsDoc, CDocument)
	//{{AFX_DISPATCH_MAP(CNoughtsDoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//      DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_DISPATCH_MAP
END_DISPATCH_MAP()

// Note: we add support for IID_INoughts to support typesafe binding
//  from VBA.  This IID must match the GUID that is attached to the 
//  dispinterface in the .ODL file.

// {4E346852-C7DD-11D2-8D7D-00104B11A479}
static const IID IID_INoughts =
{ 0x4e346852, 0xc7dd, 0x11d2, { 0x8d, 0x7d, 0x0, 0x10, 0x4b, 0x11, 0xa4, 0x79 } };

BEGIN_INTERFACE_MAP(CNoughtsDoc, CDocument)
	INTERFACE_PART(CNoughtsDoc, IID_INoughts, Dispatch)
END_INTERFACE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CNoughtsDoc construction/destruction

CNoughtsDoc::CNoughtsDoc()
{
	clearall();
	raised = rounded = autostart = TRUE;
	noswap = playerswap = FALSE;
	multipledirections = false;
	player1 = 0;
	player2 = 1;
}

CNoughtsDoc::~CNoughtsDoc()
{

}

BOOL CNoughtsDoc::OnNewDocument()
{
	clearall();
	if (!CDocument::OnNewDocument())
		return FALSE;

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CNoughtsDoc serialization

void CNoughtsDoc::Serialize(CArchive& ar)
{
	if (ar.IsStoring())
	{
	}
	else
	{
		// TODO: add loading code here
	}
}

/////////////////////////////////////////////////////////////////////////////
// CNoughtsDoc diagnostics

#ifdef _DEBUG
void CNoughtsDoc::AssertValid() const
{
	for (int c=0; c<9;c++)
		if ((statusbox[c]<0) | (statusbox[c]>2)) ASSERT(FALSE);

	ASSERT	(slash>-1);
	ASSERT  (slash<9);
	ASSERT  (winner>-1);
	ASSERT  (winner<3);

	CDocument::AssertValid();
}

void CNoughtsDoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CNoughtsDoc commands

void CNoughtsDoc::DeleteContents() 
{
	clearall();
	CDocument::DeleteContents();
}

void CNoughtsDoc::setbox(int box)
{
	if (int c=turn())
	{
		int	i=0;
		int j=0;
		for	(j=8;j>0;j--)
		{
			for (i=0;i<9;i++) {undoarray[j] [i]=undoarray[j-1] [i];}
		}
		for (i=0; i<9; i++) {undoarray[0] [i] = statusbox [i];}
		statusbox[box] = c;
		if (!slash)
		{
			int	winner=testslash();

			if ((count()==9) && (!winner && countwin)) 
			{
				statisticsbox.bwin++;
				statisticsbox.Invalidate(TRUE);
				statisticsbox.UpdateWindow();
			}

			if (winner && countwin) 
			{
				if (winner==1)
				{
					statisticsbox.cwin++;
					statisticsbox.Invalidate(TRUE);
					statisticsbox.UpdateWindow();
				}
				else 
				{
					statisticsbox.nwin++;
					statisticsbox.Invalidate(TRUE);
					statisticsbox.UpdateWindow();
				}			
				if (WinningPlayer()==1)
				{
					statisticsbox.player1win++;
					statisticsbox.Invalidate(TRUE);
					statisticsbox.UpdateWindow();
				}
				else
				{
					statisticsbox.player2win++;
					statisticsbox.Invalidate(TRUE);
					statisticsbox.UpdateWindow();
				}

			}

			PlaySound((LPCSTR)IDR_SOUND1, AfxGetInstanceHandle(), SND_RESOURCE | SND_NOWAIT );
			UpdateAllViews(NULL);

		}
	}

}

int	CNoughtsDoc::turn()
{
	if (winner) return 0;
	int	number=count();
	if (number>8) return 0;

	if (number & 0x00000001) 
		return 2;
	else 
		return 1;
}

int CNoughtsDoc::pturn()
{
	int result = turn();
	if (!result) return 0;
	else
	if (playerswap) 
	{
		if (result==1) return 2; else return 1;
	}
	else
		return result;
}

void CNoughtsDoc::undo()
{
	if (count())
	{
		int	i=0;
		int	j=0;

		for (i=0; i<9; i++) {statusbox [i] = undoarray[0] [i];}	

		for (j=1;j<9;j++)
		{
			for (i=0;i<9;i++) {undoarray[j-1] [i]=undoarray[j] [i];}
		}

		countwin=false;
		testslash();
		UpdateAllViews(NULL);
	}
}

int CNoughtsDoc::count()
{
	int	number=0;
	for (int c=0;c<9;c++)
		if (statusbox[c]) number++;

	return number;
}

void CNoughtsDoc::clearall()
{
	slash=0; 
	winner=0;
	SetModifiedFlag(FALSE);
	countwin=TRUE;
	if (!noswap) playerswap=!(playerswap);

	int	i;
	for (i=0; i<9; i++) statusbox[i]=0;
	int	j;
	for (j=0; j<9; j++)
	{
		for (i=0; i<9; i++) undoarray[j] [i] = 0;
	}
	UpdateAllViews(NULL);
	sDescription="";
}

int CNoughtsDoc::testslash()
{
	int	slashcount=0;
	int	wincolour=0;

	slash=0;
	int colour=statusbox[4];

	if ((statusbox[3]==statusbox[5]) && (statusbox[5]==colour) && colour) {slash=2; slashcount++; wincolour=colour;}
	if ((statusbox[1]==statusbox[7]) && (statusbox[7]==colour) && colour) {slash=5; slashcount++; wincolour=colour;}
	if ((statusbox[0]==statusbox[8]) && (statusbox[8]==colour) && colour) {slash=7; slashcount++; wincolour=colour;}
	if ((statusbox[2]==statusbox[6]) && (statusbox[6]==colour) && colour) {slash=8; slashcount++; wincolour=colour;}

	colour=statusbox[0];

	if ((statusbox[1]==statusbox[2]) && (statusbox[2]==colour) && colour) {slash=1; slashcount++; wincolour=colour;}
	if ((statusbox[3]==statusbox[6]) && (statusbox[6]==colour) && colour) {slash=4; slashcount++; wincolour=colour;}

	colour=statusbox[8];

	if ((statusbox[6]==statusbox[7]) && (statusbox[7]==colour) && colour) {slash=3; slashcount++; wincolour=colour;}
	if ((statusbox[2]==statusbox[5]) && (statusbox[5]==colour) && colour) {slash=6; slashcount++; wincolour=colour;}

	if (slashcount>1) multipledirections = true;
	else multipledirections = false;

	winner=wincolour;
	return winner;
}

void CNoughtsDoc::computerturn()
{
	if (((player1==1) && (pturn()==1)) | ((player2==1) && (pturn()==2)))

	{
		setbox(computemove(statusbox));
		Describe(BestScore);		// Create a description for printing
	}

	if (((player1==2) && (pturn()==1)) | ((player2==2) && (pturn()==2)))

	{
	setbox(randommove(statusbox));
	}

}

int	CNoughtsDoc::computemove(int box[9])
{
	int i=0;

	for (i=0; i<9; i++)
	{
		winme[i] = winthem[i] = winb[i] = 0;
	}
	
	int	count=0;
	int	decision=0;

	for (int c=0;c<9;c++)
	{
		if (box[c]) count++;
	}

	if (count==9) return 0;

	char mycolour;
	if (count & 0x00000001) mycolour = 'O';
	else mycolour = 'X';

	Board_Type board;
	for (int copy = 0; copy<9; copy++)
	{
		switch (box[copy])
		{
		case 0:
			board[copy] = ' ';
			break;
		case 1:
			board[copy] = 'X';
			break;
		case 2:
			board[copy] = 'O';
			break;
		default: abort();
		}
	}

	Move(board, mycolour, count+1);

	decision = Square;

	return decision;
}




int CNoughtsDoc::result()
{
	int	wincolour=0;

	int colour=statusbox[4];

	if (colour)
	{
		if ((statusbox[3]==statusbox[5]) && (statusbox[5]==colour)) wincolour=colour;
		if ((statusbox[1]==statusbox[7]) && (statusbox[7]==colour)) wincolour=colour;
		if ((statusbox[0]==statusbox[8]) && (statusbox[8]==colour)) wincolour=colour;
		if ((statusbox[2]==statusbox[6]) && (statusbox[6]==colour)) wincolour=colour;
	}

	colour=statusbox[0];

	if (colour)
	{
		if ((statusbox[1]==statusbox[2]) && (statusbox[2]==colour)) wincolour=colour;
		if ((statusbox[3]==statusbox[6]) && (statusbox[6]==colour)) wincolour=colour;
	}

	colour=statusbox[8];

	if (colour)
	{
		if ((statusbox[6]==statusbox[7]) && (statusbox[7]==colour)) wincolour=colour;
		if ((statusbox[2]==statusbox[5]) && (statusbox[5]==colour)) wincolour=colour;
	}
	return wincolour;
}





int CNoughtsDoc::randommove(int box[9])
{
	if (count()==9) return -1; // we're full

	srand( (unsigned)time( NULL ) );

	while (true)
	{
		float b = rand();
		b = b/RAND_MAX;
		b = b*20;
		int a = b-5;
		if ((a>-1) && (a<9))
		{
			if (!box[a]) return a;
		}
	}
}

int CNoughtsDoc::WinningPlayer()
{
	if (((winner==1) && (!playerswap)) | ((winner==2) && (playerswap)))
		return 1;
	else return 2;

}
