alpha_beta.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Sat, 13 Dec 2008 17:58:13 +0100
changeset 20 5fec678f931b
parent 9 c3fecc82ade6
child 27 81a574d60c15
permissions -rw-r--r--
getpass for windows does not work committer: Markus Bröker <mbroeker@largo.homelinux.org>
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 8
diff changeset
     1
/**
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 8
diff changeset
     2
 * test/demos/alpha_beta.c
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 8
diff changeset
     3
 * Copyright (C) 2008 Markus Broeker
0
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
#include <stdio.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     7
#include <stdlib.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     8
#include <limits.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     9
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    10
#define BOARD_SIZE 9
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    11
#define EMPTY 32
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    12
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    13
struct Move {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    14
    int target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    15
    int value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    16
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
typedef struct Move Move;
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
struct Node {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
    Move *data;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
    struct Node *prev;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
typedef struct Node Node;
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
Move *bestMove;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    28
Node *stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
char board[BOARD_SIZE] = {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
    EMPTY, EMPTY, EMPTY,
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    32
    EMPTY, EMPTY, EMPTY,
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
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    35
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    36
int desired_depth = -1;
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 estimateFunction ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
int max_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
int min_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
void print (void);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    42
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    43
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    44
 * push: push a move onto the stack
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
void push (Move * move)
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
    Node *actual;
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
    if ((actual = malloc (sizeof (Node) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    51
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
        exit (EXIT_FAILURE);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    55
    actual->data = move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
    actual->prev = stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
    stack_end = actual;
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
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
 * undo: revert the last move on the stack
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
void undo ()
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
    Node *actual;
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
    if (stack_end == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
        printf ("Stack underrun\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
        return;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    73
    board[stack_end->data->target] = EMPTY;
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
    actual = stack_end->prev;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
    free (stack_end);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    78
    stack_end = actual;
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
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
 * validMove returns true(1) when the inspected field is EMPTY
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
int validMove (int t)
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
    if (board[t] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    87
        return 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    88
    return 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    89
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    90
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
 * Returns a Score of +-50 for 3 in a Row
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
int estimateFunction ()
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
    if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    97
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    98
    if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   101
    if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
    if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   106
    if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   107
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   108
    if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   111
    if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   112
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   113
    if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   116
    if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   117
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   118
    if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   121
    if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   122
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   123
    if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   126
    if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   127
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   128
    if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   131
    if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   132
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   133
    if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O')
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   136
    return 0;
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
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
 * this function visualizes the board
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
void print ()
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
    int i;
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
    printf ("       1   2   3  \n     +---+---+---+\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   147
    for (i = 0; i < 3; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
        printf ("  %d  | ", i + 1);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
        printf ("%c", board[3 * i]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
        printf (" | ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   151
        printf ("%c", board[3 * i + 1]);
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 + 2]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   154
        printf (" | \n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   155
        if (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
        } else {
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
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   160
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   161
    if (stack_end->data != NULL)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   162
        printf ("Score: %3d\n", stack_end->data->value);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   163
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   164
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
 * 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
   167
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   168
Move *simulate (int t, int player)
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 *move;
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
    while (t < BOARD_SIZE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   173
        if (!validMove (t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   174
            t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   175
            continue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   176
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   177
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   178
        if ((move = malloc (sizeof (Move) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   179
            perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   180
            exit (EXIT_FAILURE);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   182
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   183
        if (player == 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   184
            board[t] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   185
        else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   186
            board[t] = 'X';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   187
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   188
        move->target = t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   189
        move->value = estimateFunction ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   190
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   191
        push (move);
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
        return 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 NULL;
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
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
 * AlphaBeta-Algorithm: the Maximizer
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
int max_alpha_beta (int depth, int alpha, int beta)
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 moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   204
    int t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   205
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   206
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   207
    if (desired_depth == -1)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   208
        desired_depth = depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   209
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   210
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   211
    while ((move = simulate (t, 0)) != NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   212
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   213
         * particular move from black
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
        t = move->target;
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
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   218
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   219
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   220
            moveValue = min_alpha_beta (depth - 1, alpha, beta);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   221
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   222
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   223
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   224
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   225
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   226
        if (moveValue >= beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   227
            return beta;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   228
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   229
        if (moveValue > alpha) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   230
            alpha = moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   231
            if (depth == desired_depth)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   232
                bestMove = move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   233
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   234
    }
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
    return alpha;
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
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
 * AlphaBeta-Algorithm: the Minimizer
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
int min_alpha_beta (int depth, int alpha, int beta)
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 moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   245
    int t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   246
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   247
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   248
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   249
    while ((move = simulate (t, 1)) != NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   250
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   251
         * particular move from white
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
        t = move->target;
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
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   256
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   257
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   258
            moveValue = max_alpha_beta (depth - 1, alpha, beta);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   259
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   260
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   261
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   262
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   263
        if (moveValue <= alpha)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   264
            return alpha;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   265
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   266
        if (moveValue < beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   267
            beta = moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   268
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   269
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   270
    return beta;
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
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
 * returns true when no more fields are empty
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
int game_over ()
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 i;
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
    for (i = 0; i < BOARD_SIZE; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   281
        if (board[i] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   282
            return 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   283
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   284
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   285
    return 1;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   288
int main (int argc, char **argv)
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
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   291
    int i, t, value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   292
    int depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   293
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   294
    if (argc == 2)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   295
        depth = atoi (argv[1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   296
    else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   297
        depth = 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   298
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   299
    if ((actual = malloc (sizeof (Node) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   300
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   301
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   302
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   303
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   304
    actual->data = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   305
    actual->prev = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   306
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   307
    stack_end = actual;
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
    printf ("\tTic Tac Toe\n");
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
    for (i = 0; i < 5; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   312
        printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   313
        while (scanf ("%d", &t) < 1) {
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
            t = getchar ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   316
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   317
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   318
        if (!validMove (--t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   319
            i--;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   320
            continue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   321
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   322
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   323
        board[t] = 'X';
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
        bestMove = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   326
        value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   327
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   328
        if (bestMove == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   329
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   330
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   331
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   332
        board[bestMove->target] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   333
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   334
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   335
        if ((estimateFunction () * estimateFunction ()) == 2500) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   336
            return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   337
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   338
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   339
        if (game_over ())
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   340
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   341
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   342
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   343
    print ();
8
96d16dfe787a We use return EXIT_SUCCESS instead of return 0
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
   344
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   345
    return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   346
}