3. 博弈树 (15分)

下棋属于一种博弈游戏，博弈过程可以用树（博弈树）来表示。假设游戏由两个人（ A 和 B ）玩，开始由某个人从根结点开始走，两个人轮流走棋，每次只能走一步， 下一步棋只能选择当前结点的孩子结点，谁先走到叶子结点为胜。例如，对于下图所示的博弈树，若 A 先走，可以选 f ， B 若选 h ，则 A 选 j 胜。

编写一程序，让计算机和人下棋。当计算机走下一步时，可以根据以下情况决定下一步：

（1） 若存在可以确保取胜的一个孩子结点，则选择该结点作为下一步；

（2） 若存在多个可以确保取胜的孩子结点，则选择其中高度最小的结点作为下一步（若有多个选择，则选最左边的结点）；

（3） 若不存在可以确保取胜的一个孩子结点，则选择高度最大的孩子结点作为下一步（若有多个选择，则选最左边的结点）；

例： （下面的黑体为输入）

(a,(b,(x)),(c,(d),(e,(g),(h)),(f)))

a

b

x

c

d

e

g

h

f

Who play first(0: computer; 1: player )?

1

player:

c

computer: d

Sorry, you lost.

Continue(y/n)?

y

Who play first(0: computer; 1: player )?

1

player:

x

illegal move.

player:

b

computer: x

Sorry, you lost.

Continue(y/n)?

y

Who play first(0: computer; 1: player )?

0

computer: c

player:

f

Congratulate, you win.

Continue(y/n)?

n

博弈树学习笔记：

完全博弈问题--下棋

特点：

    双人对弈: 轮流下,一人走一步.

    信息完备: 双方看到的信息一样.

    零和: 双方利益冲突,对一方有利则对另一方不利。

极小极大搜索方法: (假定对手每次回应都正确,即选择MIN)

    假定有一个评价函数可以对所有的棋局进行评估.

    评价函数值大于0,棋局对我方有利,对对方不利,反之同理.

    对节点N取估价函数f(N),分两类节点:

        Max,有选择时取最大;

        Min,有选择时取最小.

具体思路:

    1.我方走棋时,首先按照一定的搜索深度生成出给定深度d以内的所有状态,计算所有叶节点的评价函数值, 然后从d-1层节点开始逆向计算.

    2.对于我方要走的节点(MAX),取其子节点中的最大值为该节点的值（选择对我方有利的棋）。

    3.对于对方要走的节点(MIN),取其子节点中的最小值为该节点的值（选择对我方不利的棋）。

    4.直到计算出根节点的值为止,获得根节点取值的分枝即为最佳选择.

    5.对方回应一步棋后,重新演算.

显然这样做太低效了,需要剪枝，分析：

α-β搜索方法定义:(其实就是给节点定义范围区间--[α,β],初始化为+-∞)

    Max节点的下界为α,Min节点的上界为β.

    极大节点N,从一个子树获得的α值和β值,可以传送给其他子节点

    极大节点N的α值只可能越改越大,极小节点M的β值只可能越改越小.

    从单边子节点往父节点推,极大值父节点只更改α值，极小值父节点只更改β值.

α剪枝(发生在极小层节点)---从一个子树获得的极大节点的α值，可以传送给该节点的其他子树，从而选择α剪枝机会

    若对任一极小值层节点,α(任意父辈层)≥β(后继层),则可中止此MIN节点以下的搜索过程.

    此MIN节点的最终倒推值就确定为此β值.

β剪枝(发生在极大层节点)---从一个子树获得的极小节点的β值，可以传送给该节点的其他子节点，从而选择β剪枝机会

    若对任一极大值层节点,α(后继层)≥β(任意父辈层),则可中止此MAX节点以下的搜索过程.

    此MAX节点的最终倒推值就确定为此α值。

代码如下：

        吐槽：晚上写完感觉逻辑没问题终于交了，结果还是WA，后来发现是输出少了空格（这一句：Who play first(0: computer; 1: player )?）；改了之后AC了，，，但是看了看报表，看到一个1378B，22行过的，于是我看着我9492B，391行的代码陷入了沉思（嘶，不是哥们，这我怎么睡的着啊？就22行，我是真想不明白，除了printf/cout还能怎么写，毕竟这次测试用例是给出的三个，没有隐藏）

        强调尽量不要格式化文档，vscode的格式化文档害我WA好多次┭┮﹏┭┮，对了，现在只有6755B 303行了（合并了一些函数，去掉了一些实际上需要但是这道题测试用例考不到的检错代码）

        吃个饭回来写注释。

        注释写了，但是习惯性格式化了，现在输出不一定能过测试用例了应该，估计会少或者多个空格之类的。

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
typedef enum // 列表元素的类别
{
    ATOM,
    LIST
} ElemClass;
typedef struct GLNode
{
    ElemClass Class; // 元素的类别
    union
    {
        char atom; // 原子值
        struct
        {
            GLNode *head; // 子列表的头指针
            GLNode *tail; // 子列表的尾指针
        } ptr;
    };
} *Glist;
typedef struct Node
{
    char data;          // 节点存储数据
    int status;         // 预处理状态标志
    struct Node *first; // 指向第一个子节点的指针
    struct Node *next;  // 指向下一个兄弟节点的指针
} *Tree;
int CreateGlist(Glist &L, string s)
{
    if (s == "()")
        L = NULL; // 将广义表指针设为NULL，表示空列表
    else
    {
        L = new GLNode; // 创建一个新的广义表节点
        if (s.length() == 1)
        {
            L->Class = ATOM; // 设置节点类别为原子
            L->atom = s[0];  // 将原子值存储在节点中
        }
        else
        {
            L->Class = LIST;                 // 设置节点类别为列表
            string sub, headsub;             // sub表示子串，headsub表示头部子串
            sub = s.substr(1, s.size() - 2); // 去除外层括号，得到子串
            Glist p, q;                      // p表示当前节点，q表示上一个节点
            p = L;
            while (!sub.empty())
            {
                int i, k = 0;
                int n = sub.length();
                char c = '\0';
                for (i = 0; i < n && (c != ',' || k != 0); i++) // 查找子串中的逗号
                {
                    c = sub[i];
                    k += (c == '(') ? 1 : ((c == ')') ? -1 : 0); // 统计括号的个数
                }
                headsub = (i < n) ? sub.substr(0, i - 1) : sub; // 获取头部子串
                sub = (i < n) ? sub.substr(i, n - i) : "";      // 更新子串，去除已处理的部分
                CreateGlist(p->ptr.head, headsub);              // 递归创建子列表（或者说是更新）
                q = p;
                if (!sub.empty())
                {
                    p = new GLNode; // 创建新的广义表节点
                    p->Class = LIST;
                    q->ptr.tail = p; // 将新节点连接到上一个节点的尾部
                }
            }
            q->ptr.tail = NULL; // 最后一个节点的尾部设为NULL
        }
    }
    return 1; // 返回创建成功的标志
}
void CreateTree(Tree &root, Glist L)
{
    if (L) // 如果广义表不为空
    {
        root = new Node;                // 创建一个新的节点
        root->data = L->ptr.head->atom; // 将广义表头部的原子值存储在节点中
        root->first = NULL;             // 初始化节点的第一个孩子和下一个兄弟节点为NULL
        root->next = NULL;
        if (L->ptr.tail) // 如果广义表有尾部，即有子列表
        {
            Glist head = L->ptr.tail->ptr.head; // 获取尾部的头部子列表
            Glist t = L->ptr.tail->ptr.tail;    // 获取尾部的尾部子列表
            CreateTree(root->first, head);      // 递归创建第一个孩子节点
            Node *p = root->first;              // 指向当前孩子节点
            while (t)                           // 遍历尾部的剩余子列表
            {
                head = t->ptr.head;        // 获取当前子列表的头部
                t = t->ptr.tail;           // 获取当前子列表的尾部
                CreateTree(p->next, head); // 递归创建下一个兄弟节点
                p = p->next;               // 移动到下一个兄弟节点
            }
            p->next = NULL; // 最后一个兄弟节点的下一个节点设为NULL
        }
    }
    else
        root = NULL; // 如果广义表为空，树的根节点设为NULL
}
int PreTreat(Tree root)
{
    if (!root)             // 树为空
        return 1;          // 返回1,表示预处理完成
    if (!root->first)      // 如果树的第一个孩子为空
        root->status = 1;  // 将根节点的状态设为1
    PreTreat(root->first); // 递归预处理根节点的第一个孩子节点
    PreTreat(root->next);  // 递归预处理根节点的下一个兄弟节点
    if (root->first)       // 如果根节点有第一个孩子节点
    {
        Node *p = root->first; // 指向第一个孩子节点
        int flag = 1;          // 标志位，初始设为1
        while (p)              // 遍历根节点的孩子节点
        {
            if (p->status == 1) // 如果孩子节点的状态为1
            {
                flag = 0; // 将标志位设为0
                break;
            }
            p = p->next; // 移动到下一个兄弟节点
        }
        root->status = flag; // 将根节点的状态设为标志位的值
    }
    return 1; // 返回1,表示预处理完成
}
int GetHeight(Tree root)
{
    if (root == NULL) // 如果树为空
        return 0;     // 返回高度为0
    else
    {
        int head, h2;                  // head表示第一个孩子节点的高度，h2表示兄弟节点的高度
        head = GetHeight(root->first); // 递归获取第一个孩子节点的高度
        if (head != 0)                 // 如果第一个孩子节点的高度不为0
        {
            root = root->first; // 将根节点指向第一个孩子节点
            while (root)        // 遍历兄弟节点
            {
                h2 = GetHeight(root->next); // 递归获取兄弟节点的高度
                if (head < h2)              // 如果兄弟节点的高度大于第一个孩子节点的高度
                    head = h2;              // 更新第一个孩子节点的高度为更大的值
                root = root->next;          // 移动到下一个兄弟节点
            }
        }
        return head + 1; // 返回树的高度（第一个孩子节点的高度加1）
    }
}
Tree Computer(Tree root)
{
    int win = INF;        // 最小值，用于记录最小高度
    int lose = 0;         // 最大值，用于记录最大高度
    Tree p = root->first; // 指向第一个孩子节点
    Tree q1, q2;          // 用于记录选中的节点
    while (p)             // 遍历孩子节点
    {
        int head = GetHeight(p); // 获取当前孩子节点的高度
        if (p->status == 1)      // 如果孩子节点状态为1（表示胜利的情况）
        {
            if (height < win) // 如果当前孩子节点的高度小于最小高度
            {
                win = height; // 更新最小高度
                q1 = p;     // 记当前节点为选中节点
            }
        }
        else // 如果孩子节点状态为0（表示失败的情况）
        {
            if (height > lose) // 如果当前孩子节点的高度大于最大高度
            {
                lose = height; // 更新最大高度
                q2 = p;      // 记当前节点为选中节点
            }
        }
        p = p->next; // 移动到下一个兄弟节点
    }
    if (win != INF) // 如果存在胜利的情况
    {
        cout << "computer: " << q1->data << endl; // 输出选中节点的数据
        return q1;                                // 返回选中节点
    }
    else // 如果不存在胜利的情况
    {
        cout << "computer: " << q2->data << endl; // 输出选中节点的数据
        return q2;                                // 返回选中节点
    }
    return root; // 如果无法确定选中节点，则返回根节点
}
Tree Human(Tree root)
{
    cout << "player:" << endl;
    char c;
    cin.ignore();          // 忽略之前的输入缓冲,去除回车
    cin >> c;              // 获取玩家输入的字符
    Node *p = root->first; // 指向第一个孩子节点
    while (p)              // 遍历孩子节点
    {
        if (p->data == c) // 如果节点的数据等于玩家输入的字符
            return p;     // 返回该节点作为玩家选中的节点
        p = p->next;      // 移动到下一个兄弟节点
    }
    cout << "illegal move." << endl; // 如果没有匹配的节点，输出非法移动提示
    return root;                     // 返回根节点
}
Tree ValidMove(Tree p)
{
    while (1) // 无限循环，直到玩家选择一个有效的移动
    {
        Tree q;       // 用于存储玩家选择的节点
        q = Human(p); // 玩家进行选择，获取玩家选中的节点
        if (q != p)   // 如果玩家选择的节点与当前节点不相同（表示有效移动）
            return q; // 返回玩家选择的节点
    }
}
int Move(Tree root)
{
    while (true) // 无限循环，直到玩家选择不继续游戏
    {
        cout << "Who play first(0: computer; 1: player )?" << endl; // 提示选择谁先玩
        int player, flag = 0;                                       // player表示玩家选择的角色，flag用于标记当前玩家是电脑还是玩家
        cin >> player;                                              // 获取玩家选择的角色
        Tree p;                                                     // 用于存储当前节点
        if (player == 0)                                            // 如果玩家选择电脑先玩
        {
            p = Computer(root); // 电脑进行移动选择
            flag = 0;           // 标记当前玩家为电脑
        }
        else // 如果玩家选择玩家先玩
        {
            p = Human(root); // 玩家进行移动选择
            flag = 1;        // 标记当前玩家为玩家
        }
        if (p->first == nullptr) // 如果当前节点没有孩子节点（表示游戏结束）
        {
            if (flag == 0)                          // 如果当前玩家为电脑
                cout << "Sorry, you lost." << endl; // 输出玩家失败的信息
            else
                cout << "Congratulate, you win." << endl; // 输出玩家胜利的信息
            cout << "Continue(y/n)?" << endl;             // 询问是否继续游戏
            char c;
            cin >> c;     // 获取玩家选择
            if (c == 'y') // 如果玩家选择继续游戏
                continue; // 继续下一轮游戏
            else
                return 1; // 结束游戏
        }
        while (true) // 内层循环，直到游戏结束
        {
            if (flag == 1 && p != root) // 如果上一步为玩家且不是根节点
            {
                p = Computer(p);         // 电脑进行移动选择
                if (p->first == nullptr) // 如果当前节点没有孩子节点（表示游戏结束）
                {
                    cout << "Sorry, you lost." << endl; // 输出玩家失败的信息
                    break;
                }
                p = ValidMove(p); // 玩家进行移动选择
                if (p->first == nullptr)
                {
                    cout << "Congratulate, you win." << endl;
                    break;
                }
            }
            else // 如果上一步为电脑或者是根节点
            {
                p = ValidMove(p);        // 玩家进行移动选择
                if (p->first == nullptr) // 表示游戏结束
                {
                    cout << "Congratulate, you win." << endl;
                    break;
                }
                p = Computer(p);         // 电脑进行移动选择
                if (p->first == nullptr) // 表示游戏结束
                {
                    cout << "Sorry, you lost." << endl;
                    break;
                }
            }
        }
        cout << "Continue(y/n)?" << endl;
        char c;
        cin >> c;
        if (c == 'y')
            continue; // 继续下一轮游戏
        else
            return 1; // 结束游戏
    }
    return 1;
}
int main()
{
    string s;
    cin >> s;
    int i;
    for (i = 0; s[i] != '\0'; i++)
        if (s[i] >= 'a' && s[i] <= 'z')
            cout << s[i] << endl;
    Glist L;
    CreateGlist(L, s);
    Tree root;
    CreateTree(root, L);
    PreTreat(root);
    Move(root);
    return 0;
}