1 /*

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

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

     4  */

     5 

     6 /* TIC TAC TOE With Alpha Beta Search */

     7 

     8 #include <stdio.h>

     9 #include <stdlib.h>

    10 #include <limits.h>

    11 

    12 #define BOARD_SIZE 9

    13 #define EMPTY 32

    14 

    15 struct Move {

    16     int target;

    17     int value;

    18 };

    19 

    20 typedef struct Move Move;

    21 

    22 struct Node {

    23     Move *data;

    24     struct Node *prev;

    25 };

    26 

    27 typedef struct Node Node;

    28 

    29 Move *bestMove;

    30 Node *stack_end;

    31 

    32 char board[BOARD_SIZE] = {

    33     EMPTY, EMPTY, EMPTY,

    34     EMPTY, EMPTY, EMPTY,

    35     EMPTY, EMPTY, EMPTY,

    36 };

    37 

    38 int desired_depth = -1;

    39 

    40 int estimateFunction ();

    41 int max_alpha_beta (int, int, int);

    42 int min_alpha_beta (int, int, int);

    43 void print (void);

    44 

    45 /**

    46  * push: push a move onto the stack

    47  */

    48 void push (Move * move)

    49 {

    50     Node *actual;

    51 

    52     if ((actual = malloc (sizeof (Node) + 1)) == NULL) {

    53         perror ("MALLOC");

    54         exit (EXIT_FAILURE);

    55     }

    56 

    57     actual->data = move;

    58     actual->prev = stack_end;

    59 

    60     stack_end = actual;

    61 }

    62 

    63 /**

    64  * undo: revert the last move on the stack

    65  */

    66 void undo ()

    67 {

    68     Node *actual;

    69 

    70     if (stack_end == NULL) {

    71         printf ("Stack underrun\n");

    72         return;

    73     }

    74 

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

    76 

    77     actual = stack_end->prev;

    78     free (stack_end);

    79 

    80     stack_end = actual;

    81 }

    82 

    83 /**

    84  * validMove returns true(1) when the inspected field is EMPTY

    85  */

    86 int validMove (int t)

    87 {

    88     if (board[t] == EMPTY)

    89         return 1;

    90     return 0;

    91 }

    92 

    93 /**

    94  * Returns a Score of +-50 for 3 in a Row

    95  */

    96 int estimateFunction ()

    97 {

    98     if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X')

    99         return -50;

   100     if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O')

   101         return 50;

   102 

   103     if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X')

   104         return -50;

   105     if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O')

   106         return 50;

   107 

   108     if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X')

   109         return -50;

   110     if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O')

   111         return 50;

   112 

   113     if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X')

   114         return -50;

   115     if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O')

   116         return 50;

   117 

   118     if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X')

   119         return -50;

   120     if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O')

   121         return 50;

   122 

   123     if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X')

   124         return -50;

   125     if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O')

   126         return 50;

   127 

   128     if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X')

   129         return -50;

   130     if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O')

   131         return 50;

   132 

   133     if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X')

   134         return -50;

   135     if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O')

   136         return 50;

   137 

   138     return 0;

   139 }

   140 

   141 /**

   142  * this function visualizes the board

   143  */

   144 void print ()

   145 {

   146     int i;

   147 

   148     printf ("       1   2   3  \n     +---+---+---+\n");

   149     for (i = 0; i < 3; i++) {

   150         printf ("  %d  | ", i + 1);

   151         printf ("%c", board[3 * i]);

   152         printf (" | ");

   153         printf ("%c", board[3 * i + 1]);

   154         printf (" | ");

   155         printf ("%c", board[3 * i + 2]);

   156         printf (" | \n");

   157         if (i != 2) {

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

   159         } else {

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

   161         }

   162     }

   163     if (stack_end->data != NULL)

   164         printf ("Score: %3d\n", stack_end->data->value);

   165 }

   166 

   167 /**

   168  * simulates and returns the next possible move for a Player or null, when no more moves are possible.

   169  */

   170 Move *simulate (int t, int player)

   171 {

   172     Move *move;

   173 

   174     while (t < BOARD_SIZE) {

   175         if (!validMove (t)) {

   176             t++;

   177             continue;

   178         }

   179 

   180         if ((move = malloc (sizeof (Move) + 1)) == NULL) {

   181             perror ("MALLOC");

   182             exit (EXIT_FAILURE);

   183         }

   184 

   185         if (player == 0)

   186             board[t] = 'O';

   187         else

   188             board[t] = 'X';

   189 

   190         move->target = t;

   191         move->value = estimateFunction ();

   192 

   193         push (move);

   194 

   195         return move;

   196     }

   197     return NULL;

   198 }

   199 

   200 /**

   201  * AlphaBeta-Algorithm: the Maximizer

   202  */

   203 int max_alpha_beta (int depth, int alpha, int beta)

   204 {

   205     int moveValue;

   206     int t;

   207     Move *move;

   208 

   209     if (desired_depth == -1)

   210         desired_depth = depth;

   211 

   212     t = 0;

   213     while ((move = simulate (t, 0)) != NULL) {

   214         /*

   215          * particular move from black

   216          */

   217         t = move->target;

   218 

   219         if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)

   220             moveValue = move->value;

   221         else                    /* best next move */

   222             moveValue = min_alpha_beta (depth - 1, alpha, beta);

   223 

   224         print ();

   225         undo ();

   226         t++;

   227 

   228         if (moveValue >= beta)

   229             return beta;

   230 

   231         if (moveValue > alpha) {

   232             alpha = moveValue;

   233             if (depth == desired_depth)

   234                 bestMove = move;

   235         }

   236     }

   237 

   238     return alpha;

   239 }

   240 

   241 /**

   242  * AlphaBeta-Algorithm: the Minimizer

   243  */

   244 int min_alpha_beta (int depth, int alpha, int beta)

   245 {

   246     int moveValue;

   247     int t;

   248     Move *move;

   249 

   250     t = 0;

   251     while ((move = simulate (t, 1)) != NULL) {

   252         /*

   253          * particular move from white

   254          */

   255         t = move->target;

   256 

   257         if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)

   258             moveValue = move->value;

   259         else                    /* best next move */

   260             moveValue = max_alpha_beta (depth - 1, alpha, beta);

   261 

   262         undo ();

   263         t++;

   264 

   265         if (moveValue <= alpha)

   266             return alpha;

   267 

   268         if (moveValue < beta)

   269             beta = moveValue;

   270     }

   271 

   272     return beta;

   273 }

   274 

   275 /**

   276  * returns true when no more fields are empty

   277  */

   278 int game_over ()

   279 {

   280     int i;

   281 

   282     for (i = 0; i < BOARD_SIZE; i++) {

   283         if (board[i] == EMPTY)

   284             return 0;

   285     }

   286 

   287     return 1;

   288 }

   289 

   290 int main (int argc, char **argv)

   291 {

   292     Node *actual;

   293     int i, t, value;

   294     int depth;

   295 

   296     if (argc == 2)

   297         depth = atoi (argv[1]);

   298     else

   299         depth = 1;

   300 

   301     if ((actual = malloc (sizeof (Node) + 1)) == NULL) {

   302         perror ("MALLOC");

   303         return EXIT_FAILURE;

   304     }

   305 

   306     actual->data = NULL;

   307     actual->prev = NULL;

   308 

   309     stack_end = actual;

   310 

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

   312 

   313     for (i = 0; i < 5; i++) {

   314         printf ("Enter a number: ");

   315         while (scanf ("%d", &t) < 1) {

   316             printf ("Enter a number: ");

   317             t = getchar ();

   318         }

   319 

   320         if (!validMove (--t)) {

   321             i--;

   322             continue;

   323         }

   324 

   325         board[t] = 'X';

   326 

   327         bestMove = NULL;

   328         value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);

   329 

   330         if (bestMove == NULL) {

   331             break;

   332         }

   333 

   334         board[bestMove->target] = 'O';

   335         print ();

   336 

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

   338             return EXIT_SUCCESS;

   339         }

   340 

   341         if (game_over ())

   342             break;

   343     }

   344 

   345     print ();

   346     return EXIT_SUCCESS;

   347 }