1、Game Playing博弈 博弈被被认为是AI研究领域中的一个很好的难题:博弈是不平凡的 玩家需要具备“human-like”般的智能 游戏可能非常复杂(e.g.,Chess,Go)需要在有限时间内作出决策 games usually are:定义明确的且可重复的 完全可观察的环境是有限的 能直接比较humans and computersComputers Playing Chess对战中的AIComputers Playing Go本章大纲 博弈 博弈中的优化决策 极小极大值算法-剪枝 资源限制和近似评估 包含几率因素的游戏 不完整信息的游戏Games vs.search problem
2、s不可预测的对手解决方案是针对每一个可能的对手回复的策略时间是有限的 不太可能找到最优解，需找到近似解游戏对于低效率有严厉的惩罚 进攻计划:Computer considers possible lines of play(Babbage,1846)Algorithm for perfect play(Zermelo,1912;Von Neumann,1944)Finite horizon,approximate evaluation(Zuse,1945;Wiener,1948;Shannon,1950)First chess program(Turing,1951)Machine learn
3、ing to improve evaluation accuracy(Samuel,1952-57)Pruning（剪枝）to allow deeper search(McCarthy,1956)游戏的种类确定性的 随机的、策略的 博弈树(2-player,确定性的,轮流出招)确定性的Two-Player E.g.井字棋,国际象棋,跳棋 博弈搜索 状态-空间 搜索树 玩家轮流出招每一层包含一轮行动选择能获得最佳效用的行动 零和游戏 一个玩家要最大化效用值 而另一个要最小化效用值极小极大值原理 假设两位玩家都按照最佳策略行动 computer 假设在其行动以后，其对手会选择效用值最小的状态来移动
4、 computer在选择其最佳行动方案时要同时考虑自己以及对手的最佳行动从max的角度显示效用值Minimax 确定性的，完全信息的博弈的最优策略Idea:choose move to position with highest minimax value=best achievable payoff against best play在对手也使用最优策略的条件下，能导致至少不比其它策略差的结果假设两个游戏者都按照最优策略进行，那么节点的极小极大值就是对应状态的效用值（对于MAX）MAX优先选择有极大值的状态 MIN优先选择有极小值的状态 Minimax 确定性的，完全信息的博弈的最优策略Id
5、ea:choose move to position with highest minimax value=best achievable payoff against best play在对手也使用最优策略的条件下，能导致至少不比其它策略差的结果E.g.,2-ply game:Minimax algorithmMinimax 的性能完整性？Minimax 的性能完整性？仅当博弈树是有限时(chess has specific rules for this).但在一颗无限的博弈树中也存在有限的策略 最优性？Minimax 的性能完整性？Yes,仅当博弈树是有限时最优性？Yes,遇到一个聪明的对
6、手。Otherwise?时间复杂度？Minimax 的性能完整性？Yes,仅当博弈树是有限时最优性？Yes,遇到一个聪明的对手。Otherwise?时间复杂度？O(bm)空间复杂度？Minimax 的性能完整性？Yes,仅当博弈树是有限时最优性？Yes,遇到一个聪明的对手。Otherwise?时间复杂度？O(bm)空间复杂度？O(bm)(深度优先搜索)For chess,b35,m100 for“reasonable games寻找精确解时完全不可行的But do we need to explore every path?-剪枝 若与一个聪明的对手对弈，则博弈树上的一些分枝绝不会发生“If
7、you have an idea that is surely bad,dont take the time to see how truly awful it is.”-Pat Winston 剪枝能消除搜索树的很大一部分分枝 pruning example pruning example pruning example pruning example pruning example为什么叫 is the best value(to MAX)found so far on the current path到目前为止在路径上的任意选择点发现的MAX的最佳（即最大值）选择 If v is wor
8、se than,MAX will avoid it,so can stop considering vs other children prune that branch Define similarly for MINThe algorithm剪枝技术 对于一个MAX节点来说，它取值称为值 对于一个MIN节点来说，它取值称为值 剪枝：任何MAX节点x的值如果不能降低其父节点的值，则对节点x以下的分枝可停止搜索。剪枝：任何MIN节点x的值如果不能升高其父节点的值，则对节点x以下的分枝可停止搜索。剪枝案例搜索的效率 效率很大程度上取决于检查后继的顺序;所以尝试检查可能较好的后继是值得的 最坏情况
9、:没有分枝需要修剪 相比于穷举搜索没有改进 最好情况:每个玩家的最佳行动都先被检查 在实践中，性能接近于最好情况，而不是最坏情况，但要依实际情况而定的性能剪枝不影响最终结果好的行动顺序能提高剪枝的效率With“perfect ordering,time complexity=O(bd/2)doubles solvable depth不幸的是,3550 也是有可能的本章大纲 博弈 博弈中的优化决策 极小极大值算法-剪枝 资源限制和近似评估 包含几率因素的游戏 不完整信息的游戏Resource limits资源限制标准方法:深度有限搜索Use CUTOFF-TEST(截断测试)instead of
10、 TERMINAL-TEST（终止测试）e.g.,depth limit(perhaps add quiescence search 静态搜索)Use EVAL instead of UTILITY用可以估计棋局效用值的启发式评价函数EVAL取代效用函数i.e.,估计位置期望值的评价函数假设我们有100 seconds计算时间,探索速度为104 nodes/second106 nodes per move 358/2 reaches depth 8 pretty good chess program4-ply lookahead is a hopeless chess player!4-ply
11、 human novice 8-ply typical PC,human master 12-ply Deep Blue,Kasparov评价函数 评价非终止状态的函数 理想函数:返回每个位置的效用值 在实践中:加权线性函数:Eval(s)=w1f1(s)+w2f2(s)+wnfn(s)e.g.,for chess,w1=9 withf1(s)=(number of white queens)-(number of black queens),etc.More on 评价函数 评价函数评估当前局面配置的好坏一个线性的评价函数是关于特征f1,f2,f3的加权和 More important fe
12、atures get more weight 对弈的质量直接依赖于评价函数的质量 为了构建一个好的评价函数，必须:利用行业知识提取好的特征 选择或学习更好的权重题外话:精确的评价函数并不重要Behavior is preserved under any monotonic（单调的）transformation of EVAL对待有限的时间 在实际游戏中，通常对每一步有时间限制T 我们如何考虑这个问题?所以，我们可以设置一个保守的深度有限，以保证在T时间内决定一次行动但是，搜索可能提前结束，更多搜索的机会被浪费了对待有限的时间 在实践中,迭代深入深度优先搜索(IDS)被很好地使用 运行alpha
13、-beta search 以深度限制逐渐增加的方式 当时间T快运行完时，返回最后一次完整的 搜索的结果(i.e.,the deepest search that was completed)现今一些确定性的游戏Chess(国际象棋）:Deep Blue defeated human world champion Gary Kasparov in a six-game match in 1997.Deep Blue searches 200 million positions per second,uses very sophisticated evaluation,and undisclose
14、d methods for extending some lines of search up to 40 ply（层、厚度）.计算机能够预见它的决策中的长期棋局序列。机器拒绝走一步有决定性短期优势的棋显示了非常类似于人类的对危险的感觉。Kasparov Kasparov lost the match 2 wins to 3 wins and 1 tie Deep Blue played by“brute force”(i.e.,raw power from computer speed and memory);it used relatively little that is similar
15、 to human intuition and cleverness Used minimax,alpha-beta,sophisticated heuristics现今一些确定性的游戏Checkers（西洋跳棋）:Chinook,the World Man-Machine Checkers Champion.Chinook ended 40-year-reign of human world champion Marion Tinsley in 1994.In 2007,checkers was solved:perfect play leads to a draw.Chinook cann
16、ot ever lose使用了一个提前计算好的存有443,748,401,247个不多于8个棋子的棋局数据库，使它的残局(endgame)走棋没有缺陷50 machines working in parallel on the problem现今一些确定性的游戏黑白棋:人类冠军已经拒绝同计算机比赛了Go（围棋）:2016年以前，人类冠军拒绝与计算机比赛，因为计算机是个小学生棋手。In go,b 300（棋盘为 19x19）,所以大多数程序使用基于模式识别的方法来提供一个貌似可行的解。Go has became a new benchmark for Artificial Intelligenc
17、e(人工智能新的试金石)AlphaGo:第一次打败人类in 19x19 Go Google DeepMind computer go player deep neural networks深度神经网络:value networks价值网络:to evaluate board positions policy networks策略网络:to select moves trained by supervised learning监督学习 reinforcement learning（强化学习）by self-play search algorithm Monte-Carlo simulation+
18、value/policy networksAlphaGo:Background 减少搜索空间:减少搜索深度 position evaluation 减少搜索分枝 move sampling based on policy policy=probability distribution p(a|s)Deep Neural Networks in AlphaGoAlphaGo uses two types of neural networks:policy network:what is the next move?learned from human expert moves value net
19、work:what is the value of a state?learned from self-play using a policy networkSL=supervised learning,RL=reinforcement learning包含几率因素的游戏 西洋双陆棋非确定性游戏概述在非确定性的游戏中,几率因素是由掷骰子，抽牌等引起的。抛硬币游戏的简化示例:非确定性游戏概述 权重取决于事件发生的概率 将极小极大值推广为期望极小极大值 Choose move with highestexpected value期望效用最大化 为什么我们要计算平均效用值?为什么不计算极小极大值?期
20、望效用最大化原则:一个智能体基于其给定的知识库，会根据期望效用最大化来选择行动方式 决策的一般性原则 经常作为理性的定义 我们会在本课程中反复看到该观点!期望极小极大值算法EXPECTIMINIMAX 类似于MINIMAX，多考虑一个几率节点if state is a Max node thenreturn the highest EXPECTIMINIMAX-VALUE of SUCCESSORS(state)if state is a Min node thenreturn the lowest EXPECTIMINIMAX-VALUE of SUCCESSORS(state)if sta
21、te is a chance node thenreturn average of EXPECTIMINIMAX-VALUE of SUCCESSORS(state)随机的Two-Player 掷骰子增加分枝b:两个骰子有21种可能的掷法 西洋双陆棋 20种合法行动 Depth 4=20 x(21 x 20)3=1.2 x 109 当深度增加时，到达指定节点的概率会收窄 此时再向前搜索的价值会减少 所以限定搜索深度是OK的 但是剪枝不太可能实现 TDGammon uses depth-2 search+verygood eval function+reinforcementlearning:w
22、orld-champion level play题外话：精确的评价函数的重要性Behaviour is preserved only by positive linear transformation of EVALHence EVAL should be proportional to the expected payoff评价函数应该是棋局的期望效用值的正线性变换本章大纲 博弈 博弈中的优化决策 极小极大值算法-剪枝 资源限制和近似评估 包含几率因素的游戏 不完整信息的游戏不完整信息的游戏E.g.,card games,where opponents initial cards are u
23、nknownTypically we can calculate a probability for each possible dealSeems just like having one big dice roll at the beginning of theGameIdea:compute the minimax value of each action in each deal,then choose the action with highest expected value over allDeals在评价一个有未知牌的给定行动过程时，首先计算出每副可能牌的出牌行动的极小极大值，
24、然后再用每副牌的概率来计算得到对所有发牌情况的期望值。ExampleExampleExample合理的分析*所以从直觉上说用所有可能状态的平均效用值来评价一次行动的价值is WRONG在局部观察中,一个行动的价值取决于信度状态这样可以在信度状态中生成和搜索博弈树以下行为可以帮助生成信度状态：打出一张牌来刺探对手给合伙人发信号靠演技来最小化信息披露Summary Games are fun to work on!perfection is unattainable must approximate Games are to AI as grand prix racing is to automo
25、bile design Game playing is best modeled as a search problem Search trees for games represent alternate computer/opponent moves Evaluation functions estimate the quality of a given board configuration for each player Minimax is an algorithm that chooses“optimal”moves by assuming that the opponent al
26、ways chooses their best move Alpha-beta is an algorithm that can avoid large parts of the search tree,thus enabling the search to go deeper 消除无关的子树以提高效率Summary of Search Uninformed search strategiesBreadth-first search(BFS),Uniform cost search,Depth-first search(DFS),Depth-limited search,Iterative d
27、eepening search Informed search strategies Best-first search:greedy,A*Local search:hill climbing,simulated annealing etc.Constraint satisfaction problems Backtracking=depth-first search with one variable assigned per node Enhanced with:Variable ordering and value selection heuristics,forwardchecking,constraint propagation作业 6.1，6.3，6.5
