Thread: Tic Tac Toe Minimax Algorithm Problem

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    3

    Post Tic Tac Toe Minimax Algorithm Problem

    Hey guys I'm actually new here, kinda hoping this community will help me alot with my learning.

    Well my problem is with my minimax algorithm for tic-tac-toe. The code works, there's just some slight problem, the computer doesn't play perfectly. Sure it can draw you almost everytime, but sometimes, it doesn't see forks, or will even play randomly. So, here's the minimax code, written in c++.

    Code:
    int minimax( char _board[9] )
    {
    	short int i;
    	int bestValue = +INFINITY, index = 0;
    	char bestMoves[9] = {0};
    	for( i = 0; i < 9; i++ )
    	{
    		if( _board[i] == empty )
    		{
    			_board[i] = o;
    			int value = maxSearch( _board );
    			if( value < bestValue )
    			{
    				bestValue = value;
    				index = 0;
    				bestMoves[index] = i;
    			}
    			else if( value == bestValue )
    				bestMoves[index++] = i;
    			_board[i] = empty;
    		}
    	}
    	if( index > 0 )
    		index = rand() % index;
    	return bestMoves[index];
    }
    int minSearch( char _board[9] )
    {
    	short int i;
    	int positionValue = gameState(_board);
    	if( positionValue == DRAW ) return 0;
    	if( positionValue != INPROGRESS ) return positionValue;
    	int bestValue = +INFINITY;
    	for( i = 0; i < 9; i++ )
    	{
    		if( _board[i] == empty )
    		{
    			_board[i] = o;
    			int value = maxSearch( _board );
    			if( value < bestValue )
    				bestValue = value;
    			_board[i] = empty;
    		}
    	}
    	return bestValue;
    }
    int maxSearch( char _board[9] )
    {
    	short int i;
    	int positionValue = gameState(_board);
    	if( positionValue == DRAW ) return 0;
    	if( positionValue != INPROGRESS ) return positionValue;
    	int bestValue = -INFINITY;
    	for( i = 0; i < 9; i++ )
    	{
    		if( _board[i] == empty )
    		{
    			_board[i] = x;
    			int value = minSearch( _board );
    			if( value > bestValue )
    				bestValue = value;
    			_board[i] = empty;
    		}
    	}
    	return bestValue;
    }
    So yeah, the symbols are fixed, 'x' is for the player, and 'o' is for the computer. And yeah, the computer plays as the minimizer. I was actually thinking of implementing depth, the more shallow the leafnode (the last position, whether win for x or o, or a draw), the better the score. So, what do you guys think?

  2. #2
    Registered User
    Join Date
    Oct 2010
    Posts
    3
    Oh, I'm sorry guys. It turns out that there was some minor bug in my gameState() function that sometimes returns draw even if it is a win, and that messes up the minimax. Thanks for the view anyways. lol

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,739
    Quote Originally Posted by hello.world View Post
    Oh, I'm sorry guys. It turns out that there was some minor bug in my gameState() function that sometimes returns draw even if it is a win, and that messes up the minimax. Thanks for the view anyways. lol
    Yeah, lol

    But i see no point in making a game if it is impossible for a player to win!
    Devoted my life to programming...

  4. #4
    Registered User
    Join Date
    Oct 2010
    Posts
    3
    Quote Originally Posted by Sipher View Post
    Yeah, lol

    But i see no point in making a game if it is impossible for a player to win!
    Well I was really planning to implement alpha-beta search with my chess program, and it's my first shot with these algorithms and stuff, so I tried it in a simpler game first, just to make sure it works.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Tic Tac Toe AI help please...
    By Rune Hunter in forum Game Programming
    Replies: 12
    Last Post: 11-05-2004, 04:24 PM
  2. Help with Tic Tac Toe game
    By snef73 in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2003, 08:33 AM
  3. Tic Tac Toe display problem
    By Munkey01 in forum Game Programming
    Replies: 9
    Last Post: 03-01-2003, 06:35 PM
  4. Need some help with a basic tic tac toe game
    By darkshadow in forum C Programming
    Replies: 1
    Last Post: 05-12-2002, 04:21 PM
  5. Replies: 22
    Last Post: 11-08-2001, 11:01 PM

Tags for this Thread