Help with the min-max algorithm

This is a discussion on Help with the min-max algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi. A couple of days ago I posted the code for a dumb tic-tac-toe game I wrote and asked for ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    204

    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)
    {
    	// ????????
    }

  2. #2
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    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.

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    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;
    }

  6. #6
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Have you looked on the AI board yet? You might find something vaguely useful over there. And when you figure it out, maybe you can explain to me how to write negamax.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  7. #7
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    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.

  8. #8
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    its not hard.

    first look for a win in 1 move
    if no win look to see if opponent can win in 1 move
    if he can in more than 1 place then place random mark as its unstoppable
    if he can win in 1 sqaure only go there
    otherwise look for a strategic sqaure. how you do this is up to you.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  9. #9
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    What the evaluation function looks like will depend on what your board implementation looks like. For my board implementation, I chose to use two short integers to represent the moves. The first short was the moves for player 1, the other short for player 2. As an example, if the player 1 short was value 000 000 001b, that would indicate that player 1 chose to place an x in the bottom right corner, while if it was 100 000 000b, that would indicate that player 1 chose to x the top left corner. Assuming this is your board representation, you could check for a win by looking for one of the following ints:
    111 000 000b
    000 111 000b
    000 000 111b
    100 100 100b
    010 010 010b
    001 001 001b
    (etc.)

    So is your board representation correct? I have no idea. But it should return 1 if player 1 is winning, 0 if it is a cats game, and -1 if player 2 is winning. The rest depends on your particular board representation.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    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?

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    In Tic-Tac-Toe, it's very simple to give fields a tactical importance. Just calculate how many ways of winning it provides. You come up with:

    3 2 3
    2 4 2
    3 2 3

    Say, the player then places a piece in the center. The ways of winning are reduced:

    2 1 2
    1 X 1
    2 1 2

    Thus, the CPU randomly chooses one of the twos. A CPU piece does not reduce possibilities, it increases them (e.g. by 2), but it can't raise them from zero.

    O 3 4
    3 X 1
    4 1 2

    The player makes his move. This gives him a row-of-two, which leads to a big importance boost of 5.

    O 0 X
    3 X 0
    9 1 2

    The next move gives us a winning field, which raises importance by 10.

    O 0 X
    13X 0
    O 3 4

    O 0 X
    X X 5
    O 3 4

    O 0 X
    X X O
    O 3 4

    O 5 X
    X X O
    O X 4

    O O X
    X X O
    O X 4

    O O X
    X X O
    O X X

    Draw.

    Here's a winning game, CPU starts and player makes a mistake:

    5 4 4
    3 O X
    5 4 4

    O 4 4
    3 O X
    5 4 14

    O 4 9
    3 O X
    4 3 X

    O14 O
    3 O X
    14 3X

    O X O
    3 O X
    14 0X

    O X O
    3 O X
    O 0 X

    To sum up:
    1) Way a field participates in winning: +1
    2) Way a field participates in winning, with another spot of such a way taken by own piece: +2 (but not if importance after 1 is 0).
    3) Field is winning move for opponent: +5
    4) Field is winning move for self: +10
    5) Choose random among highest importances.
    Last edited by CornedBee; 05-10-2005 at 07:08 AM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    How to catch a draw: I assume that your array:

    char board[3][3];

    begins initialized to something like all 0. So a draw is when there are no zeros left (all slots have been chosen by 'x' or 'o'), AND there is not a win for 'x' or 'o'.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  13. #13
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help finding the max and min of a 2d array
    By finalreign in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 11:39 AM
  2. Max Min Problem
    By smithc2005 in forum C Programming
    Replies: 7
    Last Post: 10-22-2008, 10:38 AM
  3. Ranged numbers
    By Desolation in forum Game Programming
    Replies: 8
    Last Post: 07-25-2006, 10:02 PM
  4. Game of life
    By JoshR in forum C++ Programming
    Replies: 30
    Last Post: 04-03-2005, 02:17 PM
  5. Double output!
    By Spurnout in forum C++ Programming
    Replies: 3
    Last Post: 11-02-2002, 02:35 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21