Thread: Help with the min-max algorithm

Hi. A couple of days ago I posted the code for a dumb tic-tac-toe game I wrote and asked for ideas on how to make it smart. People told me to use the min-max algorithm and also provided me with source code to look at. Since then, I've read a lot about the min-max algorithm and looked at other people's source code but I am having a REALLY hard time trying to implement it on my code. Can someone look at my code and give me some hints on how to do it? Thanks a lot.

Code:

#include <iostream>
#include <string>
#include <cctype>
#include <windows.h>

void show_board(void);
void human_move(void);
void computer_move(void);
bool valid_coordinate(std::string &);
char check_board(void);

char board[3][3];

int main()
{
	char result = ' ';

	SetConsoleTitle("Tic-Tac-Toe");

	for(int i = 0; i < 3; i++)
		for(int j = 0; j < 3; j++)
			board[i][j] = ' ';

	show_board();

	while(result == ' '){
		human_move();
		show_board();
		result = check_board();

		if(result == 'X')
		{
			std::cout << "\nYou win!\n";
			break;
		}

		computer_move();
		show_board();
		result = check_board();

		if(result == 'O')
		{
			std::cout << "\nI win!\n";
			break;
		}
	}

	std::cin.get();

	return 0;
}

void show_board(void)
{
	// Change or remove this if the compiler gives you erros
	system("cls");

	std::cout << "  A   B   C\n\n";

	for(int j = 0; j < 3; j++){
		std::cout << j + 1 << " "
			<< board[j][0] << " | "
			<< board[j][1] << " | "
			<< board[j][2] << '\n';

		if(j != 2)
			std::cout << " ---|---|---\n";
	}

	std::cout << '\n';
}

void human_move(void)
{
	std::string coordinate;

	do{
		std::cout << "Coordinates for X: ";
		std::getline(std::cin, coordinate);
	}while(!valid_coordinate(coordinate));
}

bool valid_coordinate(std::string &coordinate)
{
	if(coordinate.length() == 0){
		std::cout << "You must provide the coordinates for X ";
		std::cin.get();
		show_board();
		return false;
	}

	if(coordinate.length() > 2){
		std::cout << "Coordinates cannot be more than two characters long ";
		std::cin.get();
		show_board();
		return false;
	}

	if(!isdigit(coordinate[0]) || !isalpha(coordinate[1])){
		std::cout << "Type a number followed by a letter. Ex: 1a ";
		std::cin.get();
		show_board();
		return false;
	}

	int x = coordinate[0];
	x -= 48;

	if(x < 1 || x > 3){
		std::cout << "Number out of range 1-3 ";
		std::cin.get();
		show_board();
		return false;
	}

	// C++ starts counting at 0, that's why I do this
	x--;

	char z = coordinate[1];

	if(toupper(z) < 'A' || toupper(z) > 'C'){
		std::cout << "Letter out of range A-C ";
		std::cin.get();
		show_board();
		return false;
	}

	int y;

	switch(toupper(z)){
		case 'A':
			y = 0;
			break;

		case 'B':
			y = 1;
			break;

		case 'C':
			y = 2;
			break;
	}

	// Check if the position is free
	if(board[x][y] != ' '){
		std::cout << "This position is already taken ";
		std::cin.get();
		show_board();
		return false;
	}

	// Makes the move
	board[x][y] = 'X';

	return true;
}

char check_board(void)
{
	int i;

	for(i = 0; i < 3; i++)
		if(board[i][0] == board[i][1] && board[i][0] == board[i][2])
			return board[i][0];

	for(i = 0; i < 3; i++)
		if(board[0][i] == board[1][i] && board[0][i] == board[2][i])
			return board[0][i];

	if(board[0][0] == board[1][1] && board[1][1] == board[2][2])
		return board[0][0];

	if(board[0][2] == board[1][1] && board[1][1] == board[2][0])
		return board[0][2];

	return ' ';
}

void computer_move(void)
{
	// ????????
}

Considering you haven't even started to write the function, its kind of hard to help. Do you have a specific question on min-max functions in general? As long as you have a function that can evaluate a board-state, most min-max's are pretty much the same.

Ok, so first I need a function to evaluate the board and look for a winner or a draw? Does this function have to return a specific type? Thanks.

caduardo21, min-max requires a min function that searches for the best evaluation with respect to the other player and a max function that searches for the best evaluation with respect to the player who's turn it is to move. Along with these two functions, you need an eval function which will statically evaluation the board. But just return an integer value here; you know this can only return three values: -1, 0, 1.

I'll try to understand all of this and I ask you guys to bare with me please
How about this for the board evaluation function?

Code:

int evaluate_board(const char &player)
{
	int i;

	for(i = 0; i < 3; i++)
	{
		if(board[i][0] == player && board[i][0] == player)
		{
			if(player == 'X')
				return 1;

			else
				return -1;
		}
	}

	for(i = 0; i < 3; i++)
	{
		if(board[0][i] == player && board[0][i] == player)
		{
			if(player == 'X')
				return 1;

			else
				return -1;
		}
	}

	if(board[0][0] == player && board[1][1] == player)
	{
		if(player == 'X')
			return 1;

		else
			return -1;
	}

	if(board[0][2] == player && board[1][1] == player)
	{
		if(player == 'X')
			return 1;

		else
			return -1;
	}

	// It would be good to check for a draw here also, right?

	return 0;
}

I'm trying to get the min-max thingy going first, function by function

I think I've looked at your tic-tac-toe game but as I said, I am having a hard time understand this algorithm.

So, is this how the evaluation function must look like?

Thanks.

I'm using a simple multi-subscripted array:
char board[3][3];

So I think my evaluation function is correct. It returns 1 if X wins, -1 if O wins and 0 if nobody wins. Any ideas on how to catch a draw?

Since the sample space for board states is so small for tic-tac-toe, there is never a reason to evaluate the board before the end. If you simply have a function that says 'X' won, 'O' won, or all spaces are taken and noone won, then you have all you need for the min-max. The way you have it set up as -1,0,1 is perfect.