参考链接： 人工智能对抗搜索
https://blog.csdn.net/NGUever15/article/details/89160951
对抗搜索
文章目录
对抗搜索1 博弈multi-agent 环境形式化搜索问题
2 博弈中的优化决策2.1 极小极大算法2.2 多人博弈时的最优策略
3 $alpha-beta$ 剪枝3.1 行棋排序
4 不完美的实时决策4.1 评估函数4.2 截断搜索4.3 向前剪枝
1 博弈
假设：
有两个选手完全可观察，确定性的环境zero-sum（零和游戏）时间受限
multi-agent 环境
合作 vs 对抗 对抗的情况下，产生博弈搜索问题。
对抗搜索的例子：
国际象棋西洋跳棋大富翁黑白棋
共同的特点就是 状态空间比较大
举例中国象棋： state space:
三十二个棋子十四种棋子九列十行
？？? 如何处理这么大的状态空间。 可以采用迭代加深的策略来解决
考虑两个人博弈：MAX & MIN MAX先行，轮流出招，直到游戏结束。给胜者加分，给败者减分。
形式化搜索问题
初始状态： Actions 转移模型 目标测试 路径代价
其中，节点是状态，边是移动。
2 博弈中的优化决策
最底部分数是max的得分 max 在选择时，选择 使其得分max 的路径。 min 在选择时，选择使max 得分min的路径。
2.1 极小极大算法
2.2 多人博弈时的最优策略
考虑联盟的情况，若A与B联盟，则往右边走；若A与C联盟，则往左边走。
3
α
−
β
alpha-beta
α−β 剪枝
图中存在哪些节点不必搜索？及max（）的值与哪些值无关？ 结果： 只有4 和 6 两个节点用不到。 计算公式： 在C下发现2了之后，就不用再接着看 4 和 6 了，因为最小值一定小于等于2，而2 小于B下的最小值3，所以一定不会选它。 具体的查询过程如下图所示。 [ ]表示当前节点的效用范围。 当
α
⩾
β
alpha geqslant beta
α⩾β时，不用再接着搜索。
节点的排序，影响剪枝的效果。 min节点从小到大排序，剪枝更多。 max 节点从大到小排序，剪枝更好。
3.1 行棋排序
时间有限，实行深度受限搜索。 采用迭代加深搜索。
4 不完美的实时决策
？？？如何设计评估函数。 ？？？ 如何截断。
4.1 评估函数
如何设计评估函数：
与获胜概率相关
定义状态的类别 特征的组合： 多数评估函数 会分别计算每个特征的影响，然后把他们组合起来找到总数值。 ？？？如何获取棋力值和组合权重。
4.2 截断搜索
？？？如何截断，以满足时间限制
评估函数是不准确的，截断可能导致错误。 典型的错误：
评估值的摇摆。地平线效应问题
4.3 向前剪枝
向前剪枝的方法：柱搜索 在每一层只考虑最好的n步行棋方式。
max 改下限 只能更大 min 改上限 只能更小
