path: root/ver5/ttt.c

/*++

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
    ver5 : bugfixes, added singular extension to search

--*/

#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;
unsigned int g_uExtensions = 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:  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 (ON_DIAGONAL_1(m->cHpos, m->cVpos))
        {
            p->iDSums[0] += m->sMark;
            ASSERT(VALID_SUM(p->iDSums[0]));
        }
        if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
        {
            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 (ON_DIAGONAL_1(m->cHpos, m->cVpos))
        {
            p->iDSums[0] -= m->sMark;
            ASSERT(VALID_SUM(p->iDSums[0]));
        }
        if (ON_DIAGONAL_2(m->cHpos, m->cVpos))
        {
            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:  IsMoveSingular
//
// Synopsis:  Determine if a move is singular (i.e. only good move) or not
//
// Arguments: IN POSITION *p - the board
//            IN MOVE *m - the move to undo
//            
// Returns:   BOOL : TRUE if *m is singular
//
//+----------------------------------------------------------------------------
BOOL
IsMoveSingular(IN POSITION *p, IN MOVE *m)
{
    if ((abs(p->iVSums[m->cVpos]) >= (g_uBoardSize - 2)) ||
        (abs(p->iHSums[m->cHpos]) >= (g_uBoardSize - 2)))
    {
        return(TRUE);
    }
    if ((m->cHpos == m->cVpos) &&
        (abs(p->iDSums[0]) == (g_uBoardSize - 1)))
    {
        return(TRUE);
    }
    if ((m->cVpos == ((g_uBoardSize - m->cHpos) - 1)) &&
        (abs(p->iDSums[1] == (g_uBoardSize - 1))))
    {
        return(TRUE);
    }
    return(FALSE);
}


BOOL
IsMoveWorthSearching(POSITION *p, MOVE *m)
{
    signed int h;
    signed int v;
    unsigned int uSum = 0;

    for (h = m->cHpos - 1;
         h < (signed int)m->cHpos + 2;
         h++)
    {
        for (v = m->cVpos - 1;
             v < (signed int)m->cVpos + 2;
             v++)
        {
            if (GOOD_COORD((COORD)v) && GOOD_COORD((COORD)h))
            {
                uSum += abs(p->sBoard[v][h]);
            }
        }
    }
    
    if (uSum == 0)
    {
        return(FALSE);
    }
    return(TRUE);
}


int 
Eval(POSITION *p)
{
    int iSum = p->iDSums[0];
    COORD x;
    
    for (x = 0;
         x < g_uBoardSize;
         x++)
    {
        iSum += p->iHSums[x];
        iSum += p->iVSums[x];
    }
    iSum += p->iDSums[1];
    
    return(iSum * p->sWhoseTurn);
}


//+----------------------------------------------------------------------------
//
// 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;
    BOOL fMoveIsSingular;
    unsigned int uNextDepth;
    unsigned int uMoveNum = 1;
    
    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(Eval(p));
    }

    //
    // No one won, game is still going.  Evaluate some moves 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))
        {
            //
            // Determine if move is singular
            // 
            fMoveIsSingular = IsMoveSingular(p, &mv);
            
            if ((FALSE == fMoveIsSingular) &&
                (uMoveNum > 1))
            {
                //
                // Determine if we should bother with this subtree...
                // 
                if (FALSE == IsMoveWorthSearching(p, &mv))
                {
                    continue;
                }
            }
            
            //
            // Do it
            // 
            MakeMove(p, &mv);
            uMoveNum++;

            uNextDepth = uDepth - 1;
            if (TRUE == fMoveIsSingular)
            {
                uNextDepth = uDepth;
                g_uExtensions++;
            }
            iScore = -1 * AlphaBeta(p, -iBeta, -iAlpha, uNextDepth);
            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:  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(ALPHA_BETA_SEARCH)
    double dTime;
    
    g_uPly = g_uNodes = g_uExtensions = 0;
    
    AlphaBeta(p, -INFINITY-1, +INFINITY+1, 3);
    *m = g_mvBest;
    printf("Searched %u node(s), %u extension(s)\n", 
           g_uNodes, 
           g_uExtensions);
#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 = (SQUARE **)malloc(g_uBoardSize * sizeof(SQUARE *));
    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] = (SQUARE *)
            malloc(g_uBoardSize * sizeof(SQUARE));
        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
        {
            //SearchForComputerMove(&p, &mv);
            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);
}