Game Design Foundations (Wordware Game and Graphics Library)

Visual C++ Language: Code for the AI Logic of Tic-Tac-Toe

#include "stdafx.h" #include "TicTacToeLogic.h" #include <time.h> #include <mmsystem.h> #define IDB_SMBOARD 140 #define IDB_BIGO 141 #define IDB_BIGX 142 #define IDB_SMALLO 143 #define IDB_SMALLX 144 #define IDB_BOARD 145 // extern(al) variables or variables that are defined in another file extern CString m_msg1,m_msg2,m_moves; extern HINSTANCE m_hInstance; extern int Setbuttons; extern HDC my_hDC; // Set the Global variables char Path[100]; int ttt[10][9], wp[8][3], BigBoxXY[9][3], SmBoxXY[9][3]; int playerMark, playerDONE, PmouseX, PmouseY; char squote[2]={(char)39,(char)0}; // ' single quote HBITMAP markX, markO, smarkx, smarko; HBITMAP BigBoard, SmBoard; int Clevel, L1nextspace, Level1Data[10]; unsigned int randseed; ///////////////////////////////////////////////////////////////////// void LoadBMPs() { markX = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_BIGX)); markO = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_BIGO)); smarkx = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_SMALLX)); smarko = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_SMALLO)); BigBoard = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_BOARD)); SmBoard = ::LoadBitmap(m_hInstance,MAKEINTRESOURCE(IDB_SMBOARD)); } ///////////////////////////////////////////////////////////////////// void InitVariables() { int i, j; Clevel = 0; // Initialize the Tic-Tac-Toe boards (all levels) to Zeor for(i = 0; i <= 9; i++) for(j = 0; j <= 8; j++) ttt[ i ][ j ] = 0; // We start the arrays at Zero to match our C-code // Rows wp[ 0 ][ 0 ] = 0; wp[ 0 ][ 1 ] = 1; wp[ 0 ][ 2 ] = 2; wp[ 1 ][ 0 ] = 3; wp[ 1 ][ 1 ] = 4; wp[ 1 ][ 2 ] = 5; wp[ 2 ][ 0 ] = 6; wp[ 2 ][ 1 ] = 7; wp[ 2 ][ 2 ] = 8; // Columns wp[ 3 ][ 0 ] = 0; wp[ 3 ][ 1 ] = 3; wp[ 3 ][ 2 ] = 6; wp[ 4 ][ 0 ] = 1; wp[ 4 ][ 1 ] = 4; wp[ 4 ][ 2 ] = 7; wp[ 5 ][ 0 ] = 2; wp[ 5 ][ 1 ] = 5; wp[ 5 ][ 2 ] = 8; // Diagonals wp[ 6 ][ 0 ] = 0; wp[ 6 ][ 1 ] = 4; wp[ 6 ][ 2 ] = 8; wp[ 7 ][ 0 ] = 2; wp[ 7 ][ 1 ] = 4; wp[ 7 ][ 2 ] = 6; // Define our two Tic-Tac-Toe boards int xoff1= 260,xoff2=40,yoff1=6,yoff2=210; BigBoxXY[ 0 ][ 0 ] = xoff1 + 0; BigBoxXY[ 0 ][ 1 ] = yoff1 + 0; BigBoxXY[ 1 ][ 0 ] = xoff1 + 125; BigBoxXY[ 1 ][ 1 ] = yoff1 + 0; BigBoxXY[ 2 ][ 0 ] = xoff1 + 243; BigBoxXY[ 2 ][ 1 ] = yoff1 + 0; BigBoxXY[ 3 ][ 0 ] = xoff1 + 0; BigBoxXY[ 3 ][ 1 ] = yoff1 + 101; BigBoxXY[ 4 ][ 0 ] = xoff1 + 125; BigBoxXY[ 4 ][ 1 ] = yoff1 + 101; BigBoxXY[ 5 ][ 0 ] = xoff1 + 243; BigBoxXY[ 5 ][ 1 ] = yoff1 + 101; BigBoxXY[ 6 ][ 0 ] = xoff1 + 0; BigBoxXY[ 6 ][ 1 ] = yoff1 + 196; BigBoxXY[ 7 ][ 0 ] = xoff1 + 125; BigBoxXY[ 7 ][ 1 ] = yoff1 + 196; BigBoxXY[ 8 ][ 0 ] = xoff1 + 243; BigBoxXY[ 8 ][ 1 ] = yoff1 + 196; SmBoxXY[ 0 ][ 0 ] = xoff2 + 0; SmBoxXY[ 0 ][ 1 ] = yoff2 + 0; SmBoxXY[ 1 ][ 0 ] = xoff2 + 22; SmBoxXY[ 1 ][ 1 ] = yoff2 + 0; SmBoxXY[ 2 ][ 0 ] = xoff2 + 44; SmBoxXY[ 2 ][ 1 ] = yoff2 + 0; SmBoxXY[ 3 ][ 0 ] = xoff2 + 0; SmBoxXY[ 3 ][ 1 ] = yoff2 + 22; SmBoxXY[ 4 ][ 0 ] = xoff2 + 22; SmBoxXY[ 4 ][ 1 ] = yoff2 + 22; SmBoxXY[ 5 ][ 0 ] = xoff2 + 44; SmBoxXY[ 5 ][ 1 ] = yoff2 + 22; SmBoxXY[ 6 ][ 0 ] = xoff2 + 0; SmBoxXY[ 6 ][ 1 ] = yoff2 + 44; SmBoxXY[ 7 ][ 0 ] = xoff2 + 22; SmBoxXY[ 7 ][ 1 ] = yoff2 + 44; SmBoxXY[ 8 ][ 0 ] = xoff2 + 44; SmBoxXY[ 8 ][ 1 ] = yoff2 + 44; setRandom(); // initialize the Random number function } ///////////////////////////////////////////////////////////////////// // Copy a new Tic-Tac-Toe board starting with the previous board void Copy_ttt(int level) { int index; if( level < 1)return; if( level > 8)return; Clevel = level; // for small tic-tac-toe board for( index = 0; index <= 8;index++) ttt[ level ][ index ] = ttt[ level – 1 ][ index ]; } ///////////////////////////////////////////////////////////////////// // Let's verify if there's an empty space to fill int SpaceEmpty(int level) { int index; for(index = 0; index <= 8; index++) if( ttt[level][index] == 0) return( index + 1 ); return(0); //no empty space was found } ///////////////////////////////////////////////////////////////////// // A function to check if the current board position is a winning // one for either player int IsThereaWin(int level, int MySide) { int ttWin, OppWin, MyWin, wpindex, i; OppWin = -3 * MySide; MyWin = 3 * MySide; for(wpindex = 0; wpindex <= 7; wpindex++){ // for each win (3 rows, 3 columns and 2 diagonals) ttWin = 0; for(i = 0; i<= 2; i++) // add the 3 spaces as per direction to check ttWin = ttWin + ttt[level][wp[wpindex][i]]; if( ttWin == MyWin) // I have 3 connecting marks return(100); // I win plus space to move to if( ttWin == OppWin) // Opponent can get 3 connecting marks return(-100); // forced plus space to block } return(0); } ///////////////////////////////////////////////////////////////////// // Let's check to see if there's a forced move to make // A forced move is a winning space or a blocking space to stop // a loss int forced_Move(int level, int MySide) { int index, trys, OppWin, MyWin, FMove, sgn1; OppWin = -3 * MySide; MyWin = 3 * MySide; for( trys = 0; trys<= 1; trys++) for( index = 0; index <= 8; index++){ if( level > 0 )Copy_ttt (level); if( ttt[level][index] == 0 ){ // empty space if( trys == 0 ) // Can we win on this turn ttt[level][index] = MySide; else // Can our opponent win if we don’t block ttt[level][index] = -MySide; // opponent FMove = IsThereaWin(level, MySide); if( FMove != 0 ){ sgn1 = 1; if( FMove < 0 ) sgn1 = -1; if( level > 0 ) Copy_ttt (level); return (sgn1 * (abs(FMove) + index + 1)); } } } if( level > 0 ) Copy_ttt (level); return(0); //No forced move } ///////////////////////////////////////////////////////////////////// void Tic_Tac_Toe() { int X, MySide, spaceon, FMove, i; X = 0; MySide = -playerMark; if( SpaceEmpty(0) > 0 ){ // Game still on // A forced move to win or to block a win is the best mark move X = forced_Move(1, MySide); spaceon = abs(X) % 100; // -100 or +100 plus space to mark if( X != 0 ){ // A forced move has been calculated ttt[0][spaceon - 1] = MySide; // either a '1' or a '-1' m_moves=_T(" I marked space "); m_moves+=REPitoa(spaceon,2); } // X != 0 //find a space that’s not forced if( X == 0 ){ // Initialize the level 1 available mark spaces to an extremely // low value for( i = 0; i <= 9; i++) Level1Data[i] = -999; // Call the Min-Max Function where Alpha is very low and Beta is // very high X = MinMaxValue(1, MySide, -999, 999); // find the best move // find the best space to mark from the level 1 list of valid spaces // to mark spaceon = SpaceEmpty(0) - 1; X = -999; for( i = 1; i <= 9; i++) if( Level1Data[i] > X ){ spaceon = i; X = Level1Data[i]; } ttt[ 0 ][ spaceon – 1 ] = MySide; // Mark the best space m_moves+=_T(" I marked space "); m_moves+=REPitoa(spaceon,2); } // X == 0 m_msg2=_T("Marked "); m_moves+=REPitoa(spaceon,2); show_boards(); // display current path scenario of board } // SpaceEmpty(0) > 0 show_boards(); playerDONE = 0; FMove = IsThereaWin(0, playerMark); if( FMove <= -100 ){ // Be prepared to see this message often m_moves+=_T(" HURRAY! I WON!"); m_moves+=_T(" Play me again?"); m_moves+=_T("Would you like to play me again?"); playerDONE = 100; Setbuttons= -2; // Reset_Buttons return; } // FMove <= -100 if( FMove >= 100 ){ // You may never see this message m_moves+=_T(" WOW! YOU"); m_moves+=squote; // Place a ' within " " m_moves+=_T("VE WON!"); m_moves+=_T(" Play me again?"); m_moves+=_T("Would you like to play me again?"); playerDONE = 100; Setbuttons= -2; // Reset_Buttons return; } // FMove >= 100 if( FMove == 0 ){ // No win found and all spaces marked playerDONE = 0; m_msg1=_T("Your turn, please mark a space"); if( SpaceEmpty(0) == 0 ){ // no more empty spaces to mark m_moves=_T(" DRAW!"); m_moves=_T(" Play me again?"); m_moves=_T("Would you like to play me again?"); Setbuttons= -2; // Reset_Buttons return; } // SpaceEmpty } // FMove == 0 } ///////////////////////////////////////////////////////////////////// // Just like a chess opening database, here are standard // Tic-Tac-Toe opening marks void opening() { int i, j, k; m_moves=_T(""); // Check to see if we go first and second j = 0; for (i = 0; i <= 8; i++ ) if( ttt[0, i] != 0 ){ j++; k = i; } // ttt[0, i] != 0 if( j > 1 ){ m_msg1=_T(""); Tic_Tac_Toe(); // find a space to mark return; } if( j == 0 ){ // we go first i = (int)(Random(5)); // valid first marks are spaces 1,3,5,7 // and 9 i = i * 2; // we have a random number 0 through 4 // so we double it ttt[0][i] = -playerMark; m_msg2=_T("Marked "); m_moves+=REPitoa(i + 1,2); m_msg1=_T("I marked space "); m_moves+=REPitoa(i + 1,2); playerDONE = 0; show_boards(); m_msg1=_T("Your turn, please mark a space"); // Player goes return; } // j == 0 if( j == 1 ){ // we go second // valid moves are center and the opposite corner if the opponent // marked a corner space i = -1; // a flag if( k == 4 && i == -1 ){ // center space marked i=4 ; // can't mark the center space while (i ==4) i = (int)(Random(4)); // valid first marks are spaces 1,3,7 // and 9 i = i * 2; // we have a random number 0 through 4 // so we double it } // k == 4 && i == -1 if( i == -1 ) // center space was not marked i = 4; // mark center space (space 5) ttt[0][i] = -playerMark; m_msg2=_T("Marked "); m_msg2=REPitoa(i + 1,2); m_moves=_T(" I marked space "); m_moves+=REPitoa(i + 1,2); playerDONE = 0; show_boards(); m_msg1=_T("Your turn, please mark a space"); // Player goes return; } } ///////////////////////////////////////////////////////////////////// int MinMaxValue(int level, int MySide, int alpha, int beta) { int WIN, index, nextspace, X, succval; long MTlist; // reset current level board Copy_ttt (level); if( SpaceEmpty(level) == 0 ) return( 0 ); // find a space that’s not forced // list all open spaces MTlist = 0; // List all the open (unmarked) spaces on this level X = forced_Move(level, MySide); // Is there a forced move (a win // or a block of a win) if( X != 0 ) // a forced move has been flagged MTlist = abs(X % 100); // space is 1 to 9 else{ for( index = 0; index <= 8; index++) if( ttt[level][8 - index] == 0 ) // subtract from 8 for // ascending order MTlist = MTlist * 10 + (9 - index); } // else while (MTlist > 0){ nextspace = MTlist % 10; // next space to mark MTlist = (MTlist - nextspace) / 10; // remainder of possible // spaces to mark Copy_ttt (level); ttt[level][nextspace - 1] = MySide; m_msg2=_T("Marked "); m_moves+=REPitoa(nextspace,2); show_boards(); WIN = IsThereaWin(level, MySide); if( WIN >= 100 ) succval = WIN; else succval = -MinMaxValue(level + 1, -MySide, -beta, -alpha); if( level == 1 ){ // Save this space’s value Level1Data[ nextspace ] = succval; if( succval == 100) return succval; // Winning line found } // level == 1 // The Alpha-Beta pruning code if( succval >= beta ) return( beta ); if( succval > alpha ) alpha = succval; } // While return( alpha ); // return a draw } ///////////////////////////////////////////////////////////////////// // Convert as number to a character array with a length of lval1 // (may have preceding zeroes) char *REPitoa(long val1, int lval1) { long x; int sgn=1, i, j, k, zeroflag=0; static char strx[10]; x= val1; if((val1 == 0) && (lval1 == 99)) return(""); if(lval1 == 99) lval1= 0; if(val1 < 0){sgn= -1; x= -val1;} // flag and set to positive if(lval1 < 0){ zeroflag= 1; // preceding zero lval1= -lval1; } if(lval1 == 0){ while(x > 0){ lval1++; x= x / 10L; // divide by 10 as a long } x= val1; } if((val1 == 0) && (lval1 == 0)) lval1=1; if(lval1 > 9)lval1= 9; // max length for(i=0; i<10; i++) strx[i]= (char)0; // end string if(x == 0){ for(i= 0; I < lval1; i++) strx[i]= '0'; return(&strx[0]); } j= 0; for(i= 0; i < lval1; i++){ k= x % 10; if(k > 0 && j == 0) j=1; strx[lval1 - (1 + i)] = (char)((int)'0' + k); if((zeroflag == 0) && (x == 0) && (j == 1)) strx[lval1 - (1 + i)]= (char)32; // blank left zeroes x=x / 10; // must be after the "if" } return &strx[0]; } ///////////////////////////////////////////////////////////////////// // Button 0 Play first as 'O' // Button 1 Play first as 'X' // Button 3 Play second as 'O' // Button 4 Play second as 'X' void buttontoplay(int buttonid) { show_boards(); playerMark = (2 * (buttonid % 2)) - 1; // -1 is "O", 1 is "X" playerDONE = 1; // Computer goes first if( buttonid < 2){ // Player’s turn m_msg1=_T("Your turn, please mark a space"); playerDONE = 0; } else // Computer’s turn opening(); } ///////////////////////////////////////////////////////////////////// void Get_Mark() { int i, flag; if (playerDONE == 1)return; flag = -1; // check the area the player has selected to mark for (i = 0; i < 9; i++) if ((PmouseX >= (BigBoxXY[i][0])) && (PmouseX <= (BigBoxXY[i][0] + 120))) if ((PmouseY >= (BigBoxXY[i][1])) && (PmouseY <= (BigBoxXY[i][1] + 95))) if( ttt[0][i] == 0){ ttt[0][i] = playerMark; m_moves=_T("You marked space "); m_moves+=REPitoa(i + 1,2); m_msg2=_T( "Marked "); m_msg2+=REPitoa(i + 1,2); playerDONE = 1; show_boards(); opening(); return; } } ///////////////////////////////////////////////////////////////////// void setRandom() { // Seed the random-number generator with current time so that // the numbers will be different every time we run. if(randseed == 0){ randseed= (unsigned int) timeGetTime(); srand( randseed ); } } ///////////////////////////////////////////////////////////////////// int Random(int num) { int r; DWORD r1; if(num == 0) num=1; r1= rand(); r= (int)r1 % num; return r; } ///////////////////////////////////////////////////////////////////// void show_boards() { showSmallBoard(); showBigBoard(); } ///////////////////////////////////////////////////////////////////// void showBigBoard() { int i, x, y; HDC hMemDCO= ::CreateCompatibleDC(NULL); HDC hMemDCX= ::CreateCompatibleDC(NULL); HDC hMemDC = ::CreateCompatibleDC(NULL); SelectObject(hMemDCO, markO); SelectObject(hMemDCX, markX); SelectObject(hMemDC, BigBoard); ::StretchBlt(my_hDC, 260, 6, 367, 293, hMemDC, 0, 0, 367, 293, SRCCOPY); for (i = 0; i<9; i++){ x= BigBoxXY[i][0]; y= BigBoxXY[i][1]; if (ttt[ 0 ][ I ] == 1) // markX ::StretchBlt(my_hDC, x, y, 113, 90, hMemDCX, 0, 0, 114, 90, SRCCOPY); else if (ttt[ 0 ][ I ] == -1) // markO ::StretchBlt(my_hDC, x, y, 114, 90, hMemDCO, 0, 0, 114, 90, SRCCOPY); } Clevel = 0; DeleteDC(hMemDCO); DeleteDC(hMemDCX); DeleteDC(hMemDC); } ///////////////////////////////////////////////////////////////////// void showSmallBoard() { int i,x,y; HDC hMemDCo= ::CreateCompatibleDC(NULL); HDC hMemDCx= ::CreateCompatibleDC(NULL); HDC hMemDC = ::CreateCompatibleDC(NULL); SelectObject(hMemDCo, smarko); SelectObject(hMemDCx, smarkx); SelectObject(hMemDC, SmBoard); ::StretchBlt(my_hDC, 40, 210, 64, 64, hMemDC, 0, 0, 64, 64, SRCCOPY); for (i = 0; i<9; i++){ x= SmBoxXY[ i ][ 0 ]; y= SmBoxXY[ i ][ 1 ]; if (ttt[ Clevel ][ i ] == 1) // smarkX ::StretchBlt(my_hDC, x, y, 114, 90, hMemDCx, 0, 0, 114, 90, SRCCOPY); else if (ttt[ Clevel ][ i ] == -1) // smarkO ::StretchBlt(my_hDC, x, y, 18, 20, hMemDCo, 0, 0, 18, 20, SRCCOPY); } DeleteDC(hMemDCo); DeleteDC(hMemDCx); DeleteDC(hMemDC); }