Python人工智能概述——博弈、对抗搜索

Python人工智能

Python人工智能概述——约束满足（扑克牌问题）
Python人工智能概述——对抗搜索
更新ing

---

理解对抗搜索

• Python人工智能
• 前言
• 一、博弈
• • 1.对抗性博弈
  • 2.博弈树
• 二、对抗搜索
• 三、算法实现
• • 1.Minmax（搜索）
  • 2.Minmax（计算）
  • 4.算法分析
• 四、剪枝

---

前言

近期更新都是课程所学内容，具体实验还未完成，完成后一并发出，感谢关注。

一、博弈 1.对抗性博弈

我们早已听说了2016年Alpha Go在围棋界的战绩，在这之前，2006年计算机浪潮天梭也拿下了中国象棋的第一，97年的IBM深蓝也赢过不少国际象棋大师。

对抗性博弈：一定规则下，有完备信息、确定性，轮流行动的，两个游戏者的零和游戏——《人工智能——一种现代方法》

特点：信息完整、确定、双方轮流、零和。

“零和游戏”也叫“零和博弈”。是指在一项游戏中，参加者有输有赢，赢家所得正好是输家所失，总成绩永远为零，这就叫“零和”。

2.博弈树

二、对抗搜索

Minimax算法：极小化极大算法是基于决策树和搜索的智能系统中的典型算法，可用于指导井字棋、黑白棋、五子棋等经典完全信息零和博弈。）（决策树相关内容可以参考《人工智能——决策树》）
Max：最大化收益（AI的结点层）
Min：最小化收益（玩家的结点层）

特点：1.状态空间是树
2.交替轮换
3.计算每个结点的极大极小值

当AI下棋的时候，他会考虑对自己最有利的节点，也就是Max，此时主动权在AI手中，但是轮到玩家的时候，玩家会下在AI最小收益的地方，也就是Min，主动权在玩家手里，AI肯定想让自己收益最大，但是玩家肯定要让AI的收益最小，所以AI和我们下棋一样，需要预测玩家下一步，和自己的下下步…最后返回一个值

以上图为例，AI会选择右边的结点，因为哪怕最差都可以得到5，选择左结点的话，虽然有拿8的可能，但是还可能得到2，就好比是打怪的时候前面有装备，但是前面也有大怪，过去拿装备有可能就没命了，肯定还是小命要紧。

三、算法实现 1.Minmax（搜索）

def maxvalue(state)
	  initalize v=负无穷
	  for each successor of state:
	  		v = max(v,minvalue(successor))
	  return v

def minvalue(state)
	  initalize v=正无穷
	  for each successor of state:
	  		v = min(v,maxvalue(successor))
	  return v

2.Minmax（计算）

def	value(state):
	if the state is a terminal state: 
		return the state's utility
	if the next agent is MAX:
		return maxvalue(state)
	if the next agent is MIN:
		return minvalue(state)

4.算法分析

搜索方法：与深度优先类似
时间复杂度：b的m次方
空间复杂度：bm
面临难题：仅仅在50个格子中，只是搜索四步就需要50的四次方=625w
所以无法获得完整的博弈树

四、剪枝

Minmax算法是一种双人博弈中寻找最优解的方法
而剪枝可以避免搜索不可能被选择的步骤的子树。（比如下棋的时候，一眼输的落子点直接pass了）
还是以刚刚那个图为例
当搜索完中间的子树后，知道中间最小为6，此时搜索最右边子树，发现第一个为14，继续搜素，第二个就为5，已经小于6了，后续的2就更不用搜索了。

抱歉哈，最近比较忙，这几天先更新人工智能的文章。其余几篇文章还没来得及写（代码搞完了），最迟下周末发matlabPTB和STC8H系列单片机的两三篇文章。