下棋属于一种博弈游戏，博弈过程可以用树（博弈树）来表示。假设游戏由两个人（ 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
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 3 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
博弈树学习笔记：
完全博弈问题--下棋
特点：
双人对弈: 轮流下,一人走一步.
信息完备: 双方看到的信息一样.
零和: 双方利益冲突,对一方有利则对另一方不利。
极小极大搜索方法: (假定对手每次回应都正确,即选择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 <iostream>
#include <string>
#include <cstring>
#include <algorithm>
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
{
int status;
char data;
struct Node *first, *next;
} *Tree;
int CreateGlist(Glist &L, string s)
{
if (s == "()")
L = NULL;
else
{
L = new GLNode;
if (s.length() == 1)
{
L->Class = ATOM;
L->atom = s[0];
}
else
{
L->Class = LIST;
string sub, headsub;
sub = s.substr(1, s.size() - 2);
Glist 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;
}
}
return 1;
}
void CreateTree(Tree& root, Glist L)
{
if (L)
{
root = new Node;
root->data = L->ptr.head->atom;
root->first = 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;
}
}
else
root = NULL;
}
int PreTreat(Tree root)
{
if (!root)
return 1;
if (!root->first)
root->status = 1;
PreTreat(root->first);
PreTreat(root->next);
if (root->first)
{
Node *p = root->first;
int flag = 1;
while (p)
{
if (p->status == 1)
{
flag = 0;
break;
}
p = p->next;
}
root->status = flag;
}
return 1;
}
int GetHeight(Tree root)
{
if (root == NULL)
return 0;
else
{
int head, h2;
head = GetHeight(root->first);
if (head != 0)
{
root = root->first;
while (root)
{
h2 = GetHeight(root->next);
if (head < h2)
head = h2;
root = root->next;
}
}
return head + 1;
}
}
Tree Computer(Tree root)
{
int win = INF, lose = 0;
Tree p = root->first, q1, q2;
while (p)
{
int head = GetHeight(p);
if (p->status == 1)
{
if (head < win)
{
win = head;
q1 = p;
}
}
else
{
if (head > lose)
{
lose = head;
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;
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;
}
