/*++

Module Name:

    ttt.c

Abstract:

    tic tac toe program to illustrate simple minimax searching

Author:

    Scott Gasch (SGasch) 18 Mar 2004

Revision History:

    ver0 : random play
    ver1 : simple search
    ver2 : alpha beta search
    ver3 : added eval and depth on ab search, more efficient gaveover
    ver4 : variable sized board

--*/

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <time.h>
#include "ttt.h"

SQUARE g_sComputerPlays = O_MARK;             // what side comp plays
unsigned int g_uPly = 0;
MOVE g_mvBest = { 0 };
unsigned int g_uNodes = 0;
COORD g_uBoardSize = 3;

//+----------------------------------------------------------------------------
//
// Function:  SquareContentsToChar
//
// Synopsis:  Helper function for DrawBoard
//
// Arguments: IN SQUARE s - a square to return a char to represent
//            
// Returns:   char - character representing square
//
//+----------------------------------------------------------------------------
char SquareContentsToChar(IN SQUARE s)
{
    static char c;
    switch(s)
    {
        case X_MARK:
            c = 'X';
            break;
        case O_MARK:
            c = 'O';
            break;
        case EMPTY:
            c = '_';
            break;
        default:
            ASSERT(FALSE);
            c = '?';
            break;
    }
    return(c);
}

//+----------------------------------------------------------------------------
//
// Function:  DrawBoard
//
// Synopsis:  Draw the board
//
// Arguments: IN POSITION *p - pointer to a position whose board to draw
//            
// Returns:   void
//
//+----------------------------------------------------------------------------
void DrawBoard(IN POSITION *p)
{
    COORD x, y;

    for (y = 0; y < g_uBoardSize; y++)
    {
        for (x = 0; x < g_uBoardSize; x++)
        {
            printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
        }
#ifdef DEBUG
        printf(" = %d\n", p->iVSums[y]);
#else
        printf("\n");
#endif
    }

#ifdef DEBUG
    for (x = 0; x < g_uBoardSize; x++)
    {
        printf("| ");
    }
    printf("\n");
    for (x = 0; x < g_uBoardSize; x++)
    {
        printf("%d ", p->iHSums[x]);
    }
    printf("\t%d %d\n", p->iDSums[0], p->iDSums[1]);
    printf("\n");
#endif

    ASSERT(X_OR_O(p->sWhoseTurn));
    printf("\n%c to move.\n", SquareContentsToChar(p->sWhoseTurn));
}

//+----------------------------------------------------------------------------
//
// Function:  ClearBoard
//
// Synopsis:  Clear the board
//
// Arguments: IN OUT POSITION *p - pointer to position whose board to clear
//            
// Returns:   void
//
//+----------------------------------------------------------------------------
void ClearBoard(IN OUT POSITION *p)
{
    COORD h;

    for (h = 0; h < g_uBoardSize; h++)
    {
        memset(p->sBoard[h], 0, sizeof(int) * g_uBoardSize);
    }
    memset(p->iHSums, 0, sizeof(int) * g_uBoardSize);
    memset(p->iVSums, 0, sizeof(int) * g_uBoardSize);
    p->iDSums[0] = p->iDSums[1] = 0;
    p->sWhoseTurn = X_MARK;                   // x's go first
    p->uNumEmpty = (g_uBoardSize * g_uBoardSize);
}

//+----------------------------------------------------------------------------
//
// Function:  IsLegalMove
//
// Synopsis:  Determine if a given move is legal on a given board
//
// Arguments: IN POSITION *p - the board to play the move on
//            IN MOVE *m - the move in question
//            
// Returns:   BOOL - TRUE if it's legal, FALSE otherwise
//
//+----------------------------------------------------------------------------
BOOL IsLegalMove(IN POSITION *p, IN MOVE *m)
{
    if ((m->cVpos < g_uBoardSize) && (m->cHpos < g_uBoardSize))
    {
        if (IS_SQUARE_EMPTY(p->sBoard[m->cVpos][m->cHpos]))
        {
            return(TRUE);
        }
    }
    return(FALSE);
}

//+----------------------------------------------------------------------------
//
// Function:  GetHumanMove
//
// Synopsis:  Ask the human for a move
//
// Arguments: IN POSITION *p - the current board
//            OUT MOVE *m - the move the human made; this struct is populated
//                      as a side-effect of this function.
//            
// Returns:   void* (populates the move struct)
//
//+----------------------------------------------------------------------------
void GetHumanMove(IN POSITION *p, OUT MOVE *m)
{
    unsigned int x;

    do
    {
        printf("Enter your move number: ");
        scanf("%u", &x);
        
        m->cHpos = NUM_TO_HPOS(x);
        m->cVpos = NUM_TO_VPOS(x);
        m->sMark = OPPOSITE_MARK(g_sComputerPlays);
    }
    while(FALSE == IsLegalMove(p, m));
}


//+----------------------------------------------------------------------------
//
// Function:  GameOver
//
// Synopsis:  Is the game over? 
//
// Arguments: IN POSITION *p - the board
//            OUT SQUARE *psWhoWon - who won the game (if it's over)
//            
// Returns:   TRUE if the game is over.  Also sets psWhoWon telling
//            which side one if the game is over.  This also serves
//            as a very simple evaluation routine for the search.
// 
//            FALSE if the game is not over.
//
//+----------------------------------------------------------------------------
BOOL GameOver(IN POSITION *p, OUT SQUARE *psWhoWon)
{
    int iSum;
    COORD x;
    unsigned int uFull = (g_uBoardSize * g_uBoardSize) - p->uNumEmpty;

    //
    // The game can't be over if less than g_uBoardSize * 2 - 1 marks on it
    //
    if (uFull < (g_uBoardSize * 2 - 1))
    {
        *psWhoWon = EMPTY;
        return(FALSE);
    }

    for (x = 0; x < g_uBoardSize; x++)
    {
        iSum = p->iHSums[x];
        if (abs(iSum) == g_uBoardSize) goto winner;

        iSum = p->iVSums[x];
        if (abs(iSum) == g_uBoardSize) goto winner;
    }

    iSum = p->iDSums[0];
    if (abs(iSum) == g_uBoardSize) goto winner;

    iSum = p->iDSums[1];
    if (abs(iSum) == g_uBoardSize) goto winner;

    //
    // No one won yet, either game ongoing or draw.
    //
    *psWhoWon = EMPTY;
    if (p->uNumEmpty == 0)
    {
        return(TRUE);
    }
    else
    {
        return(FALSE);
    }

 winner:
    //
    // Some side won
    //
    *psWhoWon = (iSum / (int)g_uBoardSize);
    ASSERT(X_OR_O(*psWhoWon));
    return(TRUE);
}


//+----------------------------------------------------------------------------
//
// Function:  CountAdjacents
//
// Synopsis:  Return the number of marks in adjacent squares to square x
//            that are of the same type (x or o) as the mark in square x.
//  
//            FIXME: does not consider diagonals
//
// Arguments: IN POSITION *p - the board
//            IN SQUARE x - the square to test
//            
// Returns:   A count
//
//+----------------------------------------------------------------------------
unsigned int CountAdjacents(IN POSITION *p, IN COORD x)
{
    COORD v = NUM_TO_VPOS(x);
    COORD h = NUM_TO_HPOS(x);
    SQUARE sSide = p->sBoard[h][v];
    unsigned int uCount = 0;

    //
    // If nothing at square x, nothing to count
    //
    if (sSide == EMPTY) goto end;

    //
    // Look above, below, left and right
    //
    if ((v > 0) && (p->sBoard[h][v-1] == sSide))
    {
        uCount++;
    }

    if ((v < (g_uBoardSize - 1)) && (p->sBoard[h][v+1] == sSide))
    {
        uCount++;
    }

    if ((h > 0) && (p->sBoard[h-1][v] == sSide))
    {
        uCount++;
    }

    if ((h < (g_uBoardSize - 1)) && (p->sBoard[h+1][v] == sSide))
    {
        uCount++;
    }

 end:
    ASSERT(0 <= uCount);
    ASSERT(uCount <= 4);
    return(uCount);
}


//+----------------------------------------------------------------------------
//
// Function:  Eval
//
// Synopsis:  Evaluate a position
//
// Arguments: IN POSITION *p - the board
//            
// Returns:   A score
//
//+----------------------------------------------------------------------------
int Eval(IN POSITION *p)
{
    SQUARE sWinner;
    COORD x;
    SQUARE sMark;
    int iScore = 0;

    //
    // See if the game is already over.
    //
    if (TRUE == GameOver(p, &sWinner))
    {
        if (sWinner == p->sWhoseTurn)
        {
            iScore = +INFINITY - g_uPly;
            goto end;
        }
        else if (sWinner == OPPOSITE_MARK(p->sWhoseTurn))
        {
            iScore = -INFINITY + g_uPly;
            goto end;
        }
        iScore = DRAWSCORE;
        goto end;
    }

    //
    // No one won but instead of returning score=0 see if we can
    // find some "good characteristics" or "bad characteristics" 
    // of the position and give bonuses / penalties.
    //
    for (x = g_uBoardSize + 1; 
         x < ((g_uBoardSize * g_uBoardSize) - g_uBoardSize - 1);
         x++)
    {
        sMark = p->sBoard[NUM_TO_HPOS(x)][NUM_TO_VPOS(x)];
        if (sMark == p->sWhoseTurn)
        {
            iScore += CountAdjacents(p, x);
        }
        else if (sMark == OPPOSITE_MARK(p->sWhoseTurn))
        {
            iScore -= CountAdjacents(p, x);
        }
    }

 end:
    ASSERT(-INFINITY <= iScore);
    ASSERT(iScore <= +INFINITY);
    return(iScore);
}



//+----------------------------------------------------------------------------
//
// Function:  MakeMove
//
// Synopsis:  Make a move on a board  
//
// Arguments: IN OUT POSITION *p - the board
//            IN MOVE *m - the move
//            
// Returns:   void
//
//+----------------------------------------------------------------------------
void MakeMove(IN OUT POSITION *p, IN MOVE *m)
{
    if (TRUE == IsLegalMove(p, m))
    {
        //
        // Make the new make on the board
        //
        ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
        p->sBoard[m->cVpos][m->cHpos] = m->sMark;

        //
        // One less empty square
        //
        p->uNumEmpty--;
        ASSERT(p->uNumEmpty < (g_uBoardSize * g_uBoardSize));

        //
        // Update sums as appropriate
        //
        p->iHSums[m->cHpos] += m->sMark;
        ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
        p->iVSums[m->cVpos] += m->sMark;
        ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
        if (m->cHpos == m->cVpos)
        {
            p->iDSums[0] += m->sMark;
            ASSERT(VALID_SUM(p->iDSums[0]));
        }
        if (m->cVpos == ((g_uBoardSize - m->cHpos) - 1))
        {
            p->iDSums[1] += m->sMark;
            ASSERT(VALID_SUM(p->iDSums[1]));
        }

        //
        // Other guy's turn
        //
        p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
        ASSERT(X_OR_O(p->sWhoseTurn));

        //
        // One ply deeper
        //
        g_uPly++;
        ASSERT(g_uPly > 0);
    }
}

//+----------------------------------------------------------------------------
//
// Function:  UnmakeMove
//
// Synopsis:  The opposite of MakeMove
//
// Arguments: IN OUT POSITION *p - the board
//            IN MOVE *m - the move to undo
//            
// Returns:   void
//
//+----------------------------------------------------------------------------
void UnmakeMove(IN OUT POSITION *p, IN MOVE *m)
{
    if (p->sBoard[m->cVpos][m->cHpos] == m->sMark)
    {
        p->sBoard[m->cVpos][m->cHpos] = EMPTY;

        //
        // One more empty square
        //
        p->uNumEmpty++;
        ASSERT(p->uNumEmpty > 0);
        ASSERT(p->uNumEmpty <= (g_uBoardSize * g_uBoardSize));

        //
        // Update sums as appropriate
        //
        p->iHSums[m->cHpos] -= m->sMark;
        ASSERT(VALID_SUM(p->iHSums[m->cHpos]));
        p->iVSums[m->cVpos] -= m->sMark;
        ASSERT(VALID_SUM(p->iVSums[m->cVpos]));
        if (m->cHpos == m->cVpos)
        {
            p->iDSums[0] -= m->sMark;
            ASSERT(VALID_SUM(p->iDSums[0]));
        }
        if (m->cVpos == ((g_uBoardSize - m->cHpos) - 1))
        {
            p->iDSums[1] -= m->sMark;
            ASSERT(VALID_SUM(p->iDSums[1]));
        }

        //
        // Other guy's turn
        //
        p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
        ASSERT(X_OR_O(p->sWhoseTurn));

        //
        // One ply deeper
        //
        ASSERT(g_uPly > 0);
        g_uPly--;
    }
}


//+----------------------------------------------------------------------------
//
// Function:  AlphaBeta
//
// Synopsis:  An AlphaBeta Search
//
// Arguments: IN OUT POSITION *p - the board
//            IN int iAlpha - the lower bound of the score window
//            IN int iBeta - the upper bound of the score window
//            IN int uDepth - search depth horizon
//
// Returns:   int
//
//+----------------------------------------------------------------------------
int 
AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta, IN unsigned int uDepth)
{
    SQUARE sWhoWon;
    COORD s;
    MOVE mv;
    int iScore;
    int iBestScore = -INFINITY - 2;

    g_uNodes++;

    //
    // Evaluate this position
    //
    if (TRUE == GameOver(p, &sWhoWon))
    {
        if (sWhoWon == p->sWhoseTurn)
        {
            return(+INFINITY - g_uPly);
        }
        else if (sWhoWon == (p->sWhoseTurn * -1))
        {
            return(-INFINITY + g_uPly);
        }
        return(DRAWSCORE);
    }
    else if (uDepth == 0)
    {
        return(0);//Eval(p));
    }

    //
    // No one won, game is still going.  Evaluate every
    // possible move from here.
    //
    ASSERT(p->uNumEmpty > 0);
    for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
    {
        mv.cHpos = NUM_TO_HPOS(s);
        mv.cVpos = NUM_TO_VPOS(s);
        mv.sMark = p->sWhoseTurn;

        if (IsLegalMove(p, &mv))
        {
            MakeMove(p, &mv);

            iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uDepth - 1);
            ASSERT(-INFINITY <= iScore);
            ASSERT(iScore <= +INFINITY);

            UnmakeMove(p, &mv);
            
            //
            // Fail high
            //
            if (iScore >= iBeta)
            {
                return(iScore);
            }
            
            if (iScore > iBestScore)
            {
                iBestScore = iScore;
                
                if (iScore > iAlpha)
                {
                    //
                    // PV node
                    //
                    iAlpha = iScore;
                    
                    //
                    // If this is the ply 0 move, remember it.
                    //
                    if (g_uPly == 0)
                    {
                        g_mvBest = mv;
                    }
                }
            }
        }
    }
    return(iBestScore);
}


//+----------------------------------------------------------------------------
//
// Function:  SimpleSearch
//
// Synopsis:  A Simple Search
//
// Arguments: IN OUT POSITION *p - the board
//
// Returns:   int
//
//+----------------------------------------------------------------------------
int
SimpleSearch(IN POSITION *p)
{
    SQUARE sWhoWon;
    COORD s;
    MOVE mv;
    int iScore;
    int iBestScore = -INFINITY;
    
    g_uNodes++;

    //
    // Evaluate this position
    //
    if (TRUE == GameOver(p, &sWhoWon))
    {
        if (sWhoWon == p->sWhoseTurn)
        {
            return(+INFINITY - g_uPly);
        }
        else if (sWhoWon == (p->sWhoseTurn * -1))
        {
            return(-INFINITY + g_uPly);
        }
        return(DRAWSCORE);
    }

    //
    // No one won, game is still going.  Evaluate every
    // possible move from here.
    //
    ASSERT(p->uNumEmpty > 0);
    for (s = 0; s < (g_uBoardSize * g_uBoardSize); s++)
    {
        mv.cHpos = NUM_TO_HPOS(s);
        mv.cVpos = NUM_TO_VPOS(s);
        mv.sMark = p->sWhoseTurn;

        if (IsLegalMove(p, &mv))
        {
            MakeMove(p, &mv);

            iScore = -1 * SimpleSearch(p);
            if (iScore > iBestScore)
            {
                iBestScore = iScore;
                if (g_uPly == 1)
                {
                    g_mvBest = mv;
                }
            }
            UnmakeMove(p, &mv);
        }
    }
    return(iBestScore);
}

//+----------------------------------------------------------------------------
//
// Function:  SearchForComputerMove
//
// Synopsis:  Use our sophisticated search algorithm to find a computer
//            move
//
// Arguments: IN POSITION *p - the current board
//            OUT MOVE *m - the move the computer chooses; this move struct
//                      is populated as a side-effect of this function.
//            
// Returns:   void* (populates move struct)
//
//+----------------------------------------------------------------------------
void SearchForComputerMove(IN POSITION *p, OUT MOVE *m)
{
#if defined(PLAY_RANDOMLY)
    unsigned int x;

    do
    {
        x = rand() % (g_uBoardSize * g_uBoardSize);
        m->cHpos = NUM_TO_HPOS(x);
        m->cVpos = NUM_TO_VPOS(x);
        m->sMark = g_sComputerPlays;
    }
    while(FALSE == IsLegalMove(p, m));

#elif defined(SIMPLE_SEARCH)

    g_uPly = g_uNodes = 0;
    SimpleSearch(p);
    *m = g_mvBest;
    printf("Searched %u node(s).\n", g_uNodes);

#elif defined(ALPHA_BETA_SEARCH)

    g_uPly = g_uNodes = 0;
    AlphaBeta(p, -INFINITY-1, +INFINITY+1, g_uBoardSize * 2);
    *m = g_mvBest;
    printf("Searched %u node(s).\n", g_uNodes);

#else

    #error "No Search Strategy Defined"

#endif
}

//+----------------------------------------------------------------------------
//
// Function:  main
//
// Synopsis:  The program entry point and main game loop.
//
// Arguments: void
//            
// Returns:   int
//
//+----------------------------------------------------------------------------
int 
main(void)
{
    POSITION p;
    MOVE mv;
    SQUARE sResult;
    unsigned int u;

    //
    // Randomize: the random numbers returned by rand() will be based on
    // the system clock when the program starts up.
    //
    srand(time(0));

    //
    // Make the board
    //
    do
    {
        printf("How big do you want the board (2..20)? ");
        scanf("%u", &g_uBoardSize);
    }
    while((g_uBoardSize < 2) || (g_uBoardSize > 20));

    //
    // Allocate space for 2d int array ptr
    //
    p.sBoard = (int **)malloc(g_uBoardSize * sizeof(int *));
    if (NULL == p.sBoard)
    {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }

    //
    // Allocate each row of the array
    //
    for (u = 0; u < g_uBoardSize; u++)
    {
        p.sBoard[u] = (int *)
            malloc(g_uBoardSize * sizeof(int));
        if (NULL == p.sBoard[u])
        {
            fprintf(stderr, "Out of memory!\n");
            exit(1);
        }
    }

    //
    // Allocate space for sums
    //
    p.iHSums = (int *)malloc(g_uBoardSize * sizeof(int));
    p.iVSums = (int *)malloc(g_uBoardSize * sizeof(int));
    if ((NULL == p.iHSums) ||
        (NULL == p.iVSums))
    {
        fprintf(stderr, "Out of memory!\n");
        exit(1);
    }

    //
    // Setup the board and draw it once.
    //
    ClearBoard(&p);
    DrawBoard(&p);

    //
    // Main game loop
    //
    do
    {
        // 
        // See whose turn it is -- the human's or the computers -- and
        // get a move from whoever's turn it is.
        //
        if (p.sWhoseTurn == g_sComputerPlays)
        {
            SearchForComputerMove(&p, &mv);
        }
        else
        {
            GetHumanMove(&p, &mv);
        }

        //
        // Make the move on the board and draw the board again.
        //
        MakeMove(&p, &mv);
        DrawBoard(&p);
    }
    while(FALSE == GameOver(&p, &sResult));

    //
    // If we get here the game is over... see what happened.
    //
    switch(sResult)
    {
        case X_MARK:
            printf("\nX's win.\n");
            break;
        case O_MARK:
            printf("\nO's win.\n");
            break;
        default:
            printf("Tie (what a surprise)\n");
            break;
    }

    //
    // TODO: cleanup heap
    //
    
    exit(0);
}