minimax algorithm not working properly

Sat, 26 Jan 2008 21:34:20 -0700

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.


//board.h file

#ifndef BOARD_H
#define BOARD_H

#include<iostream>
#include<cstdlib>
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<<"\n\n";
}


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\n";
		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;
}

Re: minimax algorithm not working properly

Sat, 23 Feb 2008 15:10:45 -0700

: 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 that learns over a perfect game.

Re: minimax algorithm not working properly

Mon, 29 Jun 2009 07:56:26 -0700

Hi,

you can check out this nice tutorial article about minimax with alpha-beta pruning for Objective C, although it's for Objective C, you may find it useful for your problem...

Cheers

'minimax algorithm not working properly' Thread RSS Feed

minimax algorithm not working properly

Re: minimax algorithm not working properly

Re: minimax algorithm not working properly