diff --git a/alpha_beta.c b/alpha_beta.c new file mode 100644 --- /dev/null +++ b/alpha_beta.c @@ -0,0 +1,347 @@ +/* + * $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 +#include +#include + +#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; +}