/**
 * alpha_beta.c
 * Copyright (C) 2008 Markus Broeker
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define BOARD_SIZE 9
#define EMPTY 32

struct Move {
    int target;
    int value;
};

typedef struct Move Move;

struct Node {
    Move *data;
    struct Node *prev;
};

typedef struct Node Node;

Move *bestMove;

Node *stack_end;

char board[BOARD_SIZE] = {
    EMPTY, EMPTY, EMPTY,
    EMPTY, EMPTY, EMPTY,
    EMPTY, EMPTY, EMPTY,
};

int desired_depth = -1;

int estimateFunction ();
int max_alpha_beta (int, int, int);
int min_alpha_beta (int, int, int);
void print (void);

/**
 * push: push a move onto the stack
 */
void push (Move * move)
{
    Node *actual;

    if ((actual = malloc (sizeof (Node))) == NULL) {
        perror ("MALLOC");
        exit (EXIT_FAILURE);
    }

    actual->data = move;
    actual->prev = stack_end;

    stack_end = actual;
}

/**
 * undo: revert the last move on the stack
 */
void undo ()
{
    Node *actual;

    if (stack_end == NULL) {
        printf ("Stack underrun\n");
        return;
    }

    board[stack_end->data->target] = EMPTY;

    actual = stack_end->prev;
    free (stack_end);

    stack_end = actual;
}

/**
 * validMove returns true(1) when the inspected field is EMPTY
 */
int validMove (int t)
{
    if (board[t] == EMPTY)
        return 1;
    return 0;
}

/**
 * Returns a Score of +-50 for 3 in a Row
 */
int estimateFunction ()
{
    if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X')
        return -50;
    if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O')
        return 50;

    if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X')
        return -50;
    if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O')
        return 50;

    if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X')
        return -50;
    if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O')
        return 50;

    if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X')
        return -50;
    if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O')
        return 50;

    if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X')
        return -50;
    if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O')
        return 50;

    if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X')
        return -50;
    if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O')
        return 50;

    if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X')
        return -50;
    if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O')
        return 50;

    if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X')
        return -50;
    if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O')
        return 50;

    return 0;
}

/**
 * this function visualizes the board
 */
void print ()
{
    int i;

    printf ("       1   2   3  \n     +---+---+---+\n");
    for (i = 0; i < 3; i++) {
        printf ("  %d  | ", i + 1);
        printf ("%c", board[3 * i]);
        printf (" | ");
        printf ("%c", board[3 * i + 1]);
        printf (" | ");
        printf ("%c", board[3 * i + 2]);
        printf (" | \n");
        printf ("     +---+---+---+\n");
    }
    if (stack_end->data != NULL)
        printf ("Score: %3d\n", stack_end->data->value);
}

/**
 * simulates and returns the next possible move for a Player or null, when no more moves are possible.
 */
Move *simulate (int t, int player)
{
    Move *move;

    while (t < BOARD_SIZE) {
        if (!validMove (t)) {
            t++;
            continue;
        }

        if ((move = malloc (sizeof (Move))) == NULL) {
            perror ("MALLOC");
            exit (EXIT_FAILURE);
        }

        if (player == 0)
            board[t] = 'O';
        else
            board[t] = 'X';

        move->target = t;
        move->value = estimateFunction ();

        push (move);

        return move;
    }
    return NULL;
}

/**
 * AlphaBeta-Algorithm: the Maximizer
 */
int max_alpha_beta (int depth, int alpha, int beta)
{
    int moveValue;

    int t;

    Move *move;

    if (desired_depth == -1)
        desired_depth = depth;

    t = 0;
    while ((move = simulate (t, 0)) != NULL) {
        /*
         * particular move from black
         */
        t = move->target;

        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
            moveValue = move->value;
        else                    /* best next move */
            moveValue = min_alpha_beta (depth - 1, alpha, beta);

        print ();
        undo ();
        t++;

        if (moveValue >= beta) {
            free (move);
            return beta;
        }

        if (moveValue > alpha) {
            alpha = moveValue;
            if (depth == desired_depth) {
                if (bestMove != NULL)
                    free (bestMove);
                bestMove = move;
                continue;
            }
        }
        free (move);
    }

    return alpha;
}

/**
 * AlphaBeta-Algorithm: the Minimizer
 */
int min_alpha_beta (int depth, int alpha, int beta)
{
    int moveValue;

    int t;

    Move *move;

    t = 0;
    while ((move = simulate (t, 1)) != NULL) {
        /*
         * particular move from white
         */
        t = move->target;

        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
            moveValue = move->value;
        else                    /* best next move */
            moveValue = max_alpha_beta (depth - 1, alpha, beta);

        undo ();
        free (move);
        t++;

        if (moveValue <= alpha)
            return alpha;

        if (moveValue < beta)
            beta = moveValue;
    }

    return beta;
}

/**
 * returns true when no more fields are empty
 */
int game_over ()
{
    int i;

    for (i = 0; i < BOARD_SIZE; i++) {
        if (board[i] == EMPTY)
            return 0;
    }

    return 1;
}

int main (int argc, char **argv)
{
    Node *actual;

    int i, t, value;

    int depth;

    if (argc == 2)
        depth = atoi (argv[1]);
    else
        depth = 1;

    if ((actual = malloc (sizeof (Node))) == NULL) {
        perror ("MALLOC");
        return EXIT_FAILURE;
    }

    actual->data = NULL;
    actual->prev = NULL;

    stack_end = actual;

    printf ("\tTic Tac Toe\n");

    for (i = 0; i < 5; i++) {
        printf ("Enter a number: ");
        while (scanf ("%d", &t) < 1) {
            printf ("Enter a number: ");
            t = getchar ();
        }

        if (!validMove (--t)) {
            i--;
            continue;
        }

        board[t] = 'X';

        bestMove = NULL;
        value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);

        if (bestMove == NULL) {
            break;
        }

        board[bestMove->target] = 'O';
        free (bestMove);
        print ();

        if ((estimateFunction () * estimateFunction ()) == 2500) {
            free (actual);
            return EXIT_SUCCESS;
        }

        if (game_over ())
            break;
    }

    print ();
    free (actual);

    return EXIT_SUCCESS;
}