From 6d38eb746e86589e3b8fa10ba37d206af5eb7ebf Mon Sep 17 00:00:00 2001 From: Scott Gasch Date: Wed, 1 Jun 2016 19:41:17 -0700 Subject: Initial checking of tic tac toe minimax tutorial code. --- ver2/ttt.c | 535 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 535 insertions(+) create mode 100644 ver2/ttt.c (limited to 'ver2/ttt.c') diff --git a/ver2/ttt.c b/ver2/ttt.c new file mode 100644 index 0000000..d39bc7e --- /dev/null +++ b/ver2/ttt.c @@ -0,0 +1,535 @@ +/*++ + +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 +#include +#include +#include +#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); +} + -- cgit v1.3