1. ## 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. 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.

3. 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...

4. 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*

5. 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. 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.

7. 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. 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. 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.