alpha_beta.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Sat, 13 Dec 2008 17:57:59 +0100
changeset 7 a1aa30f0f904
parent 0 af501b0c1716
child 8 96d16dfe787a
permissions -rw-r--r--
libtest demonstrates how to use shared libraries committer: Markus Bröker <mbroeker@largo.homelinux.org>
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     1
/*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     2
 *     $Id: alpha_beta.c,v 1.5 2008-05-08 21:04:08 mbroeker Exp $
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     3
 * $Source: /development/c/demos/alpha_beta.c,v $
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     4
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     5
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     6
/* TIC TAC TOE With Alpha Beta Search */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     7
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     8
#include <stdio.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     9
#include <stdlib.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    10
#include <limits.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    11
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    12
#define BOARD_SIZE 9
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    13
#define EMPTY 32
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    14
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    15
struct Move {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    16
    int target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
    int value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    19
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    20
typedef struct Move Move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
struct Node {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
    Move *data;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
    struct Node *prev;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    26
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    27
typedef struct Node Node;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    28
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
Move *bestMove;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
Node *stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    32
char board[BOARD_SIZE] = {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    33
    EMPTY, EMPTY, EMPTY,
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    34
    EMPTY, EMPTY, EMPTY,
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    35
    EMPTY, EMPTY, EMPTY,
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    36
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    37
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    38
int desired_depth = -1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
int estimateFunction ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
int max_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    42
int min_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    43
void print (void);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    44
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    45
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    46
 * push: push a move onto the stack
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    47
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    48
void push (Move * move)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    49
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    50
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    51
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
    if ((actual = malloc (sizeof (Node) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
        exit (EXIT_FAILURE);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    55
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
    actual->data = move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
    actual->prev = stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    59
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    60
    stack_end = actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    61
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    62
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    63
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    64
 * undo: revert the last move on the stack
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    65
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    66
void undo ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    67
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    68
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
    if (stack_end == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
        printf ("Stack underrun\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
        return;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    73
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    75
    board[stack_end->data->target] = EMPTY;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
    actual = stack_end->prev;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    78
    free (stack_end);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    79
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    80
    stack_end = actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    81
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    82
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    83
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    84
 * validMove returns true(1) when the inspected field is EMPTY
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    85
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    86
int validMove (int t)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    87
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    88
    if (board[t] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    89
        return 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    90
    return 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    91
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    92
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    93
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    94
 * Returns a Score of +-50 for 3 in a Row
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    95
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    96
int estimateFunction ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    97
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    98
    if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    99
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   100
    if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   101
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
    if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   104
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   105
    if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   106
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   107
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   108
    if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   109
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   110
    if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   111
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   112
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   113
    if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   114
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   115
    if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   116
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   117
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   118
    if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   119
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   120
    if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   121
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   122
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   123
    if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   124
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   125
    if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   126
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   127
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   128
    if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   129
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   130
    if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   131
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   132
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   133
    if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   134
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   135
    if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   136
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   137
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   138
    return 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   139
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   140
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   141
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   142
 * this function visualizes the board
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   143
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   144
void print ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   145
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   146
    int i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   147
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
    printf ("       1   2   3  \n     +---+---+---+\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
    for (i = 0; i < 3; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
        printf ("  %d  | ", i + 1);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   151
        printf ("%c", board[3 * i]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   152
        printf (" | ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   153
        printf ("%c", board[3 * i + 1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   154
        printf (" | ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   155
        printf ("%c", board[3 * i + 2]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   156
        printf (" | \n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   157
        if (i != 2) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   158
            printf ("     +---+---+---+\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   159
        } else {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   160
            printf ("     +---+---+---+\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   161
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   162
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   163
    if (stack_end->data != NULL)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   164
        printf ("Score: %3d\n", stack_end->data->value);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   165
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   166
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   167
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   168
 * simulates and returns the next possible move for a Player or null, when no more moves are possible.
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   169
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   170
Move *simulate (int t, int player)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   171
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   172
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   173
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   174
    while (t < BOARD_SIZE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   175
        if (!validMove (t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   176
            t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   177
            continue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   178
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   179
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   180
        if ((move = malloc (sizeof (Move) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
            perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   182
            exit (EXIT_FAILURE);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   183
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   184
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   185
        if (player == 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   186
            board[t] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   187
        else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   188
            board[t] = 'X';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   189
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   190
        move->target = t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   191
        move->value = estimateFunction ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   192
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   193
        push (move);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   194
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   195
        return move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   196
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   197
    return NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   198
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   199
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   200
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   201
 * AlphaBeta-Algorithm: the Maximizer
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   202
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   203
int max_alpha_beta (int depth, int alpha, int beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   204
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   205
    int moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   206
    int t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   207
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   208
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   209
    if (desired_depth == -1)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   210
        desired_depth = depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   211
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   212
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   213
    while ((move = simulate (t, 0)) != NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   214
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   215
         * particular move from black
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   216
         */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   217
        t = move->target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   218
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   219
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   220
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   221
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   222
            moveValue = min_alpha_beta (depth - 1, alpha, beta);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   223
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   224
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   225
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   226
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   227
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   228
        if (moveValue >= beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   229
            return beta;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   230
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   231
        if (moveValue > alpha) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   232
            alpha = moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   233
            if (depth == desired_depth)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   234
                bestMove = move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   235
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   236
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   237
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   238
    return alpha;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   239
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   240
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   241
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   242
 * AlphaBeta-Algorithm: the Minimizer
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   243
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   244
int min_alpha_beta (int depth, int alpha, int beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   245
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   246
    int moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   247
    int t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   248
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   249
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   250
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   251
    while ((move = simulate (t, 1)) != NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   252
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   253
         * particular move from white
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   254
         */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   255
        t = move->target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   256
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   257
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   258
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   259
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   260
            moveValue = max_alpha_beta (depth - 1, alpha, beta);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   261
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   262
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   263
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   264
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   265
        if (moveValue <= alpha)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   266
            return alpha;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   267
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   268
        if (moveValue < beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   269
            beta = moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   270
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   271
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   272
    return beta;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   273
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   274
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   275
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   276
 * returns true when no more fields are empty
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   277
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   278
int game_over ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   279
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   280
    int i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   281
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   282
    for (i = 0; i < BOARD_SIZE; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   283
        if (board[i] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   284
            return 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   285
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   286
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   287
    return 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   288
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   289
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   290
int main (int argc, char **argv)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   291
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   292
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   293
    int i, t, value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   294
    int depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   295
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   296
    if (argc == 2)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   297
        depth = atoi (argv[1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   298
    else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   299
        depth = 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   300
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   301
    if ((actual = malloc (sizeof (Node) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   302
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   303
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   304
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   305
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   306
    actual->data = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   307
    actual->prev = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   308
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   309
    stack_end = actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   310
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   311
    printf ("\tTic Tac Toe\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   312
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   313
    for (i = 0; i < 5; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   314
        printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   315
        while (scanf ("%d", &t) < 1) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   316
            printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   317
            t = getchar ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   318
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   319
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   320
        if (!validMove (--t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   321
            i--;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   322
            continue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   323
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   324
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   325
        board[t] = 'X';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   326
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   327
        bestMove = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   328
        value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   329
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   330
        if (bestMove == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   331
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   332
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   333
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   334
        board[bestMove->target] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   335
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   336
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   337
        if ((estimateFunction () * estimateFunction ()) == 2500) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   338
            return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   339
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   340
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   341
        if (game_over ())
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   342
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   343
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   344
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   345
    print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   346
    return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   347
}