Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

minimax algorithm not working properly

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

so please help me finding the bug in this code.thank you.
[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
{
cout<<"Enter your move
";
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 reply;
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);
reply=chooseMove(opp,dr,dc);

placeMove(r,c,EMPTY);

if(((p==NAUGHT) && (reply>=bestVal)) || ((p==CROSS) && (reply<=bestVal)))
{
bestVal=reply;
row=r;
col=c;
}
}
}
}
return bestVal;
}
[/code]

Comments

  • guesstguesst Posts: 46Member
    : 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.

    Personally, I prefer a method [link=http://www.retroremakes.com/forum2/showpost.php?p=152971&postcount=33]that learns[/link] over a perfect game.
  • iPhoneDeviPhoneDev Posts: 1Member
    Hi,

    you can check out this nice tutorial article about [link=http://www.imapps.net/devblog/files/alphabeta-objc.html]minimax with alpha-beta pruning for Objective C[/link], although it's for Objective C, you may find it useful for your problem...

    Cheers
Sign In or Register to comment.