Another Hello-World Example of AI Game Using Optimization Techniques in C/C++

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

Nim Game

Simplified version:

  • A pile consists of n blocks, n ≥ 1.

  • Two players take turns to remove blocks from the pile.

  • A player removes k blocks from the remaining pile of n blocks, with 1 ≤ k ≤ floor(n/2)

  • The player who removes the last block loses.

    Example: 

    	Players A, B
	Initial n = 5
	A removes 2 block, remaining n = 3
	B removes 1 block, remaining n = 2
	A removes 1 block, remaining n = 1
	B removes the last block, so B lost and A won
    • Minimax Nim Game Tree

    Initial n = 6 

    A


B


A


B


A



B
	

    
// minimaxnim.cpp
// nim game using minimax algorithm 
// without alpha-beta pruning
// https://forejune.co/cuda/

#include <iostream>
#include <math.h>

using namespace std;

enum Player {MAX, MIN};

struct Node {
  int score;
  int move;
};

class MiniMaxNim{
private:
  Player ai, opp;

public:
  int n;		//number of objects in pile 
  Player turn;		//which player's turn
  MiniMaxNim(int n0, Player ai0, Player opp0)
  {
    ai = ai0;
    opp = opp0;
    if ( n0 > 1 && n0 < 100)
      n = n0;
    else
      n = 1;
  }

  int checkWinner()
  {
    if ( n == 1 ){
      if (turn == opp)
        return 1;		//ai wins
      else
        return 2;		//opp wins
    }

    return -1;		//not determined
  }

  bool lost(Player player)
  {
    if (turn == player && n == 1)
      return true;

    return false;
  }

  bool remove(int k)
  {
     if ( k < 1 || k >  n / 2  )
       return false;	//fail

     n = n - k;

     return true;
  }
 
  // evaluate score at a leaf
  int evaluation(int state)
  {
    if ( state == 1 )
      return 1;
    else 
      return -1;
				
    return 0;
  }

  Node minimax(bool max, int depth)
  {
    int state = 64; 
 
    if ( lost( opp ) )
       state = 1;
    else if ( lost( ai ) )
       state = -1;

    if ( state != 64  ) {	//end game
      int score = evaluation(state); 
      Node node = {score, -1};	//-1 signifies a leaf

      return node;
    } 

    Node v;
    v.move = -1;

    Player currentTurn = turn;

    if ( max ) {		//maximize score
      v.score = -64;
      int m = n / 2;
      for (int i = 1; i <= m; i++) {
	n = n - i;	//tentative move
	turn = currentTurn == ai ? opp : ai;	// change turn
	Node maxNode = minimax(false, depth+1);  //next call is min
	n = n + i;	//restore n
	turn = currentTurn;  //restore turn
	int s = maxNode.score;
	if ( s > v.score) {
	  v.score = s;
	  v.move = i;
	}
      } // for
    } else {		//minimize score
      v.score = 64;
      int m = n / 2;
      for (int i = 1; i <= m; i++){
	n = n - i; 
	turn = currentTurn == opp ? ai : opp;   //switch turn
	Node minNode = minimax(true, depth+1);  //next call is max
	n = n + i;		//restore n
	turn = currentTurn;	//retore turn
	int s = minNode.score;
	if ( s < v.score) {
	  v.score = s;
	  v.move = i;
	}
      }
    }

    return v;
  }
};

int main()
{
  int n;
  cout << "Enter number of blocks you want to start: ";
  cin >> n;

  Player ai = MAX, opp = MIN;
  MiniMaxNim nim( n, ai, opp );

  nim.turn = ai;
  while ( true ) {
    int status = nim.checkWinner();
    if (status > 0) {
       if (status == 1)
	  cout << "AI wins!" << endl;
       else
	  cout << "You win!" << endl;
       break;
    }
    int move;
    if (nim.turn == ai){
      cout << "Blocks remain: " << nim.n << endl;
      move = nim.minimax(true, 0).move;
      nim.remove( move );
      cout << "AI takes " << move << endl;
      nim.turn = opp;

    } else {
      for ( ; ; ){
	cout << "Blocks remain: " << nim.n << endl;
        cout << "Your move (1-" << nim.n/2 << "): ";
        cin >> move;
        if ( !nim.remove(move) ) {
          cout << "Invalid move; try again: \n";
          continue;
        } else
          break;
      }
      nim.turn  = ai; 
    }
  }

  return 0;
}

    Running time T(n) ~ T(n-1) + T(n-2) + ... + T(n-n/2)

    Solving the recurrence equation:

    The algorithm repeatedly solves the same subproblems many times.

    Dynamic Programming

  • Store intermediate results in a table.

  • For example, consider n = 6, we compute each value only once
    • Base case: n = 1 --> losing position.
    • Compute n = 2: check possible moves (k = 1) --> leaving n = 1 (loosing), so n = 2 is a winning position
    • Compute n = 3: possible moves (k = 1) --> n = 2 (winning).
      Since the opponent faces a winning state, n = 3 is losing.
    • Continue until n=6, using stored results instead of recomputing. 
    			n
		1  2   3  4  5  6   7
	score: -1, 1, -1, 1, 1, 1, -1
  • C/C++ Implementation: 
      // nimdp.cpp : nim game using dynamic programming
// https://forejune.co/cuda
#include <stdlib.h>

using namespace std;

int getScore(int n, int S[])
{
  if (n == 1)
     S[n] = -1;         //got last block
  if (S[n] != 0)
    return S[n];
  int m = n / 2;	//floor of n/2.0
  for (int i = 1; i <= m; i++) {
    int nextN = n - i;
    if (getScore(nextN, S)  == -1) {	//found a path the other player loses
       S[n] = 1;
       return S[n];
    }
  }

  S[n] = -1;

  return S[n];
}

//choose a winning move i if one exists, otherwise pick a random legal move
int bestMove(int n, int score[]) 
{
  int m = n / 2;
  if ( m < 1 )
    m = 1;
  for (int i = 1; i <= m; i++) {
     if (getScore(n - i, score) == -1) 
	return i;  //choose move so that the other player loses
  }

  return (rand() % m + 1); //no winning move; pick any random legal move
}

  • Testing Routine: 
      
// testNimdp.cpp 
// https://forejune.co/cuda

#include <stdlib.h>
#include <iostream>

using namespace std;

const int NMAX = 99;	//maximum blocks allowed

int bestMove(int n, int score[]);

int main(void) 
{
    srand(time(0));
    int n;
    int score[NMAX+1] = {0};
    do {
      cout << "Enter number of blocks you want to start (2 to 99): ";
      cin >> n;
    } while (n < 2 || n > NMAX);

    int n0 = n;
    cout << "AI moves first. Starting with n = " << n << endl;
    int move;
    while ( true ) {
        // --- AI turn ---
        if (n == 1) {
	    cout << "AI lost; you won!" << endl;
            break;
        }
	
        move = bestMove(n, score);
        n -= move;
        cout << "AI takes " << move << ", " << n << " remain" << endl;

        if (n == 1) {
	    cout << "You lost!" << endl;
            break;
        }
	
	// Your turn
	int m = n / 2;
	for (; ;) {
	  cout << "Your turn. Enter number (1-" << m << "): ";
	  cin >> move;
	  if (move < 1 || move > m)
	    cout << "Invalid move; try again: "; 
	  else
            break;
        }
        n -= move;
        cout << "You take " << move << ", " << n << " remain" << endl;
    }

    return 0;
}

    • Using a GUI