第3个专题(2)-博弈搜索ppt课件.ppt

《第3个专题(2)-博弈搜索ppt课件.ppt》由会员分享，可在线阅读，更多相关《第3个专题(2)-博弈搜索ppt课件.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、状态空间搜索和回溯技术的例子二、博弈搜索第第3 3个专题（个专题（2 2）：）：搜索技术（博弈搜索）搜索技术（博弈搜索）MIN 7 (1)MIN 7 (1)MIN 7 (1)MIN 7 (1)MAX 6-1 (1)5-2 (1)4-3(1)MAX 6-1 (1)5-2 (1)4-3(1)MAX 6-1 (1)5-2 (1)4-3(1)MAX 6-1 (1)5-2 (1)4-3(1)MIN 5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(1)MIN 5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(1)MIN 5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(

2、1)MIN 5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(1)MAX 4-1-1-1(0)3-2-1-1(1)2-2-2-1MAX 4-1-1-1(0)3-2-1-1(1)2-2-2-1MAX 4-1-1-1(0)3-2-1-1(1)2-2-2-1MAX 4-1-1-1(0)3-2-1-1(1)2-2-2-1（0 0 0 0）MIN 3-1-1-1-1(0)2-2-1-1-1 MIN 3-1-1-1-1(0)2-2-1-1-1 MIN 3-1-1-1-1(0)2-2-1-1-1 MIN 3-1-1-1-1(0)2-2-1-1-1（1 1 1 1）MAX 2-1-1-1-1-1 M

3、AX 2-1-1-1-1-1 MAX 2-1-1-1-1-1 MAX 2-1-1-1-1-1 （0 0 0 0）复习：状态空间表示法的构成复习：状态空间表示法的构成状态空间方法状态空间方法:是用来表示问题及其搜索的一种方法，以状态和算符为基础来表示和求解问题，其四要素如下：1.1.状态状态2.2.算符算符3.3.状态空间状态空间4.4.问题的解问题的解例子例子1.1.回溯策略回溯策略(皇后问题皇后问题)在一个44的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获 ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q

4、(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2

5、,4)(3.2)Q(1,2)Q(1,2)(2,4)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)Q(1,2)(2,4)(3,1)(4,3)例例2 2：修道士和野人过河问题：修道士和野人过河问题 问题描述问题描述：有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到和的右岸。约束条件约束条件：但该船每次只能装载2个人，在任何岸边野人的数目都

6、不能超过不能超过修道士的人数，否则修道士就会被野人吃掉。假设野人服从从任何一种过河安排，请问如何规划过河计划才能让所有人都安全地渡到河的右岸。第一步：定义问题状态的第一步：定义问题状态的描述形式描述形式。S=(N x,N y,C)，其 中N x表 示修修 道道 士士在 左 岸 的 实 际人 数；N y表 示 野 人 在 左岸 的 实 际 人 数，C来 指 示船是否在左岸。C=1表示在左岸，C=0表 示 不 在 左 岸。第二步：把所有的状态描第二步：把所有的状态描述出来（述出来（3232个状态）个状态）S0=(3,3,1)S1=(3,2,1)S1=(3,2,1)S2=(3,1,1)S2=(3,1

7、,1)S3=(3,0,1)S4=(3,3,0)S5=(3,2,0)S5=(3,2,0)S6=(3,1,0)S6=(3,1,0)S7=(3,0,0)S7=(3,0,0)S8=(2,3,1)S9=(2,2,1)S9=(2,2,1)S10=(2,1,1)S11=(2,0,1)S12=(2,3,0)S13=(2,2,0S13=(2,2,0)S14=(2,1,0)S15=(2,0,0)S16=(1,3,1)S17=(1,2,1)S18=(1,1,1S18=(1,1,1)S19=(1,0,1)S20=(1,3,0)S21=(1,2,0)S22=(1,1,0S22=(1,1,0)S23=(1,0,0)S24

8、=(0,3,1S24=(0,3,1)S25=(0,2,1S25=(0,2,1)S26=(0,1,1S26=(0,1,1)S27=(0,0,1)S28=(0,3,0)S29=(0,2,0S29=(0,2,0)S30=(0,1,0S30=(0,1,0)S31=(0,0,0)第三步：定义算符第三步：定义算符L(i,j)L(i,j)和和R(i,j)R(i,j)从左到右：L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)从右到做：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2)第第四四步：步：状状态态空空间间搜搜索索图图二、博弈搜索二、博弈搜索博博 弈弈：被认为被认

9、为高智能行为游戏高智能行为游戏;不断为不断为AI研究提出新课题，推动研究提出新课题，推动AI研究的发展。研究的发展。基于基于博弈搜索博弈搜索的搜索策略的搜索策略n 博弈问题及博弈树概念博弈问题及博弈树概念n 博弈搜索控制策略博弈搜索控制策略n 博弈搜索算法及其应用实例博弈搜索算法及其应用实例n 博弈搜索优化博弈搜索优化-剪枝剪枝 博弈问题博弈问题及博弈树概念及博弈树概念n 博弈问题：博弈问题：对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算盘，还需充分考虑对方的应付策略，（盘，还需充分考虑对方的应付策略，（一字棋、国际象棋、一字棋、国际象

10、棋、打扑克、中国象棋、围棋打扑克、中国象棋、围棋）。）。双人完备信息：双人完备信息：对垒的双方轮流走步，对垒的双方轮流走步，对弈对弈的条件和走步规则完全相同。每的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步，而且还能估计出对方一方不仅知道对方已走过的所有棋步，而且还能估计出对方未来可能走的棋步。未来可能走的棋步。博弈问题博弈问题及博弈树概念及博弈树概念n 博弈问题描述：博弈问题描述：w 棋局描述；棋局描述；w 棋局走步规则。棋局走步规则。博弈搜索过程：博弈搜索过程：搜索棋局走步规则，隐含搜索棋局走步规则，隐含生成一棵生成一棵特殊特殊的的与或树与或树博弈问题求解：博弈问题求解：博弈

11、问题及博弈问题及博弈树博弈树概念概念与或节点与或节点分层交替出现分层交替出现的的与或树与或树从甲的立场出发从甲的立场出发或节点或节点与节点与节点或节点或节点完全取胜解完全取胜解 图图甲走步甲走步博弈问题及博弈问题及博弈树博弈树概念概念n判断走步的判断走步的极小极小-极大原则极大原则：v 考虑对方走步时（考虑对方走步时（与与节点）节点）：假定对手不会犯错假定对手不会犯错误，他总是选择对自己最有利，对我方最不利的误，他总是选择对自己最有利，对我方最不利的棋步走。因此，我方不能采取任何冒险行动棋步走。因此，我方不能采取任何冒险行动,视对视对手将走出的棋局为手将走出的棋局为极小值极小值；v考虑我方走步

12、时（考虑我方走步时（或或节点）节点）：应在对方造成的应在对方造成的最坏的局势中尽可能地选择最好的棋着走，视自己最坏的局势中尽可能地选择最好的棋着走，视自己可能走出的棋局为可能走出的棋局为极大值极大值。基于博弈搜索的搜索策略基于博弈搜索的搜索策略n 博弈问题及博弈树博弈问题及博弈树n 博弈搜索控制策略博弈搜索控制策略n 博弈搜索算法及其应用实例博弈搜索算法及其应用实例n 博弈树的博弈树的 -剪枝剪枝 w 完整的博弈搜索策略完整的博弈搜索策略（盲目搜索策略）（盲目搜索策略）w 有界深度博弈搜索策略完整的完整的博弈搜索策略博弈搜索策略n核心思想：核心思想：从博弈的从博弈的初始格局初始格局开始，轮番考

13、虑自己与对方可开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的达到分出胜负输赢的终止格局终止格局为止，此搜索过为止，此搜索过程程产生的一棵产生的一棵完整的博弈树完整的博弈树。完整的完整的博弈搜索策略博弈搜索策略n博弈问题实例博弈问题实例：有一堆数目为有一堆数目为N N的钱币，甲、乙二人轮流分堆。要求每人每次挑选的钱币，甲、乙二人轮流分堆。要求每人每次挑选其中某一堆钱币，将其分成数目不等的两小堆。分堆过程持续，其中某一堆钱币，将其分成数目不等的两小堆。分堆过程持续，直至其中一人无法再将任一堆钱币分成数目不等的两堆时，则直

14、至其中一人无法再将任一堆钱币分成数目不等的两堆时，则认输。认输。博弈问题描述：博弈问题描述：分堆格局分堆格局(状态状态):(x1,x2,(x1,x2,xn,Mxn,M),),其中，xi:xi:第第 i i 堆钱币的个数；堆钱币的个数；M:M:当前走步人编号当前走步人编号 -（MAX,MINMAX,MIN）走步规则：走步规则：IF IF (x1,x2,xn,M)(x1,x2,xn,M)(xi=Y+Z)(xi=Y+Z)(Y ZY Z)THEN THEN(x1,x2,xi-1,(x1,x2,xi-1,Y,Z,Y,Z,xi+1,xn,xi+1,xn,M)M)完整的完整的博弈搜索策略博弈搜索策略站在站在

15、MAX立场立场与节点与节点或节点或节点与节点与节点完全取胜的完完全取胜的完备策略备策略n特点：特点：w 搜索策略简单，易于控制，搜索策略简单，易于控制，可用于可用于简单的博弈简单的博弈或一个复杂或一个复杂博弈的博弈的残局残局；完整的完整的博弈搜索策略博弈搜索策略w不适合不适合复杂的博弈问题搜索复杂的博弈问题搜索 -指数爆炸指数爆炸。例，中国象棋：中国象棋：设每种格局有设每种格局有40种走法，一盘棋双方平均走种走法，一盘棋双方平均走50步，步，完整的博弈搜索完整的博弈搜索-搜索节点数（搜索节点数（402）50 10160，搜索深度达，搜索深度达100层。层。有必要引入有必要引入有界深度博弈搜索策

16、略有界深度博弈搜索策略。基于博弈搜索的搜索策略基于博弈搜索的搜索策略n 博弈问题及博弈树博弈问题及博弈树n 博弈搜索控制策略博弈搜索控制策略w 完整的博弈搜索策略（盲目搜索策略）（盲目搜索策略）w 有界深度博弈搜索策略有界深度博弈搜索策略（启发式搜索策略）（启发式搜索策略）有界深度搜索策略有界深度搜索策略n 核心思想：核心思想：根据对方已走出的棋步，构造出具有一定深度的博根据对方已走出的棋步，构造出具有一定深度的博弈树，并从此局部博弈树中弈树，并从此局部博弈树中选择选择相对好相对好的的棋着棋着走走。需解决的需解决的关键问题：关键问题：定义定义估计估计终结棋局终结棋局优劣优劣的评价函数；的评价函

17、数；给出给出棋局棋局优劣性优劣性传递的传递的计算方法。计算方法。定义定义棋局的棋局的评价函数评价函数设设 P P 为为有界博弈树有界博弈树中棋局；中棋局；(P)(P):棋局优劣的评价函数。棋局优劣的评价函数。例例1 1：从当前棋局到离我方最后取胜的差距：从当前棋局到离我方最后取胜的差距：胜利在望胜利在望 (P)(P)值较大，值较大，败局显露败局显露 (P)(P)值较小；值较小；例例2 2：从当前棋局到到某个明显有利于我方棋局的差距：从当前棋局到到某个明显有利于我方棋局的差距：吃掉对方一子吃掉对方一子,或者或者 “叫吃叫吃”。v (P)(P)MAXMAX赢赢 =(P)(P)MINMIN输输 =+

18、=+v (P)(P)MAXMAX输输 =(P)(P)MINMIN赢赢 =-=-v (P)(P)平平 =0=0v (P)(P)任一终叶棋局优劣的评价函数的任一终叶棋局优劣的评价函数的定义原则：定义原则：计算计算棋局的棋局的评价函数评价函数有界博弈树中任一棋局（节点）有界博弈树中任一棋局（节点）评价函数评价函数值的值的计算计算：w 对于对于终叶节点终叶节点：赋赋静态评价函数值静态评价函数值(P);(P);w 对于对于非终叶节点非终叶节点：按按极小极小-极大走步原则极大走步原则，采用，采用倒推的方法，倒推的方法，自下而上自下而上地由子节点地由子节点计算计算父节点的父节点的动态动态评价函数值评价函数值

19、(P)(P)。站在站在MAX立场立场基于基于极小极小-极大原则极大原则的的评价评价函数函数计算实例计算实例静态静态启发式启发式评价函数值评价函数值动态动态评价函评价函数值数值基于博弈搜索的搜索策略基于博弈搜索的搜索策略n 博弈问题及博弈树博弈问题及博弈树n 博弈搜索控制策略博弈搜索控制策略n 有界深度搜索算法及其应用实例有界深度搜索算法及其应用实例n 博弈树的博弈树的 -剪枝剪枝有界深度搜索有界深度搜索算法算法及其应用实例及其应用实例 针对针对当前当前对方对方给出的棋局给出的棋局 s：1、按宽度优先法按宽度优先法自上而下地自上而下地生成生成规定深度规定深度的博弈树；的博弈树；2、为有界深度博弈

20、树的所有、为有界深度博弈树的所有叶节点叶节点赋赋静态评价函数估计值静态评价函数估计值 3、根据、根据极小极小-极大走步原则极大走步原则自下而上地自下而上地逐级逐级计算各计算各非终叶节非终叶节点点的的动态动态评价函数估计值，评价函数估计值，直至求到起始节点的直至求到起始节点的评价函数值评价函数值(s)为止。为止。比较我方可走的各棋局的比较我方可走的各棋局的评价函数估计值，评价函数估计值，从中选择从中选择最好最好的棋的棋步走。步走。再根据对方走出的棋局再根据对方走出的棋局 s，重复上述过程。重复上述过程。有界深度搜索算法及其有界深度搜索算法及其应用实例应用实例一字棋一字棋（站在（站在MAXMAX的

21、立场）的立场）定义特殊棋局估计函数定义特殊棋局估计函数h1(P)h1(P)v h1(P)h1(P)MAXMAX赢赢 =+=+v h1(P)h1(P)MAXMAX输输 =-=-v h1 h1(P)(P)平平 =h1(P)MAX赢=+h1(P)MAX输=-h1(P)平=有界深度搜索算法及其有界深度搜索算法及其应用实例应用实例n一字棋一字棋（站在（站在MAXMAX的立场）的立场）n定义棋局评价函数：定义棋局评价函数：将整行、整列或整条对角线称为将整行、整列或整条对角线称为赢线赢线。如。如果一条赢线上只有（）方的果一条赢线上只有（）方的棋子或为空，而没有（）方棋子或为空，而没有（）方的棋子，则称此赢线

22、称为的棋子，则称此赢线称为（）方的赢线）方的赢线。设设方方任意棋局的任意棋局的静态评价函数静态评价函数 h1(P)h1(P)：w(P)=(P)=的赢线数的赢线数的赢线数的赢线数h(p)MAX=6 4=2h(p)M=4 6=-2v MAXMAX走棋第一步走棋第一步(深度为深度为2 2)：MAXMAX走步走步有界深度搜索算法及其有界深度搜索算法及其应用实例应用实例有界深度搜索算法及其有界深度搜索算法及其应用实例应用实例v MAXMAX走棋第二步：走棋第二步：v MAXMAX走棋第三步：走棋第三步：MAX走步走步MAX走步走步极大极小值算法说明n递归算法按照定义计算每个后继节点的极大极小值/搜索是从

23、目标到初始节点的反向推导n算法对博弈树实行了深度优先搜索n如果博弈树的最大深度为m，每个节点的合法招数为b，则w算法的时间复杂度是O(bm)w每次生成全部后继节点的空间复杂度是O(bm)w每次只生成一个后继节点的空间复杂度是O(m)极大极小值算法Function MAX-MIN-DECISION(state)returns an actioninputs:state(current state in game)v MAX-VALUE(state)return the action in SUCCESSORS(state)with value vFunction MAX-VALUE(state)

24、returns a utility valueif TERMINAL-TEST(state)then return UTILITY(state)v-for a,s in SUCCESSORS(state)do v MAX(v,MIN-VALUE(s)return v(a=action招数)Function MIN-VALUE(state)returns a utility valueif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)do v MIN(v,MAX-VALUE(s)retur

25、n v基于博弈搜索的搜索策略基于博弈搜索的搜索策略问题：问题：启发式博弈搜索策略启发式博弈搜索策略-将将扩展生成扩展生成博弈树的过程与博弈树的过程与计算、评价计算、评价及确定最优走步及确定最优走步的过程完全分开进行，导致了搜索效率的低下。的过程完全分开进行，导致了搜索效率的低下。对策：对策：-剪枝技术剪枝技术-在在生成生成博弈树博弈树同时同时计算和评价计算和评价棋局节点，对棋局节点，对不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算工作量，提高搜索效率。工作量，提高搜索效率。基于博弈搜索的搜索策略基于博弈搜索的搜索策略n 博弈

26、问题及博弈树概念博弈问题及博弈树概念n 博弈搜索控制策略博弈搜索控制策略n 博弈搜索算法及其应用实例博弈搜索算法及其应用实例n 博弈搜索优化博弈搜索优化-剪枝剪枝 博弈树的博弈树的 -剪枝剪枝h(3)17h(3)25nn1n1博弈树的博弈树的 -剪枝剪枝n 值：值：w 设博弈树中某节点设博弈树中某节点 n n 属于极大层。它左边第属于极大层。它左边第一个子节点一个子节点 n1n1的评价函的评价函数值数值 h(n1)h(n1)可视为节点可视为节点 n n 的的下界值下界值，或称为，或称为 值值，节点，节点 n n 的评价函数的评价函数值值 h h(n)(n)决不会小于此决不会小于此 值值。n n

27、 的的值值nn1n1博弈树的博弈树的 -剪枝剪枝 值：值：u 设博弈树中某节点设博弈树中某节点 n n 属于极小层。它左边第一属于极小层。它左边第一个子节点个子节点 n1n1的评价函数的评价函数值值 h(n1)h(n1)可视为节点可视为节点 n n 的的上界值上界值，或称为，或称为 值值，节点节点 n n 的的 h(nh(n)决不会大决不会大于此于此 值。值。n n 的的 值值m博弈树的博弈树的 -剪枝剪枝n 剪枝：剪枝：w 若任一极小层节点若任一极小层节点 m m 的的 值值小于或等于小于或等于其其位于极大层的位于极大层的父节点父节点的的 值值，即，即 ，则可终止该极小，则可终止该极小层中节

28、点层中节点 m m 以下的搜以下的搜索过程。索过程。值值 值值m博弈树的博弈树的 -剪枝剪枝 值值 值值 剪枝：剪枝：u 若任一极大层节点若任一极大层节点 m m 的的 值值大于或等于大于或等于其位于极小层的其位于极小层的父节点父节点的的 值值，即，即 ，则可终止该极大层中则可终止该极大层中节点节点 m m 以下的搜索过以下的搜索过程。程。-剪枝算法(1)n在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断Function ALPHA-BETA-SEARCH(state)returns an actioninputs:state(current state in game)v M

29、AX-VALUE(state,-,+)return the action in SUCCESSORS(state)with value v-剪枝算法(2)Function MAX-VALUE(state,)returns a utility valueinputs:state ,the value of the best alternative for MAX along the path to state ,the value of the best alternative for MIN along the path to stateif TERMINAL-TEST(state)then

30、return UTILITY(state)v-for a,s in SUCCESSORS(state)dov MAX(v,MIN-VALUE(s,)if v then return v MAX(,v)return v-剪枝算法(3)Function MIN-VALUE(state,)returns a utility valueinputs:state,the value of the best alternative for MAX along the path to state the value of the best alternative for MIN along the path

31、 to stateif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)dov MIN(v,MAX-VALUE(s,)if v then return v MIN(,v)return v-剪枝算法的说明n-剪枝可以应用树的任何深度，许多情况下可以剪掉整个子树/其原则是如果在节点n的父节点或者更上层的节点有一个更好的选择m，则在实际游戏(搜索)中永远不会到达nw=到目前为止在路径上任意点发现的MAX最佳选择w=到目前为止在路径上任意点发现的MIN最佳选择w-搜索不断更新/值，当某个节点的值分别

32、比/值更差时剪掉该节点的剩余分支-剪枝的效率n-剪枝的效率很大程度上取决于检查后继节点的次序应该先检查那些可能最好的后继n如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数/极大极小值算法为O(bd)有效分支因子b到b的平方根效率大大提高进一步研究技术：进一步研究技术：n博弈子树改变排列顺序时，博弈子树改变排列顺序时，-剪枝可能无计可施。剪枝可能无计可施。n 对弈双方不大可能使用同一个棋局估计函数。对弈双方不大可能使用同一个棋局估计函数。n 静态评价函数并非绝对可靠。一旦某个节点发生误差，由于静态评价函数并非绝对可靠。一旦某个节点发生误差，由于无法动态调整误差

33、，则此误差将会通过无法动态调整误差，则此误差将会通过极大极大-极小计算原则极小计算原则向向上传播，导致决策的失误。上传播，导致决策的失误。n 在有界深度搜索的全过程中，将深度固定不尽合理。有时暂在有界深度搜索的全过程中，将深度固定不尽合理。有时暂时的局部的放弃可能导致全面的重大胜利。时的局部的放弃可能导致全面的重大胜利。n 呆板的自下而上的计算估计值方法，难于体现对弈弈手的灵活呆板的自下而上的计算估计值方法，难于体现对弈弈手的灵活的作战意图，如声东击西、诱敌深入等。的作战意图，如声东击西、诱敌深入等。作作 业业博弈搜索作业：博弈搜索作业：n设局部博弈树如图所示，其中，设局部博弈树如图所示，其中，方格表示方格表示或或节点属极大层，节点属极大层，圆圈表示圆圈表示与与节点属极小层，节点属极小层，叶节点下面的数字为静态评价函叶节点下面的数字为静态评价函数值数值 h h，请在图上标出：，请在图上标出：.对博弈树进行的必要的对博弈树进行的必要的或或剪枝（要求标出剪去的分枝以剪枝（要求标出剪去的分枝以及剪枝采用的技术类型）；及剪枝采用的技术类型）；.按极小极大原则计算的非叶按极小极大原则计算的非叶节点的函数估计值；节点的函数估计值；3.3.确定确定1 1最终走出的棋步。最终走出的棋步。1234567101189302173 89143