#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# minimax algorithm not working properly

Member Posts: 1
hello i got frustrated after making several tries to make the minimax algorithm work in my console tic tac toe. the problem is the algorithm
doesn't play the game as it should.The thing is it just tries to play the move that it 'sees' to be the best for itself without caring that its opponet
is building an easy three to win the game.
For ex. it playing as second player as

ist player row=0;col=0;
minimax player row=2;col=1;
ist player row=0;col=1;
minimax row=2;col=0;(ignoring the fact the player will win in next move)
ist player row=0;col=2 and wins

[code]

//board.h file

#ifndef BOARD_H
#define BOARD_H

#include
#include
using namespace std;

enum PosValue {O_WIN=-1,TIE,X_WIN,UNDEFINED};
enum Piece {NAUGHT=-1,EMPTY,CROSS};
enum Player {HUMAN=1,COMP};

class board
{
public:

board();
~board(){}
void initBoard(Player pl);
bool isAWin(Piece p);
bool isBoardFull();
bool isOver();
int evaluate();
bool makeMove(int r,int c,Piece p=EMPTY);
void undoMove(int r,int c);
void drawBoard();
Piece turnToPiece();
void alterTurn();
Player firstPlayer;
void playComp();
void playHuman();

int chooseMove(Piece p,int &row,int &col);

private:

Piece hold[3][3];

void placeMove(int r,int c,Piece p=EMPTY);
char pieceToChar(Piece p);
int turn;

};

#endif

#include "board.h"

board::board()
{

}

void board::initBoard(Player pl) //initialize the board, gets who is first playing
{
firstPlayer=pl;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
hold[i][j]=EMPTY;

turn =1;
}

bool board::isAWin(Piece p) //checks whether a Piece wins
{
int row, column;

// check all rows
for( row = 0; row < 3; row++ )
{
for( column = 0; column < 3; column++ )
if( hold[ row ][ column ] != p )
break;
if( column >= 3 )
return true;
}

// check all column
for( column = 0; column < 3; column++ )
{
for( row = 0; row < 3; row++ )
if( hold[ row ][ column ] != p)
break;
if( row >= 3 )
return true;
}

// check diagonals
if( hold[ 1 ][ 1 ] == p && hold[ 2 ][ 2 ] == p
&& hold[ 0 ][ 0 ] == p )
return true;

if( hold[ 0 ][ 2 ] == p && hold[ 1 ][ 1 ] == p
&& hold[ 2 ][ 0 ] == p )
return true;

return false;

}

bool board::isBoardFull()
{
for(int row=0;row<3;row++)
{
for(int col=0;col<3;col++)
{
if (hold[row][col]==EMPTY)
return false;
}
}
return true;
}

int board::evaluate() //heuristic function used for minimax algo
{
if (isAWin(CROSS))
return X_WIN;
else if (isAWin(NAUGHT))
return O_WIN;
else if (isBoardFull())
return TIE;
else
return UNDEFINED;
}

bool board::makeMove(int r, int c, Piece p) //makes a move on board, checking available
{
if((r<0) || (r>2) || (c<0) || (c>2) || hold[r][c]!=EMPTY)
return false;

placeMove(r, c, p);

return true;
}

void board::placeMove(int r, int c, Piece p )//makes a move on board,no checking available
{ //(used by minimax)
hold[r][c]=p;
}

void board::undoMove(int r, int c) //undo a move(used by minimax)
{
hold[r][c]=EMPTY;
}

bool board::isOver() //if game is over
{
if(evaluate()==UNDEFINED)
return false;
else
return true;
}

char board::pieceToChar(Piece p) //converts a piece to char( used by drawBoard)
{
if(p==EMPTY)
return ' ';
else if(p==CROSS)
return 'X';
else
return 'O';
}

void board::drawBoard()
{
char print_board[3][3];

for (int row=0; row<3; row++)
for(int col=0;col<3;col++)
print_board[row][col] = pieceToChar(hold[row][col]);

cout << print_board[0][0] << '|' << print_board[0][1] << '|' << print_board[0][2] << endl;
cout << print_board[1][0] << '|' << print_board[1][1] << '|' << print_board[1][2] << endl;
cout << print_board[2][0] << '|' << print_board[2][1] << '|' << print_board[2][2] << endl;
cout<<"

";
}

Piece board::turnToPiece() //converts current turn(1 for X, 0 for O) to piece
{
if(turn>0)
return CROSS;
else
return NAUGHT;
}

void board::alterTurn() //alternates the turn
{
turn*=-1;
}

void board::playHuman()
{
int r,c;
Piece p=turnToPiece();

do
{
";
cin>>r>>c;
}while(makeMove(r,c,p)==false);
drawBoard();
alterTurn();
}

void board::playComp()
{
int r,c;
Piece p=turnToPiece();

/*do
{
r=rand()%3;
c=rand()%3;
}while(makeMove(r,c,p)==false);*/
chooseMove(p,r,c);
cout<<makeMove(r,c,p)<<endl;
cout<<"r"<<r<<endl;
cout<<"c"<<c<<endl;
drawBoard();
alterTurn();
}

int board::chooseMove(Piece p, int &row, int &col) //minimax algorithm
{
int imVal;
int bestVal;
int dr,dc;
Piece opp;

if((imVal=evaluate())!=UNDEFINED)
return imVal;

if(p==NAUGHT)
{
opp=CROSS;
bestVal=-1;
}
else
{
opp=NAUGHT;
bestVal=1;
}

for(int r=0;r<3;r++)
{
for(int c=0;c<3;c++)
{
if(hold[r][c]==EMPTY)
{
placeMove(r,c,p);

placeMove(r,c,EMPTY);

{
row=r;
col=c;
}
}
}
}
return bestVal;
}
[/code]

• Member Posts: 46
: hello i got frustrated after making several tries to make the
: minimax algorithm work in my console tic tac toe. the problem is the
: algorithm
: doesn't play the game as it should.The thing is it just tries to
: play the move that it 'sees' to be the best for itself without
: caring that its opponet
: is building an easy three to win the game.
I haven't read over your code entirely but I've seen this before with other tic-tac-toe games. One in particular I held on to for a while thinking I would modifiy it until I found this problem.

The thing is Tic-Tac-Toe doesn't lend itself well to mini-max. Minimax is good for "where are going to be in X moves" but even for games that minimax well like reversi you need to handle the end game slightly different. Tic-Tac-Toe is all end game.

The best thing to do is to find the "closest" 3 in a row if all paths are played out and make the move that has the most of them, randomly choosing ties. You'll notice this doesn't discriminate between X or O. If you have the chance to make 3 in a row after your opponent it doesn't matter. So you'll always want to block if your opponent will win before you. The problem with this becomes the first move. I think it will always pick the center, when we all know that this pretty much assures a tie game.