noone___'s blog
0%

minmax搜索

发表于 更新于 分类于
莫名其妙被卢神推荐让写的东西

minimax搜索（对抗搜索）

qwq莫名在做博弈论时就被卢神推荐来做这个了

常见形式

两人轮流走棋，两人目标相背

  • A希望B输，B希望A输
  • A使得分最多，B使得分最少。

双方智商均在线且极高

实现

dfs搜博弈树

思想

把走法看成一棵树

圆形代表 $A$，正方形代表 $B$ ，节点的每个孩子节点代表一个候选方案。

注：圆圈中的数字为 $A$ 的利益值，越大对A越有利

  • 假设 $A$ 选择第一种方案（即走第一个子节点）

    那么 $B$ 将有两种选择，一种使 $A$ 的值为 $7$，一种使 $A$ 的值为 $3$，那么显然 $B$ 会选择 $3$

  • 假设 $A$ 选择第二种方案

    那么 $B$ 只有一种选择

  • 同理得第三种情况

又因为 $A$ 需要最佳方案

于是有

$alpha-beta$剪枝优化

为便于理解，将 $A$ 走的节点命名为 $max$ 节点，$B$ 走到节点命名为 $min$ 节点

$alpha-beta$ 剪枝的基本思想:

是对于每个 $max$ 结点设置一个目前已知下界 $alpha$ ，每个 $min$ 节点设置一个目前已知上界 $beta$ 。$alpha$ 代表 $A$ 可以搜索到的最好值，$beta$ 代表了 $B$ 可以接受的最坏值。

如果某个行动的结果 $\leq alpha$ ，那么它就是很差的行动，$A$ 可以选择更好的行动（即当前 $alpha$ 值的行动）。

反之，如果某个行动的结果 $\geq beta$，那么整个节点就作废了，因为对手不希望走到这个局面，而它有一定有别的行动（即走当前 $beta$ 值的行动）可以避免到达这个局面。

那么发生下面两种情况时可以剪枝，即停止搜索该节点的其余子节点：

  1. 不用该点走：当计算一个 $min$ 结点时，如果它的 $beta$ 值小于等于其父结点的 $alpha$ 值，则可以立即停止此结点的计算（ $alpha$ 剪枝）。

  2. 走多了：当计算一个 $max$ 结点时，如果它的 $alpha$ 结点大于等于其父结点的 $beta$ 值，也可以立即停止此结点的计算（ $beta$ 剪枝）。

基本格式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int dfs(Status s,int Alpha,int Beta,int Which)
//Status记录当前状态，Which记录当前操作的选手，其中0号选手取Max，1号选手取Min
//Alpha存储较大值，Beta存储较小值
//如果当前节点是取Max的节点，则Alpha表示当前节点父亲的父亲的权值，Beta表示当前节点父亲的权值
//如果当前节点是取Min的节点，则Alpha表示当前节点父亲的权值，Beta表示当前节点父亲的父亲的权值
{
    if(IsEnd(s)) return GetVal(s);//如果当前状态已经为最终状态，就返回当前状态的分值
    rei i;
    expend(s);//扩展当前状态，并将新状态存储于NewStatus数组中，用NewStatusTotal记录新状态的数量
    for(i=1;i<=NewStatusTotal;++i)//枚举从当前状态能够扩展到的新状态
    {
        t=dfs(NewStatus,Alpha,Beta,Which^1);//求出当前枚举到的新状态的分值
        (s.Which?Beta=min(Beta,t):Alpha=max(Alpha,t)); //如果当前节点取min，就更新Beta，否则更新Alpha
        if(Alpha>=Beta) break;//如果Alpha≥Beta，就说明这个节点对最终答案没有贡献了，就结束搜索
    }
    return s.Which?Beta:Alpha;//返回相应值
}

例题

ICPC Asia Nanning 2017 I. Rake It In

P4576 [CQOI2013]棋盘游戏

World Finals 2009 LA4451 House of Cards UVA1085

/*刘汝佳的毒瘤题*/

UVA10838 The Pawn Chess