path: root/ver2/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

--*/

#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;

//+----------------------------------------------------------------------------
//
// 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 < BOARD_SIZE; y++)
    {
        for (x = 0; x < BOARD_SIZE; x++)
        {
            printf("%c ", SquareContentsToChar(p->sBoard[y][x]));
        }
        printf("\n");
    }
    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)
{
    memset(p->sBoard, 0, sizeof(p->sBoard));
    p->sWhoseTurn = X_MARK;                   // x's go first
    p->uNumEmpty = (BOARD_SIZE * BOARD_SIZE);
}

//+----------------------------------------------------------------------------
//
// 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 < BOARD_SIZE) && (m->cHpos < BOARD_SIZE))
    {
        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, y;

    for (x = 0; x < BOARD_SIZE; x++)
    {
        iSum = 0;

        for (y = 0; y < BOARD_SIZE; y++)
        {
            iSum += p->sBoard[x][y];
        }
        if (abs(iSum) == BOARD_SIZE) goto winner;
    }

    for (y = 0; y < BOARD_SIZE; y++)
    {
        iSum = 0;

        for (x = 0; x < BOARD_SIZE; x++)
        {
            iSum += p->sBoard[x][y];
        }
        if (abs(iSum) == BOARD_SIZE) goto winner;
    }

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

    iSum = 0;
    for (x = 0; x < BOARD_SIZE; x++)
    {
        iSum += p->sBoard[x][(BOARD_SIZE - 1 - x)];
    }
    if (abs(iSum) == BOARD_SIZE) goto winner;

    *psWhoWon = EMPTY;
    if (p->uNumEmpty == 0)
    {
        return(TRUE);
    }
    else
    {
        return(FALSE);
    }

 winner:
    *psWhoWon = (iSum / BOARD_SIZE);
    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))
    {
        ASSERT(p->sBoard[m->cVpos][m->cHpos] == EMPTY);
        p->sBoard[m->cVpos][m->cHpos] = m->sMark;
        p->uNumEmpty--;
        ASSERT(p->uNumEmpty < (BOARD_SIZE * BOARD_SIZE));
        p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
        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;
        p->uNumEmpty++;
        ASSERT(p->uNumEmpty > 0);
        ASSERT(p->uNumEmpty <= (BOARD_SIZE * BOARD_SIZE));
        p->sWhoseTurn = OPPOSITE_MARK(p->sWhoseTurn);
        ASSERT(g_uPly > 0);
        g_uPly--;
    }
}


int 
AlphaBeta(IN POSITION *p, IN int iAlpha, IN int iBeta)
{
    SQUARE sWhoWon;
    SQUARE 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 < (BOARD_SIZE * BOARD_SIZE); 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);

            UnmakeMove(p, &mv);
            
            if (iScore >= iBeta)
            {
                return(iScore);
            }

            if (iScore > iBestScore)
            {
                iBestScore = iScore;
                
                if (iScore > iAlpha)
                {
                    iAlpha = iScore;
                    if (g_uPly == 0)
                    {
                        g_mvBest = mv;
                    }
                }
            }
        }
    }
    return(iBestScore);
}


int
SimpleSearch(IN POSITION *p)
{
    SQUARE sWhoWon;
    SQUARE 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 < (BOARD_SIZE * BOARD_SIZE); 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)
{
    unsigned int x;

#if defined(PLAY_RANDOMLY)
    do
    {
        x = rand() % (BOARD_SIZE * BOARD_SIZE);
        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);
    *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;

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

    //
    // 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;
    }

    exit(0);
}