alpha_beta.c
author Markus Brökers <mbroeker@largo.homelinux.org>
Wed, 18 Aug 2010 18:17:51 +0200
changeset 143 88d9b8bfa7a5
parent 97 f883331a1bf2
permissions -rw-r--r--
a md5 demo is already in lsflib/tools
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;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
    free (stack_end);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    78
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    79
    stack_end = actual;
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    83
 * validMove returns true(1) when the inspected field is EMPTY
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    84
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    85
int validMove (int t)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    86
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    87
    if (board[t] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    88
        return 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    89
    return 0;
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    93
 * Returns a Score of +-50 for 3 in a Row
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    94
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    95
int estimateFunction ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    96
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    97
    if (board[0] == 'X' && board[1] == 'X' && board[2] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    98
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    99
    if (board[0] == 'O' && board[1] == 'O' && board[2] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   100
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   101
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
    if (board[3] == 'X' && board[4] == 'X' && board[5] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   104
    if (board[3] == 'O' && board[4] == 'O' && board[5] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   105
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   106
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   107
    if (board[6] == 'X' && board[7] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   108
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   109
    if (board[6] == 'O' && board[7] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   110
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   111
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   112
    if (board[0] == 'X' && board[3] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   113
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   114
    if (board[0] == 'O' && board[3] == 'O' && board[6] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   115
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   116
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   117
    if (board[1] == 'X' && board[4] == 'X' && board[7] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   118
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   119
    if (board[1] == 'O' && board[4] == 'O' && board[7] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   120
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   121
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   122
    if (board[2] == 'X' && board[5] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   123
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   124
    if (board[2] == 'O' && board[5] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   125
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   126
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   127
    if (board[0] == 'X' && board[4] == 'X' && board[8] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   128
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   129
    if (board[0] == 'O' && board[4] == 'O' && board[8] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   130
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   131
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   132
    if (board[2] == 'X' && board[4] == 'X' && board[6] == 'X')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   133
        return -50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   134
    if (board[2] == 'O' && board[4] == 'O' && board[6] == 'O')
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   135
        return 50;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   136
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   137
    return 0;
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   141
 * this function visualizes the board
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   142
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   143
void print ()
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   144
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   145
    int i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   146
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   147
    printf ("       1   2   3  \n     +---+---+---+\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
    for (i = 0; i < 3; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
        printf ("  %d  | ", i + 1);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
        printf ("%c", board[3 * i]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   151
        printf (" | ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   152
        printf ("%c", board[3 * i + 1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   153
        printf (" | ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   154
        printf ("%c", board[3 * i + 2]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   155
        printf (" | \n");
97
f883331a1bf2 alpha_beta ui: removed a redundant line
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 96
diff changeset
   156
        printf ("     +---+---+---+\n");
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   157
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   158
    if (stack_end->data != NULL)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   159
        printf ("Score: %3d\n", stack_end->data->value);
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
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
 * 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
   164
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   165
Move *simulate (int t, int player)
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
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   168
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   169
    while (t < BOARD_SIZE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   170
        if (!validMove (t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   171
            t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   172
            continue;
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
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   175
        if ((move = malloc (sizeof (Move))) == NULL) {
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   176
            perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   177
            exit (EXIT_FAILURE);
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 (player == 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
            board[t] = 'O';
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   182
        else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   183
            board[t] = 'X';
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
        move->target = t;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   186
        move->value = estimateFunction ();
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
        push (move);
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
        return move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   191
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   192
    return NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   193
}
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   196
 * AlphaBeta-Algorithm: the Maximizer
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
int max_alpha_beta (int depth, int alpha, int beta)
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
    int moveValue;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   201
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   202
    int t;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   203
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   204
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   205
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   206
    if (desired_depth == -1)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   207
        desired_depth = depth;
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
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   210
    while ((move = simulate (t, 0)) != NULL) {
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
         * particular move from black
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 = move->target;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   215
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   216
        if (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   217
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   218
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   219
            moveValue = min_alpha_beta (depth - 1, alpha, beta);
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
        print ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   222
        undo ();
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   223
        t++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   224
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   225
        if (moveValue >= beta) {
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   226
            free (move);
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   227
            return beta;
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   228
        }
0
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 > alpha) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   231
            alpha = moveValue;
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   232
            if (depth == desired_depth) {
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   233
                if (bestMove != NULL)
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   234
                    free (bestMove);
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   235
                bestMove = move;
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   236
                continue;
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   237
            }
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   238
        }
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   239
        free (move);
0
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
    return alpha;
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
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
 * AlphaBeta-Algorithm: the Minimizer
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 min_alpha_beta (int depth, int alpha, int beta)
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
    int moveValue;
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
    int t;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   253
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   254
    Move *move;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   255
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   256
    t = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   257
    while ((move = simulate (t, 1)) != NULL) {
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
         * particular move from white
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
        t = move->target;
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 (depth == 0 || (estimateFunction () * estimateFunction ()) == 2500)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   264
            moveValue = move->value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   265
        else                    /* best next move */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   266
            moveValue = max_alpha_beta (depth - 1, alpha, beta);
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
        undo ();
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   269
        free (move);
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   270
        t++;
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 <= alpha)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   273
            return alpha;
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
        if (moveValue < beta)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   276
            beta = moveValue;
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
    return beta;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   280
}
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
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   283
 * returns true when no more fields are empty
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
int game_over ()
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
    int i;
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
    for (i = 0; i < BOARD_SIZE; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   290
        if (board[i] == EMPTY)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   291
            return 0;
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
    return 1;
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   297
int main (int argc, char **argv)
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
    Node *actual;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   300
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   301
    int i, t, value;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   302
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   303
    int depth;
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
    if (argc == 2)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   306
        depth = atoi (argv[1]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   307
    else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   308
        depth = 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   309
48
b94d657a9acb Policy Inonsistency on many files
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
   310
    if ((actual = malloc (sizeof (Node))) == NULL) {
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   311
        perror ("MALLOC");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   312
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   313
    }
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
    actual->data = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   316
    actual->prev = NULL;
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
    stack_end = actual;
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
    printf ("\tTic Tac Toe\n");
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
    for (i = 0; i < 5; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   323
        printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   324
        while (scanf ("%d", &t) < 1) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   325
            printf ("Enter a number: ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   326
            t = getchar ();
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   329
        if (!validMove (--t)) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   330
            i--;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   331
            continue;
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[t] = 'X';
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
        bestMove = NULL;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   337
        value = max_alpha_beta (depth, SHRT_MIN, SHRT_MAX);
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 (bestMove == NULL) {
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
        board[bestMove->target] = 'O';
96
810acedf60d8 alpha_beta: memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 87
diff changeset
   344
        free (bestMove);
0
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
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   347
        if ((estimateFunction () * estimateFunction ()) == 2500) {
87
b2f1756c17ca [alpha_beta] Fix memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   348
            free (actual);
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   349
            return EXIT_SUCCESS;
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
        if (game_over ())
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   353
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   354
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   355
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   356
    print ();
87
b2f1756c17ca [alpha_beta] Fix memory leaks
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   357
    free (actual);
8
96d16dfe787a We use return EXIT_SUCCESS instead of return 0
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
   358
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   359
    return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   360
}