对抗搜索(Adversarial Games)

发布于 2022-08-07  112 次阅读


又是没见过的算法,oiwiki上都没有,不过思路似乎很直白

属于是机器学习算法向竞赛算法渗透了

主要有三种方式,分别为:minmax搜索,Alpha-Beta搜索和蒙特卡洛搜索

minmax搜索

考虑对答案的贡献,玩家想让价值尽可能大,而对抗者想让价值尽可能小,则可以建立一棵树,奇数层玩家行动,偶数层对抗者行动,那么根节点就是能够得到的最优解。

非常贪心的一个思路,就是每一步玩家行动就取大的方向,对抗者行动就取小的方向。

复杂度O(b^m)m为最大深度,b为每个节点的转移方式数量。

Alpha-Beta剪枝搜索

是对minmax搜索的剪枝优化。

依然是非常直白的优化策略,对于玩家,当前一步操作取得的最大价值为\alpha,那么对于这一层来说价值的下界就是\alpha。小于这个下界的操作就不用考虑了,也就不用再搜下去。

对于对抗者,当前一步可以取得的最小价值\beta,那么对于这一层来说价值的上界就是\beta,因为它不会让你取到更大的价值。

由此可得:

  1. Max层的\alpha=max(\alpha,所有子节点的评价值)\beta=父节点的\beta
  2. Min层的\alpha=父节点的评价值\beta=min(\beta,所有子节点的评价值)
  3. 当某个节点的\alpha\geq\beta,剪枝
  4. 叶节点没有\alpha,\beta

搜索顺序会影响剪枝的效率,但不会影响结果。听说最优可以减到O(\frac{b^m}{2}),但具体按什么顺序减感觉很tricky。

蒙特卡洛树搜索MCTS

这玩意居然能用在ACM???


盛夏日落迟 灯火未夜匆匆明