#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
#include <unistd.h>
#include <termios.h>
#include <time.h>

typedef struct 
{
    uint16_t bm; 
    char icon;
} Player;

typedef struct
{
    Player max_player;
    Player min_player;
} Board;

const uint16_t wincombs[8] = {
        0b111000000, 0b000111000, 0b000000111, 0b100100100, 
        0b010010010, 0b001001001, 0b100010001, 0b001010100};

void render(Board *board);
uint8_t askmove(Board *board, char *player); 
uint8_t evaluate(Board *board);
void checkposition(Board *board);
uint8_t minimax_alpha_beta(Board *board, bool ismax, uint8_t alpha, uint8_t beta);
uint8_t best_move(Board *board, bool ismax);
unsigned int random_number(unsigned int limit);

int main(void) 
{
    Board activeBoard = {
        .max_player = {.bm = 0b000000000, .icon = 'x'}, 
        .min_player = {.bm = 0b000000000, .icon = 'o'}
    };
    uint8_t user_move;
    uint8_t computer_move;

    time_t time = clock();
    computer_move = best_move(&activeBoard, false);
    time = clock() - time;

    double exec_time = ((double) time) / CLOCKS_PER_SEC;
    printf("bestmove function took %f seconds\n", exec_time);
    int scanvar;
    scanf("%d", &scanvar);

    while (true) {
        checkposition(&activeBoard);
        render(&activeBoard);
        user_move = askmove(&activeBoard, &activeBoard.max_player.icon);
        activeBoard.max_player.bm ^= 0b100000000 >> user_move;
        checkposition(&activeBoard);
        computer_move = best_move(&activeBoard, false);
        activeBoard.min_player.bm ^= 0b100000000 >> computer_move;
    }
    return 0;
}

void render(Board *board) 
{
    uint8_t i;
    uint16_t wincomb;
    uint16_t color_bm = 0b000000000;

    for (i = 0; i < 8; i++) {
        wincomb = wincombs[i];
        if ((wincomb & board->max_player.bm) == wincomb || (wincomb & board->min_player.bm) == wincomb) {
            color_bm |= wincomb;
        }
    }
    printf(
        "\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n───┼───┼───\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n───┼───┼───\n %s%c\x1b[0m │ %s%c\x1b[0m │ %s%c\x1b[0m \n", 
        (0b100000000 & color_bm) ? "\x1b[7m" : "", 
        (0b100000000 & board->max_player.bm) ? board->max_player.icon : (0b100000000 & board->min_player.bm) ? board->min_player.icon : '1', 
        (0b010000000 & color_bm) ? "\x1b[7m" : "", 
        (0b010000000 & board->max_player.bm) ? board->max_player.icon : (0b010000000 & board->min_player.bm) ? board->min_player.icon : '2', 
        (0b001000000 & color_bm) ? "\x1b[7m" : "", 
        (0b001000000 & board->max_player.bm) ? board->max_player.icon : (0b001000000 & board->min_player.bm) ? board->min_player.icon : '3', 
        (0b000100000 & color_bm) ? "\x1b[7m" : "", 
        (0b000100000 & board->max_player.bm) ? board->max_player.icon : (0b000100000 & board->min_player.bm) ? board->min_player.icon : '4', 
        (0b000010000 & color_bm) ? "\x1b[7m" : "", 
        (0b000010000 & board->max_player.bm) ? board->max_player.icon : (0b000010000 & board->min_player.bm) ? board->min_player.icon : '5', 
        (0b000001000 & color_bm) ? "\x1b[7m" : "", 
        (0b000001000 & board->max_player.bm) ? board->max_player.icon : (0b000001000 & board->min_player.bm) ? board->min_player.icon : '6', 
        (0b000000100 & color_bm) ? "\x1b[7m" : "", 
        (0b000000100 & board->max_player.bm) ? board->max_player.icon : (0b000000100 & board->min_player.bm) ? board->min_player.icon : '7', 
        (0b000000010 & color_bm) ? "\x1b[7m" : "", 
        (0b000000010 & board->max_player.bm) ? board->max_player.icon : (0b000000010 & board->min_player.bm) ? board->min_player.icon : '8', 
        (0b000000001 & color_bm) ? "\x1b[7m" : "", 
        (0b000000001 & board->max_player.bm) ? board->max_player.icon : (0b000000001 & board->min_player.bm) ? board->min_player.icon : '9'
    );
}

uint8_t askmove(Board *board, char *player)
{
    static struct termios term_settings;
    char c;
    uint16_t empty_cells = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
    uint8_t i;
    uint16_t cell_bm;

    /* changing term settings for special input */
    tcgetattr(STDIN_FILENO, &term_settings);
    term_settings.c_lflag ^= ICANON | ECHO;
    tcsetattr(STDIN_FILENO, TCSANOW, &term_settings);

    printf("\nWhere do you want to place your %c?\n", *player);

    while ((c = getc(stdin)) != EOF) {
        for (i = 0; i < 9; i++) {
            cell_bm = 0b100000000 >> i;
            if (empty_cells & cell_bm && c - '1' == i) {

                /* restoring old term settings */
                term_settings.c_lflag ^= ICANON | ECHO;
                tcsetattr(STDIN_FILENO, TCSANOW, &term_settings);

                return i;
            }
        }
    }
    exit(0);
}

uint8_t evaluate(Board *board) 
{
    uint8_t i;
    uint16_t wincomb;

    /* 
    0 -> position not terminal
    1 reserved for -infinity
    2 -> player2 wins
    3 -> draw = noone wins
    4 -> player1 wins
    5 reserved for infinity
    */

    for (i = 0; i < 8; i++) {
        wincomb = wincombs[i];
        if ((wincomb & board->max_player.bm) == wincomb) {
            return 4;
        }
        if ((wincomb & board->min_player.bm) == wincomb) {
            return 2;
        }
    }
    if ((board->max_player.bm | board->min_player.bm) == 0b111111111) {
        return 3;
    }
    return 0;
}

void checkposition(Board *board)
{
    uint8_t eval = evaluate(board);
    uint16_t color_bm;
    uint8_t i;
    uint16_t wincomb;

    if (eval) {
        render(board);
        if (eval == 3) {
            printf("\nDRAW\n\n");
        } else if (eval == 4) {
            printf("\n%c won the game!\n\n", board->max_player.icon);
        } else if (eval == 2) {
            printf("\n%c won the game!\n\n", board->min_player.icon);
        }
        exit(0);
    }
}

uint8_t minimax_alpha_beta(Board *board, bool ismax, unsigned char alpha, unsigned char beta)
{
    uint16_t empty_cells_bm = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
    uint8_t eval = evaluate(board);
    uint8_t bestvalue;
    uint8_t i;
    uint16_t cell_bm;
    uint8_t minimax_value;

    if (eval) {
        return eval;
    }

    if (ismax) {
        bestvalue = 1;
        for (i = 0; i < 9; i++) {
            cell_bm = 0b100000000 >> i;
            if (cell_bm & empty_cells_bm) {
                board->max_player.bm ^= cell_bm;
                minimax_value = minimax_alpha_beta(board, false, alpha, beta);
                board->max_player.bm ^= cell_bm;
                if (minimax_value > bestvalue) {
                    bestvalue = minimax_value;
                    if (bestvalue > alpha) {
                        alpha = bestvalue;
                    }
                    if (alpha >= beta) {
                        break;
                    }
                }
            }
        }
    } else {
        bestvalue = 5;
        for (i = 0; i < 9; i++) {
            cell_bm = 0b100000000 >> i;
            if (cell_bm & empty_cells_bm) {
                board->min_player.bm ^= cell_bm;
                minimax_value = minimax_alpha_beta(board, true, alpha, beta);
                board->min_player.bm ^= cell_bm;
                if (minimax_value < bestvalue) {
                    bestvalue = minimax_value;
                    if (bestvalue < beta) {
                        beta = bestvalue;
                    }
                    if (alpha >= beta) {
                        break;
                    }
                }
            }
        }
    }
    return bestvalue;
}

uint8_t best_move(Board *board, bool ismax) 
{
    uint8_t bestvalue;
    uint8_t i;
    uint16_t cell_bm;
    uint16_t empty_cells_bm = ~(board->max_player.bm | board->min_player.bm) & 0b111111111;
    uint8_t minimax_value;
    uint8_t cell_values[9];
    uint8_t ctr = 0;
    uint8_t choice;

    if (ismax) {
        bestvalue = 1;
        for (i = 0; i < 9; i++) {
            cell_bm = 0b100000000 >> i;
            if (cell_bm & empty_cells_bm) {
                board->max_player.bm ^= cell_bm;
                minimax_value = minimax_alpha_beta(board, !ismax, 1, 5);
                board->max_player.bm ^= cell_bm;
                if (minimax_value == bestvalue) {
                    cell_values[i] = minimax_value;
                    ++ctr;
                } else if (minimax_value > bestvalue) {
                    bestvalue = minimax_value;
                    cell_values[i] = minimax_value;
                    ctr = 1;
                }
            }
        }
    } else {
        bestvalue = 5;
        for (i = 0; i < 9; i++) {
            cell_bm = 0b100000000 >> i;
            if (cell_bm & empty_cells_bm) {
                board->min_player.bm ^= cell_bm;
                minimax_value = minimax_alpha_beta(board, !ismax, 1, 5);
                board->min_player.bm ^= cell_bm;
                if (minimax_value == bestvalue) {
                    cell_values[i] = minimax_value;
                    ++ctr;
                } else if (minimax_value < bestvalue) {
                    bestvalue = minimax_value;
                    cell_values[i] = minimax_value;
                    ctr = 1;
                }
            }
        }
    }
    choice = random_number(ctr);
    for (i = 0; i < 9; i++) {
        if (cell_values[i] == bestvalue) {
            if (!choice) {
                return i;
            } else {
                --choice;
            }
        }
    }
    return 0b11111111;
}

unsigned int random_number(unsigned int limit)
{
    srand(time(0));
    return rand() % limit;
}

/* python exectime > 0.066766 */
/* C exectime > 0.003077 */