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
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 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还能怎么写，毕竟这次测试用例是给出的三个，没有隐藏）
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;更多推荐
3. 博弈树 (15分)
发布评论