树形结构在人机对弈中的应用c语言

树形结构在人机对弈中的应用可以用来构建博弈树，以便对游戏进行搜索和决策。以下是一个简单的使用树形结构的C语言示例，用于实现人机对弈的井字棋游戏：

#include <stdio.h>
#include <stdlib.h>

#define BOARD_SIZE 3

enum Player { HUMAN, COMPUTER };

typedef struct Node {
    char board[BOARD_SIZE][BOARD_SIZE];
    enum Player player;
    int score;
    struct Node *children[BOARD_SIZE * BOARD_SIZE];
} Node;

void init_board(char board[BOARD_SIZE][BOARD_SIZE]) {
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            board[i][j] = ' ';
        }
    }
}

void print_board(char board[BOARD_SIZE][BOARD_SIZE]) {
    printf("  ");
    for (int i = 0; i < BOARD_SIZE; i++) {
        printf("%d ", i + 1);
    }
    printf("\n");
    for (int i = 0; i < BOARD_SIZE; i++) {
        printf("%d ", i + 1);
        for (int j = 0; j < BOARD_SIZE; j++) {
            printf("%c|", board[i][j]);
        }
        printf("\n");
        if (i != BOARD_SIZE - 1) {
            printf("  -+-+-\n");
        }
    }
}

int is_full(char board[BOARD_SIZE][BOARD_SIZE]) {
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (board[i][j] == ' ') {
                return 0;
            }
        }
    }
    return 1;
}

int is_winner(char board[BOARD_SIZE][BOARD_SIZE], char player) {
    for (int i = 0; i < BOARD_SIZE; i++) {
        // check rows
        if (board[i][0] == player && board[i][1] == player && board[i][2] == player) {
            return 1;
        }
        // check columns
        if (board[0][i] == player && board[1][i] == player && board[2][i] == player) {
            return 1;
        }
    }
    // check diagonals
    if (board[0][0] == player && board[1][1] == player && board[2][2] == player) {
        return 1;
    }
    if (board[0][2] == player && board[1][1] == player && board[2][0] == player) {
        return 1;
    }
    return 0;
}

int evaluate_board(char board[BOARD_SIZE][BOARD_SIZE]) {
    if (is_winner(board, 'O')) {
        return 1;
    } else if (is_winner(board, 'X')) {
        return -1;
    } else {
        return 0;
    }
}

void copy_board(char dest[BOARD_SIZE][BOARD_SIZE], char src[BOARD_SIZE][BOARD_SIZE]) {
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            dest[i][j] = src[i][j];
        }
    }
}

Node *create_node(char board[BOARD_SIZE][BOARD_SIZE], enum Player player) {
    Node *node = malloc(sizeof(Node));
    copy_board(node->board, board);
    node->player = player;
    node->score = evaluate_board(board);
    for (int i = 0; i < BOARD_SIZE * BOARD_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

void destroy_node(Node *node) {
    for (int i = 0; i < BOARD_SIZE * BOARD_SIZE; i++) {
        if (node->children[i] != NULL) {
            destroy_node(node->children[i]);
        }
    }
    free(node);
}

void create_children(Node *node) {
    if (node->score != 0) {
        return;
    }
    char player_char = (node->player == HUMAN) ? 'X' : 'O';
    int child_count = 0;
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            if (node->board[i][j] == ' ') {
                Node *child = create_node(node->board, (node->player == HUMAN) ? COMPUTER : HUMAN);
                child->board[i][j] = player_char;
                node->children[child_count] = child;
                child_count++;
            }
        }
    }
}

void print_score(int score) {
    if (score == 1) {
        printf("O wins!\n");
    } else if (score == -1) {
        printf("X wins!\n");
    } else {
        printf("Tie game.\n");
    }
}

Node *find_best_move(Node *node) {
    if (node->score != 0) {
        return node;
    }
    int best_score = (node->player == HUMAN) ? 1 : -1;
    Node *best_child = NULL;
    for (int i = 0; i < BOARD_SIZE * BOARD_SIZE; i++) {
        if (node->children[i] != NULL) {
            Node *child = node->children[i];
            Node *best_child_of_child = find_best_move(child);
            if (best_child_of_child != NULL) {
                int child_score = best_child_of_child->score;
                if ((node->player == HUMAN && child_score < best_score) ||
                    (node->player == COMPUTER && child_score > best_score)) {
                    best_score = child_score;
                    best_child = child;
                }
            }
        }
    }
    if (best_child != NULL) {
        node->score = best_score;
        return best_child;
    } else {
        return NULL;
    }
}

int main() {
    char board[BOARD_SIZE][BOARD_SIZE];
    init_board(board);
    enum Player current_player = HUMAN;
    while (!is_full(board) && !is_winner(board, 'X') && !is_winner(board, 'O')) {
        print_board(board);
        if (current_player == HUMAN) {
            int row, col;
            printf("Enter row (1-%d): ", BOARD_SIZE);
            scanf("%d", &row);
            printf("Enter column (1-%d): ", BOARD_SIZE);
            scanf("%d", &col);
            if (board[row - 1][col - 1] != ' ') {
                printf("That space is already taken. Try again.\n");
            } else {
                board[row - 1][col - 1] = 'X';
                current_player = COMPUTER;
            }
        } else {
            Node *root = create_node(board, COMPUTER);
            create_children(root);
            Node *best_move = find_best_move(root);
            if (best_move != NULL) {
                copy_board(board, best_move->board);
                current_player = HUMAN;
            }
            destroy_node(root);
        }
    }
    print_board(board);
    print_score(evaluate_board(board));
    return 0;
}

该示例实现了一个简单的井字棋游戏，在游戏中，玩家可以通过输入行和列来下棋，计算机则会通过构建博弈树来选择最佳的下棋位置。该示例使用树形结构来表示博弈树，并使用递归算法来搜索树以找到最佳的下棋位置。