/*

 *     $Id: alpha_beta.c,v 1.5 2008-05-08 21:04:08 mbroeker Exp $

 * $Source: /development/c/demos/alpha_beta.c,v $

 */

/* TIC TAC TOE With Alpha Beta Search */

#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) + 1)) == 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");

        if (i != 2) {

            printf ("     +---+---+---+\n");

        } else {

            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) + 1)) == 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)

            return beta;

        if (moveValue > alpha) {

            alpha = moveValue;

            if (depth == desired_depth)

                bestMove = 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 ();

        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) + 1)) == 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';

        print ();

        if ((estimateFunction () * estimateFunction ()) == 2500) {

            return EXIT_SUCCESS;

        }

        if (game_over ())

            break;

    }

    print ();

    return EXIT_SUCCESS;

}