AlphaBeta剪枝算法求解博弈树最优选择 头歌实验平台

---

前言

产生本文的缘由

人工智能原理课程 可选实验 “AlphaBeta剪枝算法求解博弈树最优选择”,
以及去年在数据结构导论没有看明白的博弈论.
记录自己的学习过程.

注:本文适合有一定基础的读者阅读.

---

以下是本篇文章正文内容

一、AlphaBeta剪枝是什么？

1.由来, 最大最小决策树

矩形一层的节点 选择较大值
圆形一层的节点 选择较小值
深度搜索 比较节点值 加上回溯即可.

2.发展

人们发现这些节点的比较过程很多是无意义的, 比如说对于上图的H节点
当C节点的正无穷大和H节点的2比较时, C节点值更新为2, 此时, 由于C是圆形一层的节点,
只能选择较小值.

那么C节点的取值只能小于等于2了

但是矩形节点A是在 圆形节点B, C, D中选择一个最大的值

然而B节点的值已经为3 , 那么A不可能考虑C了

,所以对于C的子节点 H, I , 都没有必要继续进行访问 并且比较更新C的节点值了

3. AlphaBeta剪枝

有图有真相 , 橙色画叉的就是剪枝的部分了, 根据该节点是矩形和圆形来判断是Alpha还是Beta剪枝 , 比如说C节点 划掉了I 和 J , 而C节点是圆形的, 所以是Alpha剪枝.

其实更准确的定义是, 当时是因为v<=alpha 还是 v>=beta 剪枝来判断的, 比如说C节点进行剪枝的时候, v<=alpha

---

二、实验算法伪代码

读者可以对照下面的实验源码部分 ,下面的三个函数 (从上到下) 分别对应于源码中的 minmax_with_alphabeta
max_value
min_value

如果要真正搞懂, 请一定要去debug啊啊啊

---

三、实验算法代码

注意: 这个代码在python3.7.9下 (除了python3.10以上的 python3应该都可以) 可以直接运行, 输出的是路径

# -*- coding:utf-8 -*-

import copy     # 注意对象的深拷贝和浅拷贝的使用！！！ #这个没有用到


class GameNode:
    '''博弈树结点数据结构
    成员变量：
    name - string 结点名字
    val - int  结点值
    children - list[GameNode] 子结点列表
    '''

    def __init__(self, name='', val=0):
        self.name = name        # char
        self.val = val          # int
        self.children = []      # list of nodes


class GameTree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19