Initial checking of tic tac toe minimax tutorial code.

2 files changed, 939 insertions, 0 deletions

diff --git a/ver4/ttt.c b/ver4/ttt.c
new file mode 100644
index 0000000..4dd54a6
--- /dev/null
+++ b/ver4/ttt.c
@@ -0,0 +1,846 @@
+/*++
+
+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);
+}
diff --git a/ver4/ttt.h b/ver4/ttt.h
new file mode 100644
index 0000000..6ddee35
--- /dev/null
+++ b/ver4/ttt.h
@@ -0,0 +1,93 @@
+#ifndef TTT_H_
+#define TTT_H_
+
+#define ALPHA_BETA_SEARCH 1
+
+#define TRUE (1)
+#define FALSE (0)
+
+#define IN
+#define OUT
+
+typedef unsigned int BOOL;
+
+//
+// Constants for each state a board square can be in and a programmer
+// defined type for these states.
+//
+#define X_MARK (-1)
+#define EMPTY  (0)
+#define O_MARK (+1)
+#define TIE    (+2)
+#define OPPOSITE_MARK(m) ((m) * -1)
+#define X_OR_O(m) (((m) == X_MARK) || \
+                   ((m) == O_MARK))
+
+typedef signed char SQUARE;
+#define IS_SQUARE_EMPTY(x) (x == EMPTY)
+
+//
+// A (simple) representation of a tic tac toe position
+//
+typedef struct _POSITION
+{
+    SQUARE sWhoseTurn;
+    int **sBoard;
+    //SQUARE sBoard[BOARD_SIZE][BOARD_SIZE];
+    int *iVSums;
+    //int iVSums[BOARD_SIZE];
+    int *iHSums;
+    //int iHSums[BOARD_SIZE];
+    int iDSums[2];
+    unsigned int uNumEmpty;
+} POSITION;
+
+#define NUM_TO_HPOS(x)   ((x) % g_uBoardSize)
+#define NUM_TO_VPOS(x)   ((x) / g_uBoardSize)
+#define VALID_SUM(x)     (abs(x) <= g_uBoardSize)
+
+//
+// A representation of a move in a tic tac toe game
+//
+typedef unsigned int COORD;
+
+typedef struct _MOVE
+{
+    COORD cHpos;
+    COORD cVpos;
+    SQUARE sMark;
+} MOVE;
+
+//
+// Score values
+//
+#define INFINITY (+100)
+#define DRAWSCORE (0)
+
+//
+// An assert mechanism
+//
+#ifdef DEBUG
+#define ASSERT(x)       if (x)    \
+                        { ; }     \
+                        else      \
+                        { (void) _assert(__FILE__, __LINE__); }
+#else
+#define ASSERT(x)       ;
+#endif /* DEBUG */
+
+ 
+void
+_assert(char *sz, unsigned int i)
+{
+    fprintf(stderr, "Assertion failed in %s at line %u.\n", sz, i);
+#if defined(WIN32)
+	__asm int 3;
+#elif defined(__unix__)
+    asm("int3\n");
+#else
+    #error foo
+#endif
+}
+
+#endif /* TTT_H_ */