alpha_beta.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Fri, 01 May 2009 18:27:06 +0200
changeset 89 66f0244c2863
parent 87 b2f1756c17ca
child 96 810acedf60d8
permissions -rw-r--r--
nearest: more templates fun small improvements and a new template function 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
/**
77
49e0babccb23 HEADER TAGS
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 48
diff changeset
     2
 * alpha_beta.c
9
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;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
    28
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
Node *stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
char board[BOARD_SIZE] = {
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
    EMPTY, EMPTY, EMPTY,
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    37
int desired_depth = -1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    38
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
int estimateFunction ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
int max_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
int min_alpha_beta (int, int, int);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    42
void print (void);
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    45
 * push: push a move onto the stack
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    46
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    47
void push (Move * move)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    48
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    49
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    50
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
    51
    if ((actual = malloc (sizeof (Node))) == NULL) {
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
        exit (EXIT_FAILURE);
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
    actual->data = move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
    actual->prev = stack_end;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    59
    stack_end = actual;
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    63
 * undo: revert the last move on the stack
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    64
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    65
void undo ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    66
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    67
    Node *actual;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    68
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
    if (stack_end == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
        printf ("Stack underrun\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
        return;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
    board[stack_end->data->target] = EMPTY;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    75
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
    actual = stack_end->prev;
87
b2f1756c17ca [alpha_beta] Fix memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
    77
    free (stack_end->data);
0
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
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   180
        if ((move = malloc (sizeof (Move))) == NULL) {
0
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;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   206
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   207
    int t;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   208
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   209
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   210
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   211
    if (desired_depth == -1)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   212
        desired_depth = depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   213
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   214
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   215
    while ((move = simulate (t, 0)) != NULL) {
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
         * particular move from black
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
        t = move->target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   220
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   221
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   222
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   223
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   224
            moveValue = min_alpha_beta (depth - 1, alpha, beta);
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
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   227
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   228
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   229
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   230
        if (moveValue >= beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   231
            return beta;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   232
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   233
        if (moveValue > alpha) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   234
            alpha = moveValue;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   235
            if (depth == desired_depth)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   236
                bestMove = move;
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
    return alpha;
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
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
 * AlphaBeta-Algorithm: the Minimizer
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 min_alpha_beta (int depth, int alpha, int beta)
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
    int moveValue;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   249
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   250
    int t;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   251
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   252
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   253
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   254
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   255
    while ((move = simulate (t, 1)) != NULL) {
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
         * particular move from white
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   258
         */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   259
        t = move->target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   260
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   261
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   262
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   263
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   264
            moveValue = max_alpha_beta (depth - 1, alpha, beta);
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
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   267
        t++;
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
        if (moveValue <= alpha)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   270
            return alpha;
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
        if (moveValue < beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   273
            beta = moveValue;
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
    return beta;
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
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
 * returns true when no more fields are empty
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
int game_over ()
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
    int i;
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
    for (i = 0; i < BOARD_SIZE; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   287
        if (board[i] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   288
            return 0;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   291
    return 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   292
}
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
int main (int argc, char **argv)
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
    Node *actual;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   297
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   298
    int i, t, value;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   299
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   300
    int depth;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   301
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   302
    if (argc == 2)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   303
        depth = atoi (argv[1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   304
    else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   305
        depth = 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   306
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   307
    if ((actual = malloc (sizeof (Node))) == NULL) {
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   308
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   309
        return EXIT_FAILURE;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   312
    actual->data = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   313
    actual->prev = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   314
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   315
    stack_end = actual;
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
    printf ("\tTic Tac Toe\n");
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
    for (i = 0; i < 5; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   320
        printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   321
        while (scanf ("%d", &t) < 1) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   322
            printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   323
            t = getchar ();
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   326
        if (!validMove (--t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   327
            i--;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   328
            continue;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   331
        board[t] = 'X';
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
        bestMove = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   334
        value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   335
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   336
        if (bestMove == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   337
            break;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   340
        board[bestMove->target] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   341
        print ();
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
        if ((estimateFunction () * estimateFunction ()) == 2500) {
87
b2f1756c17ca [alpha_beta] Fix memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   344
            free (actual);
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
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   347
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   348
        if (game_over ())
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   349
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   350
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   351
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   352
    print ();
87
b2f1756c17ca [alpha_beta] Fix memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   353
    free (actual);
8
96d16dfe787a We use return EXIT_SUCCESS instead of return 0
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
   354
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   355
    return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   356
}