Minimax

博弈游戏可以简化成这样的局面:第 ii 轮我方行动,目的是最大化得分;下一轮对手行动,目的是最小化我方得分;再下一轮又是我方行动,目的是最大化得分……如此往复。


Minimax 搜索优化:Alpha-Beta 剪枝

记节点分数为 xx,我们给每一个节点维护两个值 α,β\alpha,\beta 满足 αxβ\alpha\le x\le\beta. 算法流程大致如下:

  1. 如果是我方行动