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 <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;
+}