alpha_beta_pruning.c

#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

static char board_state[9];
static int values[9];
char ai_player = 'O', opponent = 'X';
int status = 0;

#define out_of_range(val, max) (val<0 || val >= max)
#define index(row, col) (row*3+col)
#define bytes_in_type(type, size) (sizeof(type)*size)

#define INF 9999999
static int possible_combinations[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 } };

bool is_move_possible(char *board, int row, int col) {
    if (out_of_range(row, 9)||out_of_range(col, 9)) return 0;
    return board_state[index(row, col)] == 0;
}

bool make_move(char *board, char player, int row, int col) {
    if (!is_move_possible(board, row, col))
        return 0;
    return board[index(row, col)] = player;
}

#define bool_ts(b) (b?"true":"false")
char check_game_winner(char *board) {
    for (int i=0; i< 8; ++i) {
        int *indexes = possible_combinations[i];
        if (board[indexes[0]] && board[indexes[0]] == board[indexes[1]] && board[indexes[1]] == board[indexes[2]]) {
            return board[indexes[0]];
        }
    }
    return 0;
}

bool moves_remaining(char *board) {
    for (int i =0; i < 9; ++i)
        if (board[i]==0) return 1;
    return 0;
}

int evaluate() {
    char winner;
    if (winner = check_game_winner(board_state)) {
        if (winner == ai_player) return 10;
        else return -10;
    }
    return 0;
}

#define max(val1, val2) (val1>val2?val1:val2)
#define min(val1, val2) (val1<val2?val1:val2)
#define next_player(curr_player) (curr_player=='X'?'O':'X')

int minmax(int h, bool is_max, int alpha, int beta) {
    int best_value, score, move_value;
    if (score = evaluate()) {
        if (is_max) return score-h;
        return score+h;
    }
    if(!moves_remaining(board_state)) {
        return 0;
    }
    if (is_max) {
        best_value = -10000; 
        bool should_break = false; 
        for (int r =0; r < 3 && !should_break; ++r) {
            for (int c =0; c < 3; ++c) {
                if (is_move_possible(board_state, r, c)) {
                    if(make_move(board_state, ai_player, r, c)){
                        move_value = minmax(h+1, !is_max, alpha, beta);
                        // printf("MAX: move_value: %d best_value: %d\n", move_value, best_value);
                        best_value = max(move_value, best_value);
                        alpha = max(best_value, alpha);
                        board_state[index(r, c)] = 0;
                        if(beta <= alpha) {
                            should_break = true;
                            break;
                        }
                    }
                }
            }
        }
        return best_value;
    }
    else {
        best_value = 10000;
        bool should_break = false;
        for (int r =0; r < 3 && !should_break; ++r) {
            for (int c =0; c < 3; ++c) {
                if (is_move_possible(board_state, r, c)) {
                    if(make_move(board_state, opponent, r, c)){
                        move_value = minmax(h+1, !is_max, alpha, beta);
                        // printf("Min: move_value: %d best_value: %d\n", move_value, best_value);
                        best_value = min(move_value, best_value);
                        beta = min(best_value, beta);
                        board_state[index(r, c)] = 0;
                        if(beta <= alpha) {
                            should_break = true;
                            break;
                        }
                    }
                }
            }
        }
        return best_value;
    }
    // printf("\n\n");
    return 0;
}


bool ai_move(char player) {
    if (!moves_remaining(board_state)) return 0;
    int best_value = -1000, move = -1, move_value;

    for (int row =0; row < 3; ++row) {
        for (int col =0; col < 3; ++col) {
            if (make_move(board_state, player, row, col)) {
                move_value = minmax(0, 0, -INF, INF);
                if (move_value > best_value) {
                    best_value = move_value;
                    move = index(row, col);
                }
                board_state[index(row, col)] = 0;
            }
        }
    }
    return board_state[move] = player;
}

void pretty_print() {
    printf("------------------------\n");
    for (int i = 0; i < 3; ++i) {
        printf("       |       |\n");
        for (int j = 0; j < 3; ++j) {
            char c =  board_state[index(i, j)];
            if (c) printf("   %c", board_state[index(i, j)]);
            else printf("   %d", index(i, j));
            if (j!=2) printf("   |");
        }
        printf("\n");
        if (i!=2)    printf("_______|_______|_______\n");
        else printf("       |       |\n");
    }
}

int main() {
    ai_player = 'O';
    while (moves_remaining(board_state) && !check_game_winner(board_state)) {
        pretty_print();
        int row, col;
        scanf("%d %d", &row, &col);
        printf("row and col are: %d %d\n", row, col);
        if (make_move(board_state, 'X', row, col)) {
            if (!check_game_winner(board_state)) {
                ai_move('O');
            }
            else break;

        }
        printf("\n\n");
    }
    pretty_print();
    char winner = check_game_winner(board_state);
    if (winner == 0)
        printf("Draw no one wins!!!!!!!!!!!!!!!!!");
    else printf("Player %c wins!!!!!", winner);
    printf("\n\n\n\nPresss enter to finish!!!!!!!!!!!!!!!");
    scanf("%c", &winner);
    return 0;
}