Why no persistence?

This is a discussion on Why no persistence? within the C Programming forums, part of the General Programming Boards category; I had a go at making a simple minimax prog, but its not working. Basically I want to pass an ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    Why no persistence?

    I had a go at making a simple minimax prog, but its not working. Basically I want to pass an instance of the grid by value to each recursive function call. In the function it then places then evaluates a new move. For some reason the grid states dont seem to be changing, when I place a new move at the beginning of the minimax function.
    Code:
    #include <stdio.h>
    
    void show(char* grid)
    {
        printf("  A B C\n");
        for(int r=0; r<9; r+=3)
            printf("%d %c %c %c\n", (r/3)+1, grid[r], grid[r+1], grid[r+2]);            
    }
    
    bool is_win(char* grid, char player)
    {
        char p = (player)?'X':'O';
        for(int r=0; r<9; r+=3) 
            if(grid[r]==p&&grid[r+1]==p&&grid[r+2]==p) 
                return true;  
        for(int c=0; c<3; c++)
            if(grid[c]==p&&grid[3+c]==p&&grid[6+c]==p) 
                return true;  
        if(grid[0]==p&&grid[4]==p&&grid[8]==p)
            return true;
        if(grid[2]==p&&grid[4]==p&&grid[6]==p)
            return true;
        return false;
    }
    
    int minimax(char* grid, int player, int pos)
    {
        if(pos != -1)grid[pos]=(player)?'X':'O';
        show(grid);
    
        if(is_win(grid, player)) return 1;
        int weight = -999999;
        for(int i=0; i<9; i++)  // For each cell
        { 
            if(grid[i] != ' ')  // If cell is free
            {
                int temp = 0-minimax(grid, player^=1, i);  //negative value switches to opponent and back
                if(temp > weight) weight = temp;
            }
        }
        if(weight == -999999) return 0; // board is full
        return weight; 
    }
    
    int main()
    {   
        char grid[9]=
        {
            'O', 'O', 'X', 
            ' ', 'X', ' ', 
            'O', 'X', ' '
        };
        minimax(grid, 1, -1);
        getchar();
    }
    Why is this?

  2. #2
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Lol, found it just after posting. This:
    Code:
    if(grid[i] != ' ')  // If cell is free
    Was a bit wrong >_<

    Still its not giving me all move permutations for some reason, so the code is still buggy.
    Last edited by mike_g; 02-07-2009 at 10:19 AM.

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    One pattern which you typically see in this sort of code is:

    Code:
    if can make move:
        make move;
        evaluate_move;
        undo move;
    I don't see where you use the latter (it can't be possible that you stumble upon the best moves just like that, without trying different options).

    Also, minimax should probably return the best move to make. Just knowing the value of the best move is not enough...
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    Like anon said, you need to actually make and unmake the moves.

    I would make the signature for minimax (or negamax since you are negating the scores)
    Code:
    int negamax(char* grid, int side_to_move); 
    //returns how good the grid is for the moving side
    //1 for win, 0 for draw, -1 for loss
    //doesn't modify grid (meaning it will have to make and unmake moves)
    *edit*
    Assuming you only need to choose a move to make, make a separate function that calls negamax on all possible moves, and return the move with highest score.

    If you want a "principal variation" line (the program's prediction of how the game will go on), you will need to pass an array around.
    */edit*
    Last edited by cyberfish; 02-07-2009 at 02:50 PM.

  5. #5
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Yeah I got it going though all the combos. And theres been quite a few changes. Still got to work out the weighting system tho.

    The way I got it working it dosent need to unmake moves, but the function is copying the grid each time its called. Will look at better ways to do it, if poss.

    Anyway, will post back with code later.

    Cheers.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I've never seen minimax without DFS before. Likewise, I've never seen it without making & unmaking moves.

    EDIT: Yes, he's using DFS - it looks so very small with TTT,

    A suggestion for the evalu8. If your m/max see's a win, it needs to also get weighted a bit less, if the win is further away (deeper in the search tree).

    Without that, your move selection may be perfectly happy to make any move that wins, at any depth, instead of the move that wins at the shallowest depth (the quickest).

    May not be a problem with TTT, but in Chess it can lead to the funny situation where the program see's the win, but keeps delaying the checkmating move, because all the moves see the deep checkmate, so they all have the same evaluation.
    Last edited by Adak; 02-08-2009 at 02:55 PM.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    I believe this is DFS.

    Unmaking moves is not strictly necessary if you make copies of the board all the time and throw old ones away, but people don't do that in chess (and use make/unmake instead) because it's slower (especially since a chess board requires at least tens of bytes to represent). For TTT, though, efficiency hardly matters, since there are only 9! or so nodes to search at most.

    I agree quicker wins should be scored higher (and further losses), but you may want to leave it until you finish your basic minimax.

    The way to do it is to score a win as something like "1000 - moves_to_win", so 1000 is a win on the board, 999 is win-in-1, 998 is win-in-2, etc. And of course, losses as "-1000 + moves_to_loss".

    And then, in minimax, when you see a win or loss on the board, score them as 1000 and -1000. Otherwise, if the score is > 800, decrement it by 1 before returning, and vice versa for losses.

  8. #8
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Ok, I fixed it. I'm undoing moves instead of copying the grid and the weighting system seems to work right for any of the test data I have tried. Still have to add alpha-beta pruning tho.
    Code:
    #include <stdio.h>
    #define DEBUG 0     /* prints gridstates. Not recommended for deep searches */
    
    void show(char* grid)
    {
        printf("  A B C\n");
        for(int r=0; r<9; r+=3)
            printf("%d %c %c %c\n", (r/3)+1, grid[r], grid[r+1], grid[r+2]);  
        putchar('\n');          
    }
    
    bool is_win(char* grid, char player)
    {
        char p = (player)?'X':'O';
        for(int r=0; r<9; r+=3) 
            if(grid[r]==p&&grid[r+1]==p&&grid[r+2]==p) 
                return true;  
        for(int c=0; c<3; c++)
            if(grid[c]==p&&grid[3+c]==p&&grid[6+c]==p) 
                return true;  
        if(grid[0]==p&&grid[4]==p&&grid[8]==p)
            return true;
        if(grid[2]==p&&grid[4]==p&&grid[6]==p)
            return true;
        return false;
    }
    
    int minimax(char* grid, int player, int pos, int depth)
    {
        int weight = -999999;
        int opponent = player^=1;
    
        grid[pos]=(player)?'X':'O';  // Make Move
        if(DEBUG) show(grid);
        
        if(is_win(grid, player))
        {
            grid[pos]=' ';
            if(DEBUG)printf((player)?"WIN!\n":"LOSE!\n"); 
            return (depth*10); 
        }
    
        for(int i=0; i<9; i++)  // For each cell
        { 
            if(grid[i] == ' ')  // If cell is free
            {
                //negative value switches to opponent and back depth value (multiplier) reduced each ply only
                int temp = 0-minimax(grid, opponent, i, (player)?depth:depth-1);  
                if(weight== -999999)
                    weight=temp;
                else
                    weight+=temp;
            }
        }
        grid[pos]=' '; // Undo Move Made
        if(weight == -999999)// board is full
        {
            if(DEBUG)printf("DRAW!\n");
            return 0;
        } 
        return weight; // return the highest weight?
    }
    
    void choose_move(char* grid, int player, int depth)
    {
        show(grid);
        int weights[9];   // Set by mimimax function
        for(int i=0; i<9; i++)
            weights[i]=-9999999;
        for(int i=0; i<9; i++)      // For each cell
        { 
            if(grid[i] == ' ')      // If cell is free
            {
                weights[i] = minimax(grid, player, i, depth);  
            }
        }    
        for(int i=0; i<9; i++)
            printf("%c%d: %d\n", 'A'+(i%3), (i/3)+1, weights[i]);
    
    }
    
    int get_depth(char* grid) /* Gets the number of turns until the end of the game by assessing the board state */
    {
        int depth = 0;
        for(int i=0; i<9; i++)
            if(grid[i]==' ')depth++;
        return depth;
    }
    
    
    int main()
    {   
        //Players: 1 = X ; 0 = Y
        char grid[9]=
        {
            ' ', ' ', ' ', 
            ' ', ' ', ' ', 
            ' ', ' ', ' '
        };
        int depth = get_depth(grid);
        choose_move(grid, 1, depth);
        getchar();
    }

  9. #9
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,170
    You can add alpha-beta pruning for practice, but you probably don't need it since TTT is a tiny tree.

    If you want to get more practice with minimax/alpha-beta, you can switch to a slightly larger game such as Othello. You will also need a heuristic function for that since it's not possible to search the whole tree in Othello, unlike TTT.

    Or maybe something like chess, but it's a lot more complex (move generation, repetition draws, horizon effect, etc), and Othello is a lot easier in terms of rules, and has a tree large enough to force you to use alpha-beta and a heuristic function.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Persistence of network events
    By Hunter2 in forum Networking/Device Communication
    Replies: 0
    Last Post: 10-02-2004, 08:38 PM
  2. Object Persistence
    By IndigoTangoOne in forum C++ Programming
    Replies: 4
    Last Post: 08-21-2003, 02:30 AM
  3. Chemtrails?
    By frenchfry164 in forum A Brief History of Cprogramming.com
    Replies: 70
    Last Post: 06-15-2003, 11:07 PM
  4. Image persistence (cue Twilight Zone theme...)
    By SMurf in forum Windows Programming
    Replies: 3
    Last Post: 04-21-2002, 10:24 PM

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