博弈树的搜索算法(一)

Stubborn

MaxMin算法（极大极小值算法）

该算法是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归形式来实现。
Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的一个，其输赢的总和为0。

其实一般不太建议用这种算法，不过由于这个是AlphaBeta剪枝算法的前置，所有这里还是介绍一下。

介绍这个算法前，简单的介绍一下博弈树。如下图井子琪游戏为例，这只是一个简略的博弈树，整个博弈树有多少个节点的呢？答案是9!，共计362880个节点。而该算法则会尽心尽力的去搜遍这362880个节点。所以这是一个不“太聪明”的算法，也型号，这个是可以改进的，这里暂且不提。





MINMAX的基本思想，我们程序在搜索完成井子琪游戏的博弈树之后，可以知道所有的游戏的结局，知道哪个分枝会输，知道哪个分枝会赢，或者平局。既然知道结局，那么把结果传播回去就可以，假定电脑赢游戏，对游戏给定 1 分的评价，电脑输游戏，给对游戏给定 -1 分的评价，如果是平局，对游戏给定 0 分的评价。并且假定对手是非常聪明的，他落子的时候，总会选择最优的局面，对电脑而言就是最差的局面。

python伪代码实现

1. 
   
2. def MiniMaxAlgorithm(int: depth,  flag)：
   
3.     # depth:: 是深度的意思，对于一些游戏树是深不可达，所以一般扩展到某一个游戏状态就停止了
   
4.     #  定义递归出口,或者是游戏结束状态，返回当前游戏状态的评分
   
5.     if (depth==0 and GameOver)：
   
6.         # 评分函数，赢了，输了，平局，会在自己定义响应的规则评分
   
7.         return EvaluationFunction(Gs)
   
8.     MaxValue = float('-inf')
   
9.     MinValue = float('inf')
   
10.     # 测试所有合法的着点
    
11.     for Move in GeneratorMoves:
    
12.         # 执行着点
    
13.         MakeNextMove()
    
14.         # 交换身份，继续，
    
15.         score = MiniMaxAlgorithm(depth-1, falg)
    
16.         # 撤销着点
    
17.         UnMakeNextMove()
    
18.         # 如果当前是电脑走步落子
    
19.         if flag is Max:
    
20.             MaxValue = max(score, MaxValue)
    
21.         else:
    
22.             MinValue = min(socre, MinValue)
    
23.     if flag is Max:
    
24.         return Maxvalue
    
25.     else:
    
26.         return MinValue
    
27. 
    

复制代码

傻眼貓咪

其实博弈树可以说是用内存替代的演算法吧？简单的说就是运算未来可能的路线，并且找出最优路线（算命师 + 风水师？）。
目前为止，世界级 AI 无论是象棋、五子棋等，棋盘游戏用博弈树方法（包括 AlphaBeta 等算法）最多也只能预算后十步以内吧（这已经是超级电脑的极限了，预设树根 root 的上限），不可能预算到游戏结束为止的所有步骤。毕竟每预算下一步所需的内存负担是以次方在增加的（井字棋游戏共 362880 个节点，扣除不合理步骤，也有 255168 个棋局之多啊）。

Stubborn

傻眼貓咪 发表于 2022-4-23 18:02
其实博弈树可以说是用内存替代的演算法吧？简单的说就是运算未来可能的路线，并且找出最优路线（算命师 +  ...

人下棋不也一样吗，我们的思维在布局，布陷阱，或者厉害的棋手可以看透预见后面棋。
这个我一个可以打包票，十步不止，虽然博弈树很大，但是阿尔法GO用的是蒙特卡洛算法，在看到的分支里面，远远大于一般的搜索。后面还有三篇，会有说AlphaBeta PV MCTS算法

hrpzcf

收藏吃灰