题目引入
在博弈论中，有这样一类题目：
- 两个玩家 A、B 轮流行动，A 先手，B 后手。
- 有一个结果，A 想要使它最大，B 想要使它最小。
Minimax 算法
把每个状态作为一个点，每个转移作为一条边建出一棵树。这棵树好像叫博弈树。
两种实现（都没有真正地建树）：
- 直接搜索（可能有结点被重复经过）
- 记忆化搜索。
现在我们不考虑 当前的 先手和后手，而是考虑当前结点是 一开始的 先手还是后手行动，即是 A 还是 B 行动。
每个状态得到一个确定的权值。因为 A 想让权值尽量大，所以 Ta 会在 Ta 行动的每一步都取子结点权值的 max。类似地，B 会在 Ta 行动的每一步取子结点的 min。
那么直接用上面提到的两种实现来实现这个“树形 DP”的过程即可。
Alpha-Beta 剪枝
jsh: 画图！
参考
https://zhuanlan.zhihu.com/p/404144927 （应该不全）
https://oi-wiki.org/search/alpha-beta/ （主要是代码实现）
https://www.cnblogs.com/wkfvawl/p/12066647.html
2024.10.18
标签：剪枝,结点,Minimax,Beta,https,权值 From： https://www.cnblogs.com/huangkxQwQ/p/18474903