Sign in to follow this  

Tic Tac Toe

This topic is 3035 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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."

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

This topic is 3035 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this