A Hello-World Example of AI Game in C/C++

Materials available at: https://forejune.co/cuda/

Game Tree

In an adversary game like chess, a player may look ahead several moves in advance.

The sequences of moves may be represented by a game tree.

The root represents the initial condition.

Branches from the root represnet legal moves the first player could make.

At the next level, branches represnet legal moves of the second player and so on.

Example: Game of Eight

Played between 2 players.
Each player alternately chooses one of the numbers 1, 2 or 3.
The number chosen in the previous step is not allowed.
The player who brings the sum of the numbers chosen to 8 wins.
F -- First Player
S -- Second Player
F S F S

Minimax Game Tree

Larger value favors the first player, smaller value favors the second player.

Evaluation at a leaf.

		e.g. Chess: 	capturing a pawn: +2
			 	capturing a knight +5
				losing a pawn: -2
				.....
		Tic-tac-toe:
			won : +1
			lost: -1
			draw: 0

The first player selects the move that maximizes the score.

The second player selects the move that minimizes the score.

MAX ( 7 ) MIN MAX MIN

Examples

MAX ( 0 ) MIN MAX

MAX ( 0 ) MIN MAX Evaluation

Alpha Beta Pruning

A minimax tree has been partially evaluated.

Maximizer: ignore branches where the minimum value is less than or equal to
the current best maximum

Minimizer: ignore branches where the maximum value is greater than or equal to
the current best minimum

Alpha (α), Beta (β) refered to the cutoff values

In the above figure, branches enclosed in dotted lines can be pruned

Tic-tac-toe Minimax Game in C/C++

Evaluation discussed: win: +1, draw: 0, lose: -1

The evaluation is fine but may have this situation:

In practice, we want to win as soon as possible,
that is at a smaller depth of the tree

Evaluation function accounting for depth:

	score(depth, state) = 0		   state = draw
	                      10 - depth	   ai wins
			      depth - 10	   opp wins


// minimax.h
// https://forejune.co/cuda/
#ifndef __minimax_H__
#define __minimax_H__

enum Player {EMPTY=0, X, O};

struct Node {
  int score;
  int move;
};

class MiniMaxT{
private:
  Player ai, opp;

public:
  MiniMaxT(Player ai, Player opp);
  Player board[9];
  void resetBoard();
  void printBoard();
  bool isWinning(Player player);
  bool emptyCell();
  int evaluation(int depth, int state);
  Node minimax(bool max, int depth);
};

#endif


// minimax.cpp
// Tic-tac-toe game using minimax algorithm 
// without alpha-beta pruning
// https://forejune.co/cuda/

#include <iostream>
#include <ctime>
#include "minimax.h"

using namespace std;

MiniMaxT::MiniMaxT(Player ai0, Player opp0)
{
    ai = ai0;
    opp = opp0;
    for (int i = 0; i < 9; i++)
      board[i] = EMPTY;
}

void MiniMaxT::resetBoard()
{
  for (int i = 0; i < 9; i++)
    board[i] = EMPTY;
}

void MiniMaxT::printBoard()
{
  char symbols[3] = {' ', 'X', 'O'};
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      Player p = board[3*i+j];
      cout << symbols[p];
      if (j < 2) cout << " | ";
    }
    cout << endl;
    if (i < 2) cout << "---------" << endl;
  }
}

bool MiniMaxT::isWinning(Player player)
{
    const int w[8][3] = {               //winning positions
        {0,1,2},{3,4,5},{6,7,8},        //rows
        {0,3,6},{1,4,7},{2,5,8},        //columns
        {0,4,8},{2,4,6}                 //diagonals
    };
    for (int i = 0; i < 8; i++){
      if (board[w[i][0]]==player && board[w[i][1]]==player
                      && board[w[i][2]]==player)
        return true;
     }

    return false;
}

bool MiniMaxT::emptyCell()
{
    //chekc if more empty space 
    for (int i = 0; i < 9; i++)
       if (board[i] == EMPTY)
         return true;

    return false;   //no more empty space 
}

// evaluate score at a leaf
int MiniMaxT::evaluation(int depth, int state)
{
  if ( state == 0 )	//draw
    return 0;
  else if ( state == 1 )
    return (10 - depth);	//ai wins
  else 
    return (depth - 10);	//opp wins
				
  return 0;
}

Node MiniMaxT::minimax(bool max, int depth)
{
  int state = 89;	//non-terminal state
  
  if ( isWinning( ai ) )
     state = 1;
  else if ( isWinning( opp ) )
     state = -1;
  else if ( !emptyCell() ) 
     state = 0;		//draw

  if ( state != 89 ) {	//end game
    int score = evaluation(depth, state); 
    Node n = {score, -1};	//-1 signifies a leaf
    return n;
  } 

  Node v;
  v.move = -1;

  if ( max ) {		//maximize score
    v.score = -89;
    for (int i = 0; i < 9; i++)
      if (board[i] == EMPTY) {
	 board[i] = ai;		//tentative move
				//next level is opp's (min) turn
	 Node maxNode = minimax(false, depth+1);  //next call is min
	 board[i] = EMPTY;	//restore board
	 int s = maxNode.score;
	 if ( s > v.score) {
	   v.score = s;
	   v.move = i;
	 }
      }
  } else {		//minimize score
    v.score = 89;
    for (int i = 0; i < 9; i++)
      if (board[i] == EMPTY) {
	 board[i] = opp;	//tentative move
			//next is ai's (max) turn
	 Node minNode = minimax(true, depth+1);  //next call is max
	 int s = minNode.score;
	 if ( s < v.score) {
	   v.score = s;
	   v.move = i;
	 }
	 board[i] = EMPTY;	//restore board
      }
  }

  return v;
}

// testMinimax.cpp
// https://forejune.co/cuda/
#include <iostream>
#include <ctime>
#include "minimax.h"

using namespace std;

int main()
{
  Player ai = X;
  Player opp = O;
  Player turn;
  srand(time(0));

  MiniMaxT game(ai, opp);
  if ( rand() % 2 == 0 )
    turn = ai;		//ai goes first
  else
    turn = opp;		//opp goes first
  while ( true ) {
    if ( game.isWinning( ai ) ) {
 	cout << "AI wins!\n";
	break;
    } else if ( game.isWinning( opp ) ) {
 	cout << "You win!\n";
	break;
    } else if ( !game.emptyCell() ) {
	cout << "Draw!\n";
	break;
    }
    int move; 
    if (turn == ai) {
      move =  game.minimax(true, 0).move;
      game.board[move] = ai;
      cout << "AI plays " << move << endl;
      turn = opp;
    } else {		// opponent's turn
      for ( ; ; ){
	cout << "Your move (0-8): ";
        cin >> move;
	if ( move < 0 || move > 8 || game.board[move] != EMPTY) {
	  cout << "Invalid move; try again: \n";
	  continue;
	} else
	  break;
      }
      game.board[move] = opp;
      turn = ai;
    }  //else	    
    game.printBoard();
  }  //while true

  return 0;
}

Using a GUI

/* https://forejune.co/cuda
 * testMinimaxg.cpp
 *
 */

#include <GL/gl.h>
#include <GL/glu.h>
#include <GL/glut.h>
#include <iostream>
#include "imageio.h"
#include "minimax.h"

using namespace std;

Player ai = X;
Player opp = O;
bool oppMove = false;
bool playing = false;
const int nImages = 5;
unsigned char *ibuff[nImages];
char *fnames[nImages] ={ (char *) "Xs.png", (char *) "Os.png", (char *) "aiWon.png",
		(char *) "youWon.png", (char *) "draw.png" };
int   iwidth[nImages], iheight[nImages];
const float d = 1;	//drawing distance between lines = 2*d
int	whoWon = -1;
MiniMaxT *game = NULL;

void resetBoard()
{
  game->resetBoard();
  oppMove = false;
  playing = false;
  whoWon = -1;
}

void printBoard()
{
   float di = -d/2.0;		//align image center at center of square
   // positions to display X or O
   float cx[9] = {-2*d, 0, 2*d, -2*d, 0, 2*d, -2*d, 0, 2*d};
   float cy[9] = {2*d, 2*d, 2*d, 0, 0, 0, -2*d, -2*d, -2*d};
   for (int i = 0; i < 9; i++ ) {
       if (game->board[i] != EMPTY) {
     	  glRasterPos2f (cx[i]+di, cy[i]+di);	//position to display image
	  if (game->board[i] == X)
   	    glDrawPixels(iwidth[0],iheight[0],GL_RGBA,GL_UNSIGNED_BYTE,ibuff[0] );
	  else
   	     glDrawPixels(iwidth[1],iheight[1],GL_RGBA,GL_UNSIGNED_BYTE,ibuff[1] );
       } 
   } // for
 
   if ( whoWon > 0 ) {
     glRasterPos2f (-3*d, -5*d);		//position to display image
     glDrawPixels ( iwidth[whoWon], iheight[whoWon], GL_RGBA, GL_UNSIGNED_BYTE,
     ibuff[whoWon] );
   } 
   glFlush();
}

int window;
int screenWidth = 500, screenHeight = 500;

void init(void)
{   
  glClearColor(1, 1, 1, 0);     //clear color buffer with white color
  glClear(GL_COLOR_BUFFER_BIT); //clear color buffer
  //define coordinate system
  glMatrixMode(GL_PROJECTION);
  glLoadIdentity();
  gluOrtho2D(-10, 10, -10, 10);
  glPointSize( 3 );
  glColor3f(0.0, 0.0, 0.0);             //draw with black color

  glMatrixMode(GL_MODELVIEW);
  glLoadIdentity();
  glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
  for (int i = 0; i < nImages; i++) {
     ibuff[i] = loadImageRGBA( fnames[i], &iwidth[i], &iheight[i]);
  }
}

void line (float x0, float y0, float x1, float y1)
{
  glBegin(GL_LINES);
    glVertex2f(x0, y0);
    glVertex2f(x1, y1);
  glEnd();
}
void display(void)
{
   glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
   glLineWidth( 3 );
   glColor3f(0, 0, 0);
   line(-3*d, d, 3*d, d);		//upper horizontal line 
   line(-3*d, -d, 3*d, -d);		//lower horizontal line 
   line(-d, 3*d, -d, -3*d);		//left vertical line
   line(d, 3*d, d, -3*d);		//right vertical line

   glFlush();
}
   
int checkStatus()
{
   if ( game->isWinning( ai ) ) 
        return 2;
   else if ( game->isWinning( opp ) ) 
        return 3;
    else if ( !game->emptyCell() ) 
        return 4;

    return -1;
}

void aiMove()
{
  whoWon = checkStatus();
  if (whoWon > 0 ) return;	//game over

  int move =  game->minimax(true, 0).move;
  game->board[move] = ai;
}

void play()
{
  if ( playing )
    return;
  if ( game != NULL )
    delete game;		//start new game
  game = new MiniMaxT(ai, opp);
  srand(time(0));
  
  if ( rand() % 2 == 0 ) {  //ai goes first
    int move = rand() % 9;   //random first move
    game->board[move] = ai;
    printBoard();
  }
  oppMove = true;	    //else opp moves first
}

void keyboard(unsigned char key, int x, int y)
{
  switch(key) {
    case 27: /* escape */
        glutDestroyWindow(window);
        exit(0);
    case 'p':	//play game
	if ( !playing ) {
	  play();
	  playing = true;
	}
	break;
    case 'r':	//reset board
	resetBoard();
	glutPostRedisplay();
	break;
  }
}

int getLocation(float wx, float wy)
{
  if (wx < -d) {
    if (wy > d)
 	return 0;
    else if (wy > -d)
	return 3;
    else
	return 6;
   }else if (wx < d) {
    if (wy > d)
 	return 1;
    else if (wy > -d)
	return 4;
    else
	return 7;
   }else {
    if (wy > d)
 	return 2;
    else if (wy > -d)
	return 5;
    else
	return 8;
   }
}

void mouse(int button, int state, int mx, int my)
{
   if ( !oppMove )
     return;
   int x = mx, y = screenHeight - my;
   float wx = (float) x * 20.0/screenWidth - 10;	//world coordinates
   float wy = (float) y * 20.0/screenHeight - 10;	
   if ( button == GLUT_LEFT_BUTTON && state == GLUT_DOWN ){
      if (whoWon < 0 ) {	//game not done
        int loc = getLocation(wx, wy);
        if (game->board[loc] == EMPTY) {
	  game->board[loc] = opp;
	  oppMove = false;
	  printBoard();
	  aiMove();
	  whoWon = checkStatus();
	  printBoard();
	  oppMove = true;
        }
      }
   }
}

int graphics(int argc, char** argv)
{
   glutInit(&argc, argv);
   glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB | GLUT_DEPTH);
   glutInitWindowSize(screenWidth, screenHeight);
   glutInitWindowPosition(100, 100);
   window = glutCreateWindow(argv[0]);
   init();
   glutDisplayFunc(display);
   glutKeyboardFunc(keyboard);
   glutMouseFunc( mouse );
   glutMainLoop();
   return 0; 
}


int main(int argc, char** argv)
{
  graphics(argc, argv);

  return 0;
}

Using Alpha-Beta Pruning

Node MiniMaxT::minimaxab(bool max, int depth, int alpha, int beta)
{
  int state = 89, e;
  
  e = emptyCell();
  if ( isWinning( ai ) )
     state = 1;
  else if ( isWinning( opp ) )
     state = -1;
  else if ( e < 0 ) 
     state = 0;		//draw

  if ( state != 89 ) {	//end game
    int score = evaluation(depth, state); 
    Node n = {score, -1};	//-1 signifies a leaf
    return n;
  } 

  Node v;
  v.move = -1;

  if ( max ) {		//maximize score
    v.score = -89;
    for (int i = 0; i < 9; i++)
      if (board[i] == EMPTY) {
	board[i] = ai;		//tentative move
	Node maxNode = minimaxab(false, depth+1, alpha, beta);  //next call is min
	board[i] = EMPTY;	//restore board
	int s = maxNode.score;
	if ( s > v.score) {
	  v.score = s;
	  v.move = i;
	}
	if (alpha < s)
	  alpha = s;
	if (alpha >= beta ) break;	//alpha-beta pruning
      }
  } else {		//minimize score
    v.score = 89;
    for (int i = 0; i < 9; i++)
      if (board[i] == EMPTY) {
	board[i] = opp;	//tentative move
	Node minNode = minimaxab(true, depth+1, alpha, beta);  //next call is min
	int s = minNode.score;
	if ( s < v.score) {
	  v.score = s;
	  v.move = i;
	}
	board[i] = EMPTY;	//restore board
	if (beta > s)
	  beta = s;
	if (beta <= alpha)	//alpha-beta pruning
	  break;
      }
  }

  return v;
}

	Note: In minimaxab(), alpha, beta are value parameters,
		changed values won't be passed back to calling routines
	AI starts first

MAX (depth=0) MIN (1) MAX (2) MIN (3)

	 Initial (depth=0), α = -89, β = 89
	
 After calling the left two branches, α = 7, β = 89
	
 Calling third branch, α = 7, β = 89
	
 At depth 1, minimaxab() executes minimizer:
	α = 7, β = 3
	Since α ≥ β it breaks out of the loop and returns
	
 Calling the fourth branch, α = 7, β = 89
	......