Thread: 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?

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.

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.

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();
}

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.