Sign in to follow this  
villiageidiot

Min Max Tic Tac Toe C++

Recommended Posts

I've done some research on using Min Max for the computer's AI in my tic tac toe game, and I can't quite seem to understand it. Here's an example of some code that I found:
int bestmove = -1; // Where the best move for computer is

enum square
{
        EMPTY = 0,
        PLAYER1 = 1,
        PLAYER2 = 2
};
    
square board[9];

bool board_full()
{
	for(int i = 0; i < 9; ++i)
	{
		if(board[i] == EMPTY) {
			return false;
		}
	}

	return true;
}

bool player_won(square player, int p1, int p2, int p3)
{
	return board[p1] == player && board[p2] == player && board[ p3] == player;
}

bool player_won(square player)
{
	bool left = player_won(player, 0, 1, 2) || player_won(player, 3, 4, 5) || player_won(player, 6, 7, 8);
	bool up = player_won(player, 0, 3, 6) || player_won(player, 1, 4, 7) || player_won(player, 2, 5, 8);
	bool diag = player_won(player, 0, 4, 8) || player_won(player, 2, 4, 6);
	
	return left || up || diag;
}

int eval()
{
	if(player_won(PLAYER1))
	{
		return 1;
	}


 	if(player_won(PLAYER2))
	{
		return -1;
	}

	return 0;
}

struct search_result
{
	int score;
	int best_move;
};

search_result search_max();
search_result search_min();

search_result search_max()
{
	search_result best_res;
	int score = eval();

	// has anyone won?
 	if(score)
	{
		best_res.score = score;
		return best_res;
	}
	else
	{
		// done if the board is full
		if(board_full())
		{
			best_res.score = score;
			return best_res;
		}
	}

	best_res.score = INT_MIN;

	for(int i = 0; i < 9; ++i)
	{
		if(board[i] == EMPTY)
		{
			board[i] = PLAYER1;
			
			search_result curr_res = search_min();
			curr_res.best_move = i;

			if(curr_res.score > best_res.score)
			{
                //MessageBox(NULL,"YES","TES",0);
				best_res = curr_res;
			}

			board[i] = EMPTY;
		}
		
	}	

	return best_res;
}
What I don't understand is how this code figures out which move is "best". I sort of see the concept...it iterates through all the possible moves on the board and then sets them to "1", but how does it actually "figure out" what the best place to move is? I know the concept of it iterating through all the possibilities of the positions of "X"'s and "O"'s, but I do not understand how this code actually does that. Can anyone sort of simplify things a little bit?

Share this post


Link to post
Share on other sites
Since I wrote that code I feel kinda obliged to answer. I think there are better resources on the net that can explain how gametrees work than what I could do here though. One good link is link.

Share this post


Link to post
Share on other sites
Quote:
Original post by doho
Since I wrote that code I feel kinda obliged to answer. I think there are better resources on the net that can explain how gametrees work than what I could do here though. One good link is link.


Thanks for the link - I hope you didn't mind me reposting your code here, I definately wasn't trying to take credit for it or anything. Your thread about the same topic basically helped me out some though as well.

Share this post


Link to post
Share on other sites

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