Minimax (full tree search) tic-tac-toe AI in C

ttt.c

//Tic-tac-toe playing AI. Exhaustive tree-search. WTFPL
//Matthew Steel 2009, www.www.repsilat.com

#include <stdio.h>

char gridChar(int i) {
    switch(i) {
        case -1:
            return 'X';
        case 0:
            return ' ';
        case 1:
            return 'O';
    }
}

void draw(int b[9]) {
    printf(" %c | %c | %c\n",gridChar(b[0]),gridChar(b[1]),gridChar(b[2]));
    printf("---+---+---\n");
    printf(" %c | %c | %c\n",gridChar(b[3]),gridChar(b[4]),gridChar(b[5]));
    printf("---+---+---\n");
    printf(" %c | %c | %c\n",gridChar(b[6]),gridChar(b[7]),gridChar(b[8]));
}

int win(const int board[9]) {
    //determines if a player has won, returns 0 otherwise.
    unsigned wins[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};
    int i;
    for(i = 0; i < 8; ++i) {
        if(board[wins[i][0]] != 0 &&
           board[wins[i][0]] == board[wins[i][1]] &&
           board[wins[i][0]] == board[wins[i][2]])
            return board[wins[i][2]];
    }
    return 0;
}

int minimax(int board[9], int player) {
    //How is the position like for player (their turn) on board?
    int winner = win(board);
    if(winner != 0) return winner*player;

    move = -1;
    int score = -2;//Losing moves are preferred to no move
    int i;
    for(i = 0; i < 9; ++i) {//For all moves,
        if(board[i] == 0) {//If legal,
            board[i] = player;//Try the move
            int thisScore = -minimax(board, player*-1);
            if(thisScore > score) {
                score = thisScore;
                move = i;
            }//Pick the one that's worst for the opponent
            board[i] = 0;//Reset board after try
        }
    }
    if(move == -1) return 0;
    return score;
}

void computerMove(int board[9]) {
    int move = -1;
    int score = -2;
    int i;
    for(i = 0; i < 9; ++i) {
        if(board[i] == 0) {
            board[i] = 1;
            int tempScore = -minimax(board, -1);
            board[i] = 0;
            if(tempScore > score) {
                score = tempScore;
                move = i;
            }
        }
    }
    //returns a score based on minimax tree at a given node.
    board[move] = 1;
}

void playerMove(int board[9]) {
    int move = 0;
    do {
        printf("\nInput move ([0..8]): ");
        scanf("%d", &move);
        printf("\n");
    } while (move >= 9 || move < 0 && board[move] == 0);
    board[move] = -1;
}

int main() {
    int board[9] = {0,0,0,0,0,0,0,0,0};
    //computer squares are 1, player squares are -1.
    printf("Computer: O, You: X\nPlay (1)st or (2)nd? ");
    int player=0;
    scanf("%d",&player);
    printf("\n");
    unsigned turn;
    for(turn = 0; turn < 9 && win(board) == 0; ++turn) {
        if((turn+player) % 2 == 0)
            computerMove(board);
        else {
            draw(board);
            playerMove(board);
        }
    }
    switch(win(board)) {
        case 0:
            printf("A draw. How droll.\n");
            break;
        case 1:
            draw(board);
            printf("You lose.\n");
            break;
        case -1:
            printf("You win. Inconceivable!\n");
            break;
    }
}

in line number 43 have an error.
"move = -1;" must change to "int move = -1;"
thanks

A Critical Bug Found

In the above Code, the Player can always Win the Game by Overwriting the Computer move or Self move.

Bug Removed

The Problem Be Solved by making a Slight Change in playerMove function as follows:

void playerMove(int board[9]) {
int move = 0;
do {
start:
printf("\nInput move ([0..8]): ");
scanf("%d", &move);
if(board[move] != 0) {
printf("Its Already Occupied !");
goto start;
}
printf("\n");
} while (move >= 9 || move < 0 && board[move] == 0);
board[move] = -1;
}

Thanks for your sharing, but would you mind explaining for me a little bit about minimax function, i don't understand much what it's doing, thank fist ?

Excellent program!!!

you're a god damn genius

Ghost is right about that bug, however, there is a much better way of going about solving it.

In the playerMove function, take a look at that while loop one more time.
while (move >= 9 || move < 0 && board[move] == 0);

That doesn't look right at all. It would be better if you just changed it to this.
while (move >= 9 || move < 0 || board[move] != 0);

For people who want to understand why this works, let me explain myself. In the first while loop, it's giving two conditions.

1. If move is GREATER THAN OR EQUAL TO 9, it is not valid.
2. If move is LESS THAN 0 AND the chosen space is 0 (which means unoccupied in this case), it is not valid

That's a little weird, if the space is unoccupied, then the user should be able to place something there. Here are the conditions that my while loop states.

1. If move is GREATER THAN OR EQUAL TO 9, it is not valid.
2. If move is LESS THAN 0, it is not valid
3. If move IS NOT EQUAL TO 0 (meaning it is unoccupied), it is not valid.

Which makes a lot more sense.

A little note to the person who made this. You did a great job with this, in fact, this taught me how the minimax algorithm works. Mistakes happen, and that's fine. I'm just trying to teach people who can't understand why it's not working, why it was not working and how to get it working.

we well-written code. helped me a lot. than you.

You such a genius!

Heyy . I realize a serious error
When you choose to coincide with the machine. Break the minimax
sorry . my english is bad

code for this game using alpha beta purning?

Please tell guys how to hold the console output.

use system("pause")

Bug in Line-43
Initialize move integer as "int move".

Great implementation of min-max algorithm.
But why you are comparing 1-D Array (Board) with 2-D Array (Wins) in your win() method you could have just made your board as 2-D Array aswell like this unsigned board[3][3]; that would have made comparison much easier.

Thanks for this code. It is really good but I just don't get why have you used the - sign before the minimax function

Hey! Nice code!

The thing I thought a lot, and cant still understand is when the line 57 is executed. It seems it is executed when the game is tie, but line 52 wil never let line 57 get executed. Anyone could explain it?

Hey! Nice code!

The thing I thought a lot, and cant still understand is when the line 57 is executed. It seems it is executed when the game is tie, but line 52 wil never let line 57 get executed. Anyone could explain it?

It will happen at some point in the program, since if there are no moves left naturally move will be initialized as - 1 in one of the branches of the tree.

Bug in Line-43 Initialize move integer as "int move".

Guys keep this bug in mind and don't forget to initialize this before running. Just change move = -1 to int move = -1