C++构造六子棋博弈树‘’

首先，我们需要定义一个棋盘类，来保存棋盘上的棋子位置和状态：

class Board {
public:
    static const int size = 6; // 棋盘大小
    static const int empty = 0; // 空位
    static const int black = 1; // 黑棋
    static const int white = 2; // 白棋

    int board[size][size]; // 棋盘

    Board() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                board[i][j] = empty; // 初始化为空位
            }
        }
    }

    bool is_legal(int x, int y) const {
        return x >= 0 && x < size && y >= 0 && y < size && board[x][y] == empty; // 判断该位置是否合法
    }

    void put(int x, int y, int color) {
        board[x][y] = color; // 在该位置放置指定颜色的棋子
    }

    void remove(int x, int y) {
        board[x][y] = empty; // 将该位置移除棋子
    }

    bool is_win(int color) const {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i][j] == color) {
                    // 检查横向连续棋子
                    if (j + 5 < size && board[i][j + 1] == color && board[i][j + 2] == color && board[i][j + 3] == color && board[i][j + 4] == color && board[i][j + 5] == color) {
                        return true;
                    }
                    // 检查纵向连续棋子
                    if (i + 5 < size && board[i + 1][j] == color && board[i + 2][j] == color && board[i + 3][j] == color && board[i + 4][j] == color && board[i + 5][j] == color) {
                        return true;
                    }
                    // 检查左上到右下的斜线连续棋子
                    if (i + 5 < size && j + 5 < size && board[i + 1][j + 1] == color && board[i + 2][j + 2] == color && board[i + 3][j + 3] == color && board[i + 4][j + 4] == color && board[i + 5][j + 5] == color) {
                        return true;
                    }
                    // 检查右上到左下的斜线连续棋子
                    if (i + 5 < size && j - 5 >= 0 && board[i + 1][j - 1] == color && board[i + 2][j - 2] == color && board[i + 3][j - 3] == color && board[i + 4][j - 4] == color && board[i + 5][j - 5] == color) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool is_full() const {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (board[i][j] == empty) {
                    return false; // 棋盘还有空位
                }
            }
        }
        return true; // 棋盘已满
    }
};

接下来，我们需要定义一个博弈树节点类，来保存当前棋盘状态和可能的下一步走法：

class Node {
public:
    Board board; // 当前棋盘状态
    vector<Node*> children; // 可能的下一步走法

    Node(const Board& board) : board(board) {}

    ~Node() {
        for (auto child : children) {
            delete child; // 递归删除所有子节点
        }
    }

    void expand(int color) {
        for (int i = 0; i < Board::size; i++) {
            for (int j = 0; j < Board::size; j++) {
                if (board.is_legal(i, j)) {
                    Board new_board = board;
                    new_board.put(i, j, color); // 尝试在该位置放置指定颜色的棋子
                    Node* child = new Node(new_board);
                    children.push_back(child); // 添加新的子节点
                }
            }
        }
    }

    bool is_leaf() const {
        return children.empty(); // 没有子节点即为叶子节点
    }
};

最后，我们需要定义一个博弈树类，来构造和搜索博弈树：

class GameTree {
public:
    Node* root; // 根节点

    GameTree(const Board& board) {
        root = new Node(board);
    }

    ~GameTree() {
        delete root;
    }

    void build(int depth, int color) {
        if (depth == 0 || root->board.is_full() || root->board.is_win(Board::black) || root->board.is_win(Board::white)) {
            return; // 达到指定深度或者结束游戏，停止构造博弈树
        }
        root->expand(color); // 扩展当前节点的子节点
        for (auto child : root->children) {
            build(depth - 1, color == Board::black ? Board::white : Board::black); // 递归构造子节点的博弈树
        }
    }

    int evaluate(const Board& board) const {
        // 简单的评估函数，统计棋盘上每个连续的棋子数量
        int score = 0;
        for (int i = 0; i < Board::size; i++) {
            for (int j = 0; j < Board::size; j++) {
                if (board.board[i][j] == Board::black) {
                    // 统计横向连续棋子
                    if (j + 5 < Board::size && board.board[i][j + 1] == Board::black && board.board[i][j + 2] == Board::black && board.board[i][j + 3] == Board::black && board.board[i][j + 4] == Board::black && board.board[i][j + 5] == Board::black) {
                        score += 10000;
                    } else if (j + 4 < Board::size && board.board[i][j + 1] == Board::black && board.board[i][j + 2] == Board::black && board.board[i][j + 3] == Board::black && board.board[i][j + 4] == Board::black) {
                        score += 1000;
                    } else if (j + 3 < Board::size && board.board[i][j + 1] == Board::black && board.board[i][j + 2] == Board::black && board.board[i][j + 3] == Board::black) {
                        score += 100;
                    } else if (j + 2 < Board::size && board.board[i][j + 1] == Board::black && board.board[i][j + 2] == Board::black) {
                        score += 10;
                    } else if (j + 1 < Board::size && board.board[i][j + 1] == Board::black) {
                        score += 1;
                    }
                    // 统计纵向连续棋子
                    if (i + 5 < Board::size && board.board[i + 1][j] == Board::black && board.board[i + 2][j] == Board::black && board.board[i + 3][j] == Board::black && board.board[i + 4][j] == Board::black && board.board[i + 5][j] == Board::black) {
                        score += 10000;
                    } else if (i + 4 < Board::size && board.board[i + 1][j] == Board::black && board.board[i + 2][j] == Board::black && board.board[i + 3][j] == Board::black && board.board[i + 4][j] == Board::black) {
                        score += 1000;
                    } else if (i + 3 < Board::size && board.board[i + 1][j] == Board::black && board.board[i + 2][j] == Board::black && board.board[i + 3][j] == Board::black) {
                        score += 100;
                    } else if (i + 2 < Board::size && board.board[i + 1][j] == Board::black && board.board[i + 2][j] == Board::black) {
                        score += 10;
                    } else if (i + 1 < Board::size && board.board[i + 1][j] == Board::black) {
                        score += 1;
                    }
                    // 统计左上到右下的斜线连续棋子
                    if (i + 5 < Board::size && j + 5 < Board::size && board.board[i + 1][j + 1] == Board::black && board.board[i + 2][j + 2] == Board::black && board.board[i + 3][j + 3] == Board::black && board.board[i + 4][j + 4] == Board::black && board.board[i + 5][j + 5] == Board::black) {
                        score += 10000;
                    } else if (i + 4 < Board::size && j + 4 < Board::size && board.board[i + 1][j + 1] == Board::black && board.board[i + 2][j + 2] == Board::black && board.board[i + 3][j + 3] == Board::black && board.board[i + 4][j + 4] == Board::black) {
                        score += 1000;
                    } else if (i + 3 < Board::size && j + 3 < Board::size && board.board[i + 1][j + 1] == Board::black && board.board[i + 2][j + 2] == Board::black && board.board[i + 3][j + 3] == Board::black) {
                        score += 100;
                    } else if (i + 2 < Board::size && j + 2 < Board::size && board.board[i + 1][j + 1] == Board::black && board.board[i + 2][j + 2] == Board::black) {
                        score += 10;
                    } else if (i + 1 < Board::size && j + 1 < Board::size && board.board[i + 1][j + 1] == Board::black) {
                        score += 1;
                    }
                    // 统计右上到左下的斜线连续棋子
                    if (i + 5 < Board::size && j - 5 >= 0 && board.board[i + 1][j - 1] == Board::black && board.board[i + 2][j - 2] == Board::black && board.board[i + 3][j - 3] == Board::black && board.board[i + 4][j - 4] == Board::black && board.board[i + 5][j - 5] == Board::black) {
                        score += 10000;
                    } else if (i + 4 < Board::size && j - 4 >= 0 && board.board[i + 1][j - 1] == Board::black && board.board[i + 2][j - 2] == Board::black && board.board[i + 3][j - 3] == Board::black && board.board[i + 4][j - 4] == Board::black) {
                        score += 1000;
                    } else if (i + 3 < Board::size && j - 3 >= 0 && board.board[i + 1][j - 1] == Board::black && board.board[i + 2][j - 2] == Board::black && board.board[i + 3][j - 3] == Board::black) {
                        score += 100;
                    } else if (i + 2 < Board::size && j - 2 >= 0 && board.board[i + 1][j - 1] == Board::black && board.board[i + 2][j - 2] == Board::black) {
                        score += 10;
                    } else if (i + 1 < Board::size && j - 1 >= 0 && board.board[i + 1][j - 1] == Board::black) {
                        score += 1;
                    }
                } else if (board.board[i][j] == Board::white) {
                    // 同理，统计白棋连续棋子
                    // ...
                }
            }
        }
        return score;
    }

    int minimax(Node* node, int depth, int alpha, int beta, int color) {
        if (depth == 0 || node->is_leaf()) {
            return evaluate(node->board); // 叶子节点执行评估函数
        }
        if (color == Board::black) { // 黑棋节点取最大值
            int value = INT_MIN;
            for (auto child : node->children) {
                value = max(value, minimax(child, depth - 1, alpha, beta, Board::white));
                alpha = max(alpha, value);
                if (beta <= alpha) {
                    break; // alpha-beta剪枝
                }
            }
            return value;
        } else { // 白棋节点取最小值
            int value = INT_MAX;
            for (auto child : node->children) {
                value = min(value, minimax(child, depth - 1, alpha, beta, Board::black));
                beta = min(beta, value);
                if (beta <= alpha) {
                    break; // alpha-beta剪枝
                }
            }
            return value;
        }
    }

    pair<int, int> search(int depth, int color) {
        int max_score = INT_MIN;
        pair<int, int> best_move(-1, -1);
        for (auto child : root->children) {
            int score = minimax(child, depth - 1, INT_MIN, INT_MAX, color == Board::black ? Board::white : Board::black);
            if (score > max_score) {
                max_score = score;
                for (int i = 0; i < Board::size; i++) {
                    for (int j = 0; j < Board::size; j++) {
                        if (child->board.board[i][j] != root->board.board[i][j]) {
                            best_move.first = i;
                            best_move.second = j;
                            break;
                        }
                    }
                }
            }
        }
        return best_move;
    }
};

使用时，我们可以先构造一个初始棋盘，然后构造博弈树，并搜索出最优的下一步走法：

int main() {
    Board board;
    board.put(2, 2, Board::black);
    board.put(3, 3, Board::black);
    board.put(4, 4, Board::black);
    board.put(2, 3, Board::white);
    board.put(3, 4, Board::white);
    board.put(4, 5, Board::white);
    GameTree tree(board);
    tree.build(3, Board::white);
    pair<int, int> best_move = tree.search(3, Board::white);
    cout << "Best move: (" << best_move.first << ", " << best_move.second << ")" << endl;
    return 0;
}