# Tic Tac Toe Minimax Algorithm Problem

• 10-22-2010
hello.world
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?
• 10-22-2010
hello.world
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 :)
• 10-23-2010
GReaper
Quote:

Originally Posted by hello.world
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!
• 10-24-2010
hello.world
Quote:

Originally Posted by Sipher
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.