北大公开课-人工智能基础 31 对抗性搜索之 a-b剪枝

之前的课程已经说过了，通过互相action的节点，形成一棵决策树。

而随着博弈的深入，决策树的节点增加是指数式的

通过a-b剪枝，可以至少砍去一半的决策树，提高对抗性搜索的效率。

只考虑有希望的节点及其后续节点，对于明显价值较差的节点，尽早剪枝，节省算力。

a:对于本方max的一系列最大值的节点。

b：对于对方一系列最小值的节点。

如果当前节点差于a，或者高于b，则直接剪枝舍去。

alpha-beta算法

通过max的最大值alpha，或min的最小值 beta，定义值v

将当前状态与 alpha，beta值比较，

若当前状态好于alpha或差于beta，则将当前值赋值给新的v

否则，则舍去当前状态节点及其后续子节点。

这是一个交替执行的决策树

max执行了自己的步数，得到值3

min执行的步数中，取最小值

max在min最小值的节点中，再求下一步骤的最大值。

剪枝是剪去整个枝干（剪去某一节点及其全部后续节点），

而非只是剪去某一个节点。可以大大提升搜索的效率。