Initial checking of tic tac toe minimax tutorial code.

2 files changed, 377 insertions, 0 deletions

diff --git a/ver0/ttt.c b/ver0/ttt.c
new file mode 100644
index 0000000..779cbe5
--- /dev/null
+++ b/ver0/ttt.c
@@ -0,0 +1,329 @@
+#include <stdlib.h>

+#include <stdio.h>

+#include <memory.h>

+#include <time.h>

+#include "ttt.h"

+

+SQUARE g_sComputerPlays = O_MARK;             // what side comp plays

+

+//+----------------------------------------------------------------------------

+//

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

+        default:

+            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");

+    }

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

+    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 = (x % BOARD_SIZE);

+        m->cVpos = (x / BOARD_SIZE);

+        m->sMark = g_sComputerPlays * -1;

+    }

+    while(FALSE == IsLegalMove(p, m));

+}

+

+//+----------------------------------------------------------------------------

+//

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

+

+    do

+    {

+        x = rand() % (BOARD_SIZE * BOARD_SIZE);

+        m->cHpos = (x % BOARD_SIZE);

+        m->cVpos = (x / BOARD_SIZE);

+        m->sMark = g_sComputerPlays;

+    }

+    while(FALSE == IsLegalMove(p, m));

+}

+

+//+----------------------------------------------------------------------------

+//

+// 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))

+    {

+        p->sBoard[m->cVpos][m->cHpos] = m->sMark;

+        p->uNumEmpty--;

+        p->sWhoseTurn *= -1;

+    }

+}

+

+//+----------------------------------------------------------------------------

+//

+// 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.

+// 

+//            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);

+    return(TRUE);

+}

+

+//+----------------------------------------------------------------------------

+//

+// 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);

+}

+

diff --git a/ver0/ttt.h b/ver0/ttt.h
new file mode 100644
index 0000000..c20a3d1
--- /dev/null
+++ b/ver0/ttt.h
@@ -0,0 +1,48 @@
+#ifndef _TTT_H_
+#define _TTT_H_
+
+#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)
+
+typedef signed char SQUARE;
+#define IS_SQUARE_EMPTY(x) (x == EMPTY)
+
+//
+// A (simple) representation of a tic tac toe position
+//
+#define BOARD_SIZE (3)
+
+typedef struct _POSITION
+{
+    SQUARE sWhoseTurn;
+    SQUARE sBoard[BOARD_SIZE][BOARD_SIZE];
+    unsigned int uNumEmpty;
+} POSITION;
+
+//
+// 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;
+
+#endif /* _TTT_H_ */