Hello to all, i have coded a Tic Tac Toe program using C++. The problem now is i would like to implement AI features in this program. I not an AI student but just normal CS student. I wonder can any explain what is minimax theorem and alpha beta prunning. I did quite amount of research but still cannot understand it. I can code it once i understand the algorithm.

#ifndef TIC_TAC_TOE_H
#define TIC_TAC_TOE_H


#include <vector>
#include <string>
#include <map>

class TicTacToe
{
private:
 typedef std::vector<std::string> strVec;
 typedef std::vector<strVec> MultiStrVec;
 MultiStrVec DashBoard;

 static size_t PlayerID;

public:
 
 TicTacToe();
 ~TicTacToe();

 void operator()();

 int GameMode();

 void AI_VS_Player();
 void Player_VS_Player();
 
 void DisplayBoard();
 void userInput();
 void checker();


 

};


#endif

#include <iostream>
#include <limits>

#include "TicTacToe.h"

using std::cout;
using std::cin;
using std::getline; 


size_t TicTacToe::PlayerID = 1;

// =============================================
TicTacToe::TicTacToe() : DashBoard(MultiStrVec(3, strVec(3, " ")) )
{
}
// =============================================
TicTacToe::~TicTacToe()
{
}
// =============================================
void TicTacToe::operator()()
{
 
 
}
// =============================================
int TicTacToe::GameMode()
{
 system("cls");
 cout << "\n1. AI VS Player "
  << "\n2. Player VS Player ";
 cout << "\n\nEnter Game Mode : ";
 int gameMode = 0;
 cin >> gameMode;

 return gameMode;
}
// =============================================
void TicTacToe::AI_VS_Player()
{
} 
// =============================================
void TicTacToe::Player_VS_Player()
{
 int loop = 0;
 while (loop < 9)
 {
  userInput();
  ++loop;
 }

 cout << "\n\n";
 DisplayBoard();
 checker();
}
// =============================================
void TicTacToe::DisplayBoard()
{
 system("cls");
 cout << " ";
 int dashBoardLoop = 0;
 for (int loop = 0; loop < 11 ;++loop)
 {
  cout << "=";
 }

 cout << "\n";
 for (int loop = 0; loop < 11;++loop)
 {
  if (loop == 2 || loop == 6 || loop == 10)
  {
   cout << this->DashBoard[0][dashBoardLoop];
   ++dashBoardLoop;
  }
  else if (loop == 4 || loop == 8)
  {
   cout << "|";
  }
  else
  {
   cout << " ";
  }
 }
 
 cout << "\n ";
 dashBoardLoop = 0;
 for (int loop = 0; loop < 11 ;++loop)
 {
  cout << "=";
 }
 
 cout << "\n";
 for (int loop = 0; loop < 11;++loop)
 {
  if (loop == 2 || loop == 6 || loop == 10)
  {
   cout << this->DashBoard[1][dashBoardLoop];
   ++dashBoardLoop;
  } 
  else if (loop == 4 || loop == 8)
  {
   cout << "|";
  }
  else
  {
   cout << " ";
  }
 }
 cout << "\n ";
 dashBoardLoop = 0;
 for (int loop = 0; loop < 11 ;++loop)
 {
  cout << "=";
 }

 cout << "\n";
 for (int loop = 0; loop < 11;++loop)
 {
  if (loop == 2 || loop == 6 || loop == 10)
  {
   cout << this->DashBoard[2][dashBoardLoop];
   ++dashBoardLoop;
  } 
  else if (loop == 4 || loop == 8)
  {
   cout << "|";
  }
  else
  {
   cout << " ";
  }
 }
 cout << "\n ";
 for (int loop = 0; loop < 11 ;++loop)
 {
  cout << "=";
 }

 cout << "\n\n\n";
}
// =============================================
void TicTacToe::userInput()
{
 int row = 0, column = 0;
 enum {MINPOSITION = 0, MAXPOSITION = 2};
 if (PlayerID == 1)
 {
  do
  {
   DisplayBoard();
   cout << "First Player Turn";
   cout << "\nEnter Row : ";
   cin >> row;
   while (cin.fail() || row < MINPOSITION || row > MAXPOSITION)
   {
    cin.clear();
    cin.ignore(std::numeric_limits<int>::max(), '\n');
    cout << "Enter Row : ";
    cin >> row;
   }

   cout << "Enter Column : ";
   cin >> column;
   while (cin.fail() || column < MINPOSITION || column > MAXPOSITION)
   { 
    cin.clear();
    cin.ignore(std::numeric_limits<int>::max(), '\n');
    cout << "Enter Column : ";
    cin >> column;
   }

  }while (this->DashBoard[row][column] != " ");
  
  ++PlayerID;
  // Assign row column
  DashBoard[row][column] = "X"; 

 }
 else if (PlayerID == 2)
 {
  do
  {
   DisplayBoard();
   cout << "Second Player Turn\n";
   cout << "Enter Row : ";
   cin >> row;
   while (cin.fail() || row < MINPOSITION || row > MAXPOSITION)
   {
    cin.clear();
    cin.ignore(std::numeric_limits<int>::max(), '\n');
    cout << "Enter Row : ";
    cin >> row;
   }

   cout << "Enter Column : ";
   cin >> column;
   while (cin.fail() || column < MINPOSITION || column > MAXPOSITION)
   {
    cin.clear();
    cin.ignore(std::numeric_limits<int>::max(), '\n');
    cout << "Enter Column : ";
    cin >> column;
   }

  } while (this->DashBoard[row][column] != " " );
 
  --PlayerID;
  // Assign row column
  DashBoard[row][column] = "O";

 }
}
// =============================================
void TicTacToe::checker()
{
 bool HasGameStatus = false;
 int rowLoop = 0, columnLoop = 0, winStatus = 99;
 
 for (rowLoop = 0; rowLoop < 3;++rowLoop)
 {
  if (DashBoard[rowLoop][0] == "X" &&  
   DashBoard[rowLoop][1] == "X" && 
   DashBoard[rowLoop][2] == "X")
  {
   winStatus = 1;
   HasGameStatus = true;
  }
  else if (DashBoard[rowLoop][0] == "O" &&  
   DashBoard[rowLoop][1] == "O" && 
   DashBoard[rowLoop][2] == "O")
  {
   winStatus = 2;
   HasGameStatus = true;
  }
 }

 rowLoop = 0;
 while (!HasGameStatus && columnLoop < 3)
 {
  if (DashBoard[0][columnLoop] == "X" &&
   DashBoard[1][columnLoop] == "X" && 
   DashBoard[2][columnLoop] == "X" )
  {
   winStatus = 1;
   HasGameStatus = true;
  }
  else if (DashBoard[0][columnLoop] == "O" &&
   DashBoard[1][columnLoop] == "O" && 
   DashBoard[2][columnLoop] == "O" )
  {
   winStatus = 2;
   HasGameStatus = true;
  }
  ++columnLoop;
 }

 rowLoop = 0;
 int LeftMirrorColumnLoop = 0, RightMirrorColumnLoop = 2;
 while (!HasGameStatus && rowLoop < 1)
 {
  if (DashBoard[0][LeftMirrorColumnLoop] == "X" && 
    DashBoard[1][LeftMirrorColumnLoop] == "X" && 
    DashBoard[2][LeftMirrorColumnLoop] == "X" || 
    
    DashBoard[0][RightMirrorColumnLoop] == "X" && 
    DashBoard[1][RightMirrorColumnLoop] == "X" && 
    DashBoard[2][RightMirrorColumnLoop] == "X")
  {
   winStatus = 1;
   HasGameStatus = true;
  }
  else if (DashBoard[0][LeftMirrorColumnLoop] == "O" && 
    DashBoard[1][LeftMirrorColumnLoop] == "O" && 
    DashBoard[2][LeftMirrorColumnLoop] == "O" || 
    
    DashBoard[0][RightMirrorColumnLoop] == "O" && 
    DashBoard[1][RightMirrorColumnLoop] == "O" && 
    DashBoard[2][RightMirrorColumnLoop] == "O")
  {
   winStatus = 2;
   HasGameStatus = true;
  }

  ++rowLoop;
  ++LeftMirrorColumnLoop;
  --RightMirrorColumnLoop;

 }

 if (winStatus == 1 && HasGameStatus)
 {
  cout << "\nFirst Player Win ";
 }
 else if (winStatus == 2 && HasGameStatus)
 {
  cout << "\nSecond Player Win ";
 }
 else
 {
  cout << "\nDraw";
 }


}
// =============================================

// =============================================

// =============================================


// =============================================


// =============================================


// =============================================

// =============================================

// =============================================

Thanks.

This is solved using minmax search. This article looks like a decent explanation.

Thanks.

Any other.

How about the alpha beta prunning article ?

Thanks.

Read the description of alpha-beta pruning on Bruce Moreland's old website.

Good website.

How about article minimax mixed with alpha beta pruning ?

Quote:Original post by Peter_APIIT
How about article minimax mixed with alpha beta pruning ?

Alpha beta pruning is just an optimization to the minimax algorithm. It's not "something separate." There's no way for an article to describe it in a way that's not "mixed with minimax."

Thanks. The problem now is how to represent a position in board with the algorithm.

Quote:Original post by Peter_APIIT
Thanks. The problem now is how to represent a position in board with the algorithm.

The standard way to do this is to keep some "global" representation of your board, and then, as you do minmax, to simply do and undo moves on this "global" representation of the board.

If you're using explicit recursion, this would look something like (pseudocode)...

global BOARD// ...function minmax(){  // ...  for each possible move MOVE  {     // ...     Do MOVE to BOARD     minmax();     Undo MOVE to BOARD     // ...  }} .

For a small problem like Tic Tac Toe, however, it's also entirely possible to just shove the entire gamestate into a single uint32 and pass that around. That's what I did once.

Actually, let's see... a sloppy (but simple) packing would be to allocate two bits per cell to store one of the possible markings {X,O,empty}; that's 2*9=18 bits there. Then you need another bit to store whose turn it is. That's 19 bits. You can also shove alpha, beta, and the current reward/cost in there too. Assuming these can take one of three values {win, lose, tie}, then you can store each inefficiently as two bits; that's an extra 6 bits, which brings you up to a total of 25 bits. I may be leaving some things out but that gives the basic idea.

Personally I'd use the traditional "do/undo" method though; it's more transferable to other, larger problems.