Minimax, URGENT :(

Im doing a invencible tic tac toe, but my minimax doesnt work -_- please I need to know where is my mistake, this is urgent

Code:

---

#include <algorithm>
#include <cstdlib>
using namespace std;


int cross;
int board[3][3] =
{
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
};


int winner( )
{
    for (int player = -1; player <= 1; player += 2) {
        for (int i = 0; i < 3; ++i) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
                return player;
            }
           
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player) {
                return player;
            }
        }
       
        if (board[1][1] == player) {
            if (board[0][0] == player && board[2][2] == player) {
                return player;
            }
       
            if (board[2][0] == player && board[0][2] == player) {
                return player;
            }
        }
    }
   
    return 0;
}


int best_move( )
{
    if (cross > 0) {
        int maxv = -2;
       
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    board[i][j] = cross;
                    cross = -cross;

                    maxv = max(maxv, best_move( ));
               
                    if (maxv == 1) {
                        return 1;
                    }
               
                    cross = -cross;
                    board[i][j] = 0;
                }
            }
        }
       
        return max(winner( ), maxv);
    }
    else {
        int minv = 2;
       
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    board[i][j] = cross;
                    cross = -cross;

                    minv = min(minv, best_move( ));
               
                    if (minv == -1) {
                        return -1;
                    }
               
                    cross = -cross;
                    board[i][j] = 0;
                }
            }
        }

        return min(winner( ), minv);
    }
}


int main( )
{
    cross = 1;
   
    int best_place;
    int max_result = -2;
   
    cross = 1;
   
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[i][j] == 0) {
                board[i][j] = cross;
                cross = -cross;
               
                int res = max(winner( ), best_move( ));
               
                if (max_result < res) {
                    best_place = (i * 3) + j;
                    max_result = res;
                }
               
                if (max_result == 1) {
                    return best_place;
                }
               
                cross = -cross;
                board[i][j] = 0;
            }
        }
    }

    return best_place;
}

---

I want the cross to win, cross will always play first
cross = 1, round = -1, withouth mark/tie = 0

please :(

http://www.catb.org/~esr/faqs/smart-...ns.html#urgent
That said, recursive functions and global variables are not going to work too well, if (as it seems) part of the recursive state is stored in the global.

ok just fixed:

Code:

---

#include <algorithm>
#include <cstdlib>
using namespace std;


int cross;
int board[3][3] =
{
    {0, 0, 0},
    {0, 0, 0},
    {0, 0, 0}
};


int winner( )
{
    for (int player = -1; player <= 1; player += 2) {
        for (int i = 0; i < 3; ++i) {
            if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
                return player;
            }
           
            if (board[0][i] == player && board[1][i] == player && board[2][i] == player) {
                return player;
            }
        }
       
        if (board[1][1] == player) {
            if (board[0][0] == player && board[2][2] == player) {
                return player;
            }
       
            if (board[2][0] == player && board[0][2] == player) {
                return player;
            }
        }
    }
   
    return 0;
}


int best_move( )
{
    if (cross > 0) {
        int maxv = -2;
       
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    board[i][j] = cross;
                    cross = -cross;

                    maxv = max(maxv, best_move( ));
               
                    cross = -cross;
                    board[i][j] = 0;
                }
            }
        }
       
        return max(winner( ), maxv);
    }
    else {
        int minv = 2;
       
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (board[i][j] == 0) {
                    board[i][j] = cross;
                    cross = -cross;

                    minv = min(minv, best_move( ));

                    cross = -cross;
                    board[i][j] = 0;
                }
            }
        }

        return min(winner( ), minv);
    }
}


int main( )
{
    cross = 1;
   
    int best_place;
    int max_result = -2;
   
    cross = 1;
   
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (board[i][j] == 0) {
                board[i][j] = cross;
                cross = -cross;
               
                int res = max(winner( ), best_move( ));
               
                if (max_result < res) {
                    best_place = (i * 3) + j;
                    max_result = res;
                }
               
                if (max_result == 1) {
                    return best_place;
                }
               
                cross = -cross;
                board[i][j] = 0;
            }
        }
    }

    return best_place;
}

---

still doesnt work :(

Code:

---

$ diff bar.cpp foo.cpp
56,59d55
<                    if (maxv == 1) {
<                        return 1;
<                    }
<
78,82c74
<
<                    if (minv == -1) {
<                        return -1;
<                    }
<

---

Explain how any of those changes have anything to do with removing your global variables.

I removed them because that inmediate quit from function would cause recursion state to not be completely cleared, I dont see any other place, if you do please help :(

best_move still calls best_move.

--
Mats

got it work, thanks