Thread: Minimax, URGENT :(

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    4

    Unhappy 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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    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

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    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

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    best_move still calls best_move.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    got it work, thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. urgent please please..
    By peter_hii in forum C++ Programming
    Replies: 4
    Last Post: 10-30-2006, 06:35 AM
  2. Minimax tree help
    By stonecold1654 in forum C Programming
    Replies: 1
    Last Post: 09-13-2005, 09:34 PM
  3. Help Needed: Borland C++ 5.5 Installation - URGENT!
    By Linette in forum C++ Programming
    Replies: 12
    Last Post: 03-09-2002, 06:44 PM
  4. help... urgent,... thanks!
    By weihann in forum C Programming
    Replies: 6
    Last Post: 02-28-2002, 10:17 PM
  5. Help.... Urgent... Thanks!
    By weihann in forum C Programming
    Replies: 0
    Last Post: 02-27-2002, 10:15 PM