2023年7月29日发(作者：)

⼈⼯智能基础复习2——问题求解03 Problem solving search很多AI任务都可以形式化为搜索问题：寻找路径、过河问题、解谜题（魔⽅、数码问题）、酒壶分⽔Outline问题求解智能体：基于⽬标Agent问题形式化问题实例基本搜索算法问题求解Agentfunction SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action static:seq, an action sequence, initially empty state, some description of the current world state goal, a goal, initially null problem, a problem formulation state ← UPDATE-STATE(state,percept) if seq is empty then do

goal ← FORMULATE-GOAL(state) problem ← FORMULATE-PROBLEM(state, goal) seq ← SEARCH(problem) action ← FIRST(seq) seq ← REST(seq) return action

这是离线问题，在求解问题时是闭眼执⾏的，⽽联机问题在解决问题时不需要完整的知识搜索问题搜索问题包括：状态空间、后继函数、开始状态和⽬标测试问题的解是从初始状态到⽬标状态的⼀组⾏动序列搜索树：计划和结果的“what if"树；开始状态对应根结点；孩⼦结点对应后继函数；结点标记为状态，分别对应这些状态的计划；对⼤多数问题不可能建⽴整个树状态空间图：每个状态是⼀个结点，每个后继是⼀条发出的边实例：罗马尼亚问题构造⽬标：在Bucharest构造问题：状态：各个城市；⾏为：驾驶往返于各个城市寻找问题的解：城市序列，如Arad，SIbiu，Fagaras，Bucharest单状态问题形式化：初始状态，如“at Arad”⾏动或后继函数，S(x)=set of action-state pairs，如S(Arad) = { ,... }⽬标测试：明确的，如x = "at Bucharest"，隐含的，如Checkmate(x)路径损耗：如距离，⾏动执⾏的次数等，c(x,a,y)>=0问题的解是⼀组从初始状态到⽬标状态的⾏动序列选择⼀个状态空间真实世界中状态空间必须抽象化（抽象）状态=真实状态的集合（抽象）⾏动=真实⾏动的复杂组合（抽象）解=真实世界解决⽅案的真实路径集合每个抽象动作都应该⽐原问题更简单例⼦：吸尘器状态空间图状态：地板是否脏、机器⼈的位置⾏动：Left, Right, Suck, NoOp⽬标测试：没有灰尘路径损耗：每次⾏动消耗1,NoOp则消耗0例⼦：8数码状态：数码块的位置⾏动：move blank left, right, up, down⽬标测试：给定的数码块位置状态路径损耗：每次⾏动消耗1注意：求解n数码问题的最优解是NP完全的基本搜索算法Tree search algorithms——搜索树function Tree-Search(problem, strategy) returns a solution, or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy(根据不同策略选择扩展节点) if the node contains a goal then return the corresponding solution else expand the node and add the resuling nodes to the search tree end实现：状态 vs. 节点状态是物理配置的⼀种表现形式⼀个节点是⼀个数据结构构成的搜索树的⼀部分，包括状态、⽗节点、⾏动、路径成本g(n)、深度实现：⽣成树搜索function TREE-SEARCH(problem, fringe) returns a solution, or failure fringe ← INSERT(MAKE-NODE(INITIAL-STATE[problem],fringe) loop do if fringe is empty then return failure node ← REMOVE-FRONT(finge) if GOAL-TEST[problem](STATE[node]) then return SOLUTION(node) fringe ← INSERTALL(EXPAND(node, problem), fringe)function EXPAND(node, problem) returns a set of nodes successors ← the empty set for each action, result in SUCCESSOR-FN[problem](STATE[node]) do s ← a new NODE PARENT-NODE[s] ← node; ACTION[s] ← action; STATE[s] ← result PATH-COST[s] ← PATH-COST[node] + STEP-COST(node,action,s) DEPTH[s] ← DEPTH[node] + 1 add s to successors return successors搜索策略：节点扩展顺序的选取性能评价：完备性、时间复杂度、空间复杂度、最优性衡量时间和空间复杂度相关的项：分⽀因⼦b、最浅的⽬标节点的深度d、最⼤深度m⽆信息搜索策略：只利⽤问题定义中提供的状态信息⼴度优先搜索、⼀致代价搜索、深度优先搜索、深度受限搜索、迭代加深的深度优先搜索1.⼴度优先搜索：扩展未扩展过的最浅节点，将边缘组织成FIFO队列实现，新的厚积节点加⼊到队列尾完备性？是的（若d有限）时间？1+b+b^2+b^3+...+b^d+b(b^d-1) = O(b^(d+1))，即d的指数空间？O(b^(d+1))（保存所有节点在内存中）最优？是的（若每步的路径损耗为1），通常情况下不是最优的空间代价是最⼤的问题，⽣成节点的速度可达100MB/sec，24hrs = 8640GB2.⼀致代价搜索：扩展代价最⼩的未扩展的节点，边缘组织成按路径损耗排序的队列实现，若单步代价均相等则等价于⼴度优先搜索完备性？是的，若单步代价>=ε时间？空间？ C*为最优解的代价，对于g<=C*，O(b^(ceiling(C*/ε)))最优？是的，节点根据g(n)的递增顺序扩展3.深度优先搜索：扩展深度最深的未扩展过的节点，边缘=LIFO队列，后继结点放在队列前完备性？否，只在有限状态空间中完备时间？O(b^m)，若m⽐d⼤很多，时间消耗更多，但若解是密集的，则⽐⼴度优先搜索更快空间？O(b^m)，即线性最优？否4.深度受限搜索：设置界限l，解决⽆限深度路径问题若ld，⾮最优递归实现5.迭代加深的深度优先搜索：每轮增加深度限制的深度受限搜索function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution inputs:problem, a problem for depth o to ∞ do

result DEPTH-LIMITED-SEARCH(problem, depth) if result ≠ cutoff then return result end

完备性？是的时间？(d+1)b^0 + db^1 + (d-1)b^2 + ... + b^d = O(b^d)空间？O(bd)最优？是的，若单步代价=1对于b=10,d=5，N(IDS)=50+400+3000+20000+100000=123450N(BFS)=10+100+1000+10000+100000+999990=1111100IDS表现更优，因为在深度为d的节点不需展开⽆信息搜索策略对⽐表格：见第三版课本P81重复状态：未检测到重复状态可能导致⼀个线性的问题变成⼀个指数的问题图搜索function GRAPH-SEARCH(problem,fringe) returns a solution, or failure closed ← an empty set fringe ← INSERT(MAKE-NODE(INITIAL-STATE[problem]),fringe) loop do if fringe is empty then return failure node ← REMOVE-FRONT(finge) if GOAL-TEST(problem, STATE[node]) then return node if STATE[node] is not in closed then add STATE[node] to closed fringe ← INSERTALL(EXPAND(node,problem),fringe) end04 Informed search⽆信息的搜索：除了问题中提供的定义之外没有任何关于状态的附加信息有信息的搜索：在问题本⾝的定义之外还可利⽤问题的特定知识Outline最佳优先搜索：贪婪最佳优先搜索、A*搜索启发式搜索局部搜索算法：爬⼭法搜索、模拟退⽕搜索、局部束搜索、遗传算法最佳优先搜索对每个结点利⽤评价函数f(n)，扩展最需要扩展的还未扩展过的节点实现：边缘是⼀个根据需求的降序进⾏排列的队列（优先级队列）特殊情况：贪婪搜索、A*搜索⼀致代价搜索策略是扩展最⼩路径成本优点：UCS完备且最优缺点：在每个⽅向上进⾏搜索、没有最优⽬标的信息最佳优先搜索策略是扩展离⽬标最近的节点启发函数：将状态映射到距离的函数⼀种普遍的情况是最佳优先搜索会使得直接找到错误的⽬标最坏情况是像badly-guided DFS贪婪搜索评价函数f(n)=h(n)=节点n到⽬标节点的最低耗散路径的耗散值估计值h(n)是特定问题的函数，若n是⽬标节点，则h(n)=0，如hSLD(n)为从n到Bucharest的直线距离贪婪搜索试图扩展离⽬标节点最近的点完备性？否，可能导致死循环，在有限空间中进⾏重复性检查可构成完备性时间？O(b^m)，如果有⼀个好的启发式函数，复杂度可以有效降低空间？O(b^m)，保存所有节点在内存中最优？否UCS与贪婪算法结合：Uniform-cost按路径代价g(n)排序，Greedy-search按⽬标距离h(n)排序A*按两者的和f(n)=g(n)+h(n)排序A*搜索评价函数：f(n)=g(n)+h(n)g(n)：到达节点n的耗散h(n)：启发函数：从节点n到⽬标节点的最低耗散路径的耗散估计值f(n)：经过节点n的最低耗散的估计函数A*搜索使⽤可采纳启发式，即h(n)<=h*(n)，h*(n)是到n的实际代价，h(n)>=0如hSLD(n)从不会⾼估实际路径长对任⼀节点n，有h(n)<=h*(n)，则称h(n)是可采纳的可采纳启发式从不会过⾼估计到达⽬标的代价，即乐观的定理：如果h(n)是可采纳的，A*使⽤的TREE-SEARCH是最优的A*的最优性证明：略⼀致性启发函数：如果对于任⼀节点n，n'是n的后继，对于某⼀⾏动a，有h(n)<=c(n,a,n')+h(n')，则A*启发式是⼀致的若h是⼀致的，有f(n')=g(n')+h(n')=g(n)+c(n,a,n')+h(n')>=g(n)+h(n)=f(n)f(n)值沿任何路径都是⾮递减的定理：如果h(n)是⼀致的，则A*使⽤的GRAPH-SEARCH是最优的A*的最优性证明：略A*的性质：完备性？是的（除⾮f<=f(G)的节点是⽆穷的）时间？A*算法对于任何给定的启发函数都是效率最优的，但仍为指数级空间？保存所有节点在内存中最优？是的A*扩展所有f(n)C*的节点8数码问题——把棋⼦⽔平或者竖直地滑动到空格中，直到⽬标局⾯：平均解步数是22步，分⽀因⼦约为3到达深度为22的穷举搜索将考虑约3^22≈3.1×10^10状态个数O((n+1)!)，NP完全问题可采纳启发式函数：h1(n)=错位的棋⼦数，h2(n)=所有棋⼦到其⽬标位置的⽔平竖直距离和统治：若对于所有n，有h2(n)>=h1(n)，则称h2统治h1（dominate，统治、占优），h2更利于搜索h(n)=max(ha(n);hb(n))同样是可采纳的，且统治ha,hb使⽤f(n)=g(n)+h(n)搜索，h(n)=错放数字个数，g(n)=节点深度松弛：减少⾏动限制⼀个松弛问题的最优解的耗散是原问题的⼀个可采纳的启发式如果棋⼦可以任意移动，则h1给出最短的确切步数如果棋⼦可以移动到任意相邻的位置，则h2给出最短的确切步数松弛问题的最优解不⼤于实际问题的最优解构造松弛问题原问题：⼀个棋⼦可以从⽅格A移动到⽅格B，如果A与B⽔平或者垂直相邻⽽且B是空的松弛1：⼀个棋⼦可以从⽅格A移动到⽅格B，如果A与B相邻——h2松弛2：⼀个棋⼦可以从⽅格A移动到⽅格B，如果B是空的松弛3：⼀个棋⼦可以从⽅格A移动到⽅格B——h1如果有⼀个可采纳启发式的集合{h1,...,hm}，h(n)=max(h1(n),...,hm(n)}可采纳并⽐成员启发式更有优势评价函数f(n)h(n)——节点n到⽬标节点的最低耗散路径的耗散估计值g(n)——初始节点到这个节点的路径损耗的总和f(n)=g(n): Uniform Costf(n)=h(n): Greedyf(n)=g(n)+h(n): A*局部搜索算法对⼤规模问题，A*存在不⾜：状态空间太⼤、不能访问所有f值⼩于最优解的状态、不能存储整个边缘值解决办法：更好的启发式、贪婪爬⼭算法（fringe size = 1）、束搜索（limited fringe size）有限的内存选择：⽆⾜够的内存来存储整个边缘爬⼭搜索：只有最佳节点保持不变，⽆边缘，优先根据h选择后继（贪婪爬⼭）与贪婪回溯相⽐，后者仍旧拥有边缘束搜索（限制内存搜索）：在边缘保留K个节点、转储所需的最低优先节点、可以单独根据h来优先排序（贪婪束搜索）、h+g（限制内存的A*）状态空间=⼀系列完全状态局部搜索算法：保持单⼀的⼀个当前状态，尝试去改进它，直⾄⽆法变得更好常数空间，适合在线和离线搜索通常更有效（但不完备）例⼦：n皇后问题优化问题：爬⼭法搜索从任何地⽅开始总是选择最优的相邻值如果所有相邻值均未⽐当前值的得分⾼，则退出像健忘的⼈在⼤雾中试图登顶珠穆朗玛峰，不能⼀下⼦看到全局function HILL-CLIMBING(problem) returns a state that is a local maximum inputs:problem, a problem local variables: current, a node neighbor, a node current ← MAKE-NODE(INITIAL-STATE[problem]) loop do

neighbor ← a highest-valued successor of current if VALUE[neighbor] <= VALUE[current] then return STATE[current] current ← neighbor问题：依赖于初始状态，可能会陷⼊局部最⼤值的困境随机重启爬⼭法克服了局部极⼤值 极度完备，易实现（只要不太崎岖）随机侧移逃离⼭肩，极⼤循环随机重启爬⼭算法：1. When stuck, pick a random new starting state and re-run hill-climbing from there2. Repeat this k times3. Return the best of the k local optima模拟退⽕搜索：通过允许⼀些“坏”的移动，但逐渐降低它们的频率逃离局部最⼤值function SIMULATED-ANNEALING(problem, schedule) returns a solution state inputs: problem, a problem schedule, a mapping from time to "temperature" local variables: current, a node next, a node T, a "temperature" controlling prob. of downward steps current ← MAKE-NODE(INITIAL-STATE[problem]) for t ← 1 to ∞ do T ← schedule[t] if T=0 then return current next ← a randomly selected successor of current ΔE ← VALUE[next] - VALUE[current] if ΔE > 0 then current ← next else current ← net only with probability e^(ΔE/T)模拟退⽕搜索的性质：如果调度让T下降得⾜够慢，算法找到全局最优解的概率逼近于1⼴泛应⽤于VLSI布局、航空调度等Local Beam Search（局部剪枝搜索）记录k个状态，⽽不是1个，从k个随机⽣成的状态开始，每次迭代，全部k个状态的所有后继全部⽣成，如果有⽬标状态，停⽌，否则选择k个最佳后继，重复该过程问题：很多时候，所有k个状态最终停留在相同的局部最⼤值上遗传算法利⽤⾃然选择的隐喻，通过结合两个⽗状态⽣成后继状态从k个随机⽣成的状态开始（种群），⼀个状态被表⽰为⼀个有限长度字符串（0、1串）评价函数：适应度函数（fitness function），越好的状态值越⾼通过选择、杂交、变异产⽣下⼀代8皇后的遗传算法图解：见课本P111有信息/⽆信息搜索——主要思想好的启发式搜索能⼤⼤提⾼搜索性能但由于启发式搜索需要抽取与问题本⾝有关的特征信息，⽽这种特征信息的抽取有时会⽐较困难，因此盲⽬搜索仍不失为⼀种有⽤的搜索策略好的搜索策略应该：引起运动——避免原地踏步；系统——避免兜圈；运⽤启发函数——缓解组合爆炸搜索树 vs 搜索图搜索树：结点有重复，但登记过程简单搜索图：结点⽆重复，但登记过程复杂（每次都要查重），省空间，费时间05 CSPConstraint Satisfaction Problems 约束满⾜问题OutlineCSP实例CSP的回溯搜索问题结构和问题分解CSP局部搜索标准搜索问题：状态是⼀个⿊盒——任何可以由⽬标测试、评价函数、后继函数访问的数据结构CSP：状态由值域Di中的变量Xi定义；每个约束包括⼀些变量的⼦集，并指定这些⼦集的值之间允许进⾏的合并形式化表⽰⽅法的简单例⼦实例：地图着⾊问题变量：WA,NT,Q,NSW,V,SA,T值域：Di={red,green,blue}约束：相邻区域染上不同颜⾊解：满⾜所有约束的颜⾊分配约束图Binary CSP：每个约束和两个变量相关Constraint graph：节点是变量，弧是约束通⽤的CSP算法利⽤图结构来加速搜索，如Tasmania是独⽴的⼦问题CSP的种类离散变量：有限区域：n个变量，值域⼤⼩d → O(d^n)完全分配例如：Boolean CSPs, incl. Boolean satisfiability (NP-complete)⽆限值域（integers,strings,etc.），如作业调度需要⼀种约束语⾔线性约束可解，⾮线性不可判定连续变量：如：哈勃太空望远镜观测的开始、结束时间线性规划⽅法在多项式时间内是线性约束可解的约束的种类⼀元约束涉及单⼀变量，如 SA≠green⼆元约束涉及变量对，如SA≠WA⾼阶约束涉及3个或更多变量，如密码算数的列约束偏好约束（软约束），如红⾊⽐绿⾊更好；偏好约束通常被处理成个体变量赋值的耗散——约束优化问题（COP）例⼦：密码算数变量：F T U W R O X1 X2 X3值域：{0,1,2,3,4,5,6,7,8,9}约束：alldiff (F,T,U,W,R,O)O + O = R + 10．X1X1 + W + W = U + 10．X2X2 + T + T = O + 10．X3X3 = F , T ≠ 0, F ≠ 0真实世界的CSP指派问题：谁教授哪⼀节课、谁阅读哪篇⽂献时间安排问题：何时何地上什么课硬件布局、交通调度、⼯⼚调度、平⾯布置注意真实世界问题包含了实数值变量标准搜索的增量形式化初始状态：空，{}后继函数：分配⼀个值给未赋值的变量，并且新赋值与当前赋值不冲突（如果不存在合法赋值则失败）⽬标测试：当前分配是完备的这和所有的CSP是⼀样的，每个解在深度n出现n个变量，利⽤深度优先搜索由于路径是不相关的，所以可以使⽤完全状态形式化在深度l，b=(n-1)d，所以n!．d^n 个叶⼦

回溯搜索变量赋值具有可交换性，如[WA = red then NT = green] 等价于 [NT = green then WA = red]只需考虑对每个节点的单⼀变量的赋值：b = d 所以有d^n个叶节点在CSP中，对深度优先搜索的单⼀变量赋值称为回溯搜索回溯搜索是CSP中基本的⽆信息搜索算法可以解决规模为n≈25的n皇后问题function BACKTRACKING-SEARCH(csp) returns solution/failure return RECURSIVE-BACKTRACKING({},csp)function RECURSIVE-BACKTRACKING(assignment,csp) returns soln/failure if assignment is complete then return assignment var ← SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp) for each value in ORDER-DOMAIN-VALUES(var, assignment,csp) do if value is consistent with assignment given CONSTRAINTS[csp] then add {var = value} to assignment result ← RECURSIVE-BACKTRACKING(assignment,csp) if result ≠ failure then return result remove {var = value} from assignment return failure另⼀个回溯搜索例⼦：满⾜{┐a∨b，┐b∨c，┐c，┐a}的值枚举法：{a,b,c} = 1 1 1，1 1 0， 1 0 1， 1 0 0， 0 1 1， 0 1 0， 0 0 1， 0 0 0回溯法：{a,b,c} = 1 - -， 0 1 1， 0 1 0， 0 0 1， 0 0 0提⾼回溯法的效率通常的算法有很⼤的改善空间：1.下⼀次赋值应该对哪个变量进⾏？2.尝试的变量应该按照什么顺序？3.是否可以尽早地发现不可避免的失败？4.是否可以利⽤问题结构？1. Minimum remaining values 最⼩剩余值（MRV）：选择拥有最少合法值的变量约束最多的变量先开始，按照最快失败的顺序进⾏Degree heuristic 度启发式Tie-breaker among MRV variables度启发式：通过选择与其他未赋值变量约束最多的变量来试图降低未来的分⽀因⼦2. Least constraining value 最少约束值给定⼀个变量，选择最少约束值：优先选择的值是给邻居变量留下更多的选择；可能会需要更⼤的计算量Forward checking——前向检验思路：对剩下的未赋值的变量的合法值进⾏跟踪检查，如果发现任⼀变量不再拥有合法值则终⽌搜索算法3. Constraint propagation——约束传播前向检查从已赋值的变量向未赋值的变量传播信息，但是不对早期的失败提供早期的发现NT和SA不能都是蓝⾊（具体例⼦见课本P181）约束传播局部重复地实施约束Arc consistency——弧相容（定义见课本P174）使每条弧保持相容（consistent）的最简单的传播形式X → Y is consistent iff for every value x of X there is some allowed yif X loses a value, neighbors of X need to be rechecked弧相容⽐前向检验更早地发现失败，可以作为预处理器或在每次赋值之后进⾏弧形容算法AC-3：function AC-3(csp) returns the CSP, possibly with reduced domains inputs:csp, a binary CSP with variables {X1,X2,...,Xn} local variables:queue, a queue of arcs, initially all the arcs in csp while queue is not empty do (Xi,Xj) ← REMOVE-FIRST(queue) if REMOVE-INCONSISTENT-VALUES(Xi,Xj) then for each Xk in NEIGHBORS[Xi] do add (Xk,Xi) to queuefunction REMOVE-INCONSISTENT-VALUES(Xi,Xj) returns true iff succeeds removed ← false for each x in DOMAIN[Xi] do

if no value y in DOMAIN[Xj] allows (x,y) to satisfy the constraint Xi ↔ Xj then delete x from DOMAIN[Xi]; removed ← true return removed4.问题结构和问题分解对Tasmain着⾊和对mainland着⾊是两个独⽴的⼦问题，独⽴性可以通过在约束图中寻找连通域来确定假设每个⼦问题包含了n个变量中的c个变量，最坏情况下的⼯作量是n/c．d^c，是n的线性函数如：n=80，d=2，c=20，4*2^20树结构的CSP定理：如果约束图⽆环，则CSP可以在O(n*d^2)时间内解决；任何⼀个树状结构的CSP问题可以在变量个数的线性时间内求解与通常的CSP⽐较，后者的最坏时间为O(d^n)这个定理也可以⽤逻辑和概率性原因解释：在语法约束和推理复杂性之间的⼀个重要例⼦CSP的树结构算法1. 选择⼀个变量作为根节点，从根节点到叶⼦节点进⾏排序，使每个节点的⽗节点在该节点之前2. 对j从n到2,执⾏函数REMOVEINCONSISTENT(Parent(Xi),Xi)3. 对j从1到n，对Xi相容地赋值Parent(Xi)复杂度：O(n*d^2)近似树结构的CSP调整：实例化⼀个变量，删除其邻居节点的值域Cutset conditioning（割集调整）：实例化变量的⼀个集合，使剩余的约束图变成树割集⼤⼩c → 运⾏时间O(d^c(n-c)d^2)，对于很⼩的c速度很快寻找⼀个最⼩的割集是个NP问题CSP局部搜索爬⼭、模拟退⽕⼯作于完全状态化的形式化，即所有已赋值的变量应⽤于CSP：允许未满⾜约束的状态、操作对变量的值重新赋值变量选择：对任意冲突的变量进⾏随机选择最⼩冲突启发式变量选择：选择会造成与其他变量的冲突最⼩的值，如爬⼭h(n)=违背约束的总数例⼦：4皇后问题状态：4个皇后在棋盘的4列（4^4=256个状态）⾏动：在列⽅向上移动皇后⽬标测试：没有互相攻击的皇后评价：h(n)=互相攻击的对数最⼩冲突的性能评价给定随机初始状态，可以在常数时间内解决任意⼤概率n值的n皇后问题R=(number of constraints) / (number of variables)例⼦：3-SAT问题每个约束涉及3个变量。。。加速1：模拟退⽕思路：通过⼀些“坏”的⾏动来逃离局部最⼤值，但是逐渐降低它们的频率If 新状态⽐现有状态好，移动到新状态Else 以某个⼩于1的概率接受该移动，此概率随温度“T"降低⽽下降加速2：最⼩最⼤值优化Putweights on constraintsrepeat Primal search: update assignment to minimize weighted violation, until stuck Dual step: update weights to increase weighted violation, until unstuckuntil solution found, or bored06 GAME PLAYING博弈被认为是⼈⼯智能研究的⼀个很好的问题博弈是不平凡的- 玩家需要类似⼈类的智能

- 游戏可以很复杂(象棋、围棋等)

- 在有限的时间内需要作出决定

游戏通常是- 明确的和可重复的

- 充满可观察和有限的环境

可以直接⽐较⼈类和计算机

Outline- 游戏

- 最优策略

- 极⼩极⼤算法

- α-β剪枝

- 资源限制和近似评估

- 包含⼏率因素的游戏

- 不完全信息的游戏游戏 vs. 搜索问题- 不可预测的对⼿=>解决⽅案是对对⼿的每种可能的回应选择⼀种移动的策略

- 时间限制=>游戏对于低效率有严厉的惩罚游戏的种类

确定型的 随机的

完全信息 象棋跳棋围棋奥赛罗 西洋双陆棋

不完全信息 战列舰、盲的井棋 桥牌、扑克、拼字游戏核战争

博弈树(2个玩家、确定性、轮流)确定性、两⼈制

- ⼀字棋、象棋、跳棋

- 游戏搜索

- 状态空间搜索树

- 玩家轮流

- 每⼀层，包含⼀轮的移动

- 选择移动到效⽤值最⾼的位置

- 零和游戏

- ⼀个玩家最⼤化结果

- 另⼀个玩家最⼩化结果

极⼤极⼩原则

- 假设双边玩家均作最优选择

- 计算机假设在它移动之后，对⼿会选择最⼩值的移动

- 计算机选择的最佳移动考虑了它的移动以及对⼿的最优移动

极⼤极⼩值

- 对确定性、完全信息博弈的最优策略

- 策略：选择移动到具有最⾼的极⼤极⼩值的位置，在对⼿也使⽤最优策略的条件下，能导致⾄少不⽐其它策略差的结果。 - 假设两个游戏者都按照最优策略进⾏，那么节点的极⼩极⼤值就是对应状态的效⽤值(对于MAX)

- MAX优先选择有极⼤值的状态

- MIN优先选择有极⼩值的状态

- MINMAX-VALUE(n)=

UTILITY(n) 当n为终⽌状态

max MINMAX-VALUE(s) 当n为MAX节点

min MINMAX-VALUE(s) 当n为MIN节点

极⼤极⼩值算法

function MINIMAX-DECISION(state) returns an action inputs: state, current state in game return the a in ACTIONS(state) maximizing MIN-VALUE(RESULT(a,state))function MAX-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← -∞ for a, s in SUCCESSORS(state) do v ← MAX(v, MIN-VALUE(s)) return vfunction MIN-VALUE(state) returns a utility value if TERMINAL-TEST(state) then return UTILITY(state) v ← ∞ for a, s in SUCCESSORS(state) do v ← MIN(v,MAX-VALUE(s)) return v性质

- 完备性：仅当树是有限的(国际象棋有特定的规则)，在⼀个⽆限的树中甚⾄存在有限的策略

- 最优性：是的，对战⼀个最优策略的对⼿，不然呢

- 时间复杂度：O(b^m)

- 空间复杂度：O(bm) (深度优先搜索)

α-β剪枝

- 如果对战⼀个聪明的对⼿，博弈树的⼀些树枝不会被遍历到。

- 剪枝可以忽略⼀些树枝

- 为什么称为α-β

- α是到⽬前为⽌在路径上的任意选择点发现 的MAX的最佳(即最⼤值)选择，β的定义类似α-β算法function ALPHA-BETA-DECISION(state) returns an action

return the a in ACTIONS(state) maximizing MIN-VALUE(RESULT(a, state)function MAX-VALUE(state,α,β) returns a utility value inputs: state, current state in game α, 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 state if TERMINAL-TEST(state) then return UTILITY(state) u ← -∞ for a, s in SUCCESSORS(state) do

v ← MAX(v, MIN-VALUE(s,α,β)) if v ≥ β then return v α ← MAX(α,v) return vfunction MIN-VALUE(state,α，β) returns a utility value same as MAX-VALUE but with roles of α,β reversedα-β的效率

- 效果取决于后继的检查顺序，如果最优的后继最先被检查则效果更好。

- 最坏的情况：

- 顺序排列所以没有树枝被修剪

- 对穷举算法没有改进

- 最好的情况：

- 每个玩家的最优移动都被最先评价

- 在实践中，性能接近最佳，⽽不是最坏的

α-β的性质

- 剪枝不影响最后的结果

- 好的移动顺序提⾼了剪枝的效率

- 在好的移动顺序情况下，时间复杂度=O(b^(m/2))

资源限制

- 标准⽅法：有限深度搜索

- 利⽤截断测试代替终⽌测试

- 例如深度限制(可能增加静态搜索)

- 利⽤可以估计棋局效⽤值的启发式评价函数EVAL取代效⽤函数

- 即估计位置期望值的评价函数

评价函数

- 理想函数：返回位置的效⽤值

- 实际上：典型特征的线性加权和

Eval(s)=w_1f_1(s)+w_2f_2(s)+...+w_nf_n(s)

- 越重要的特征，加权值越⾼

- 确定性博弈的结果作为⼀个序数效⽤函数有限时间的解决

- 在实际游戏中，通常对每⼀步移动有个时间限制T

- 怎么考虑进去呢

- 不能中途停⽌α-β，有信⼼利⽤期望的结果

- 所以，我们可以设置⼀个保守的极限深度，保证我们会在⼩于T的时间内找到下⼀步

- 但是，搜索可能会提前停⽌，进⾏更多搜索的机会被浪费掉了

- 实际中，常⽤迭代加深搜索(IDS)

- 以逐渐增加的深度限制进⾏α-β搜索

- 当时间到时，使⽤最后⼀次完成的α-β搜索的策略(即已完成的最深的搜索)在实践中的确定性游戏

- 国际象棋：深蓝在1997年⼀场六局的⽐赛中打败⼈类世界冠军，深蓝每秒搜索2亿个位置，使⽤⾮常复杂的评估，并扩⼤到40层。

- 计算机能够预见它的决策中的长期棋局序列。机器拒绝⾛⼀步有决定性短期优势的棋—显⽰了⾮常类似⼈类的对危险的感觉。

- 西洋跳棋：Chinook，世界⼈机跳棋冠军

- Chinook在1994年结束了⼈类长达40年的世界冠军统治

- 2007年，跳棋得到解决，最佳算法最终导致平局

- Chinook不会输

- 使⽤了⼀个提前计算好的存有443，748，401，247个不多于8个棋⼦的棋局数据库，使它的残局⾛棋没有缺陷

- 奥赛罗：⼈类冠军拒绝对战强⼤的电脑

- Go，围棋：⼈类冠军拒绝对战弱⼩的计算机。在围棋中，b>300(棋盘为19×19)，所以⼤多数程序使⽤模式的知识基础，提出合理的动作。⼈⼯智能的试⾦⽯。

- AlphaGl：⾸次在19×19的棋盘上打败⼈类

- ⾕歌电脑棋⼿DeepMind

- 深度神经⽹络：

- 价值⽹络：评价板的位置

- 政策⽹络：选择移动

- 训练于：

- 有监督的学习

- 增强⾃我发挥学习 - 搜索算法

- 蒙特卡罗模拟+价值/政策⽹络

AlphaGo：背景

- 减少搜索空间

- 减少深度

- 位置评价

- 减少分⽀

- 基于政策的移动采样

- 政策=概率分布 p (a|s)

AlphaGo中的深度神经⽹络

- AlphaGo使⽤两种类型的神经⽹络

- 政策⽹络：下⼀步的⾏动是什么

- 从⼈类专家的⾏动学习

- 价值⽹络：状态的值是什么

- 利⽤政策⽹络从⾃我学习

- SL=监督学习，RL=强化状态不确定的游戏：西洋双陆棋

- 在不确定的游戏中，机会由骰⼦、洗牌决定，简化的例⼦⽤掷硬币表⽰。

- 最⼤期望效⽤

- 为什么对效⽤求平均，⽽不是极⼤极⼩值

- 最⼤期望效⽤原则：⼀个agent应该根据其知识选择期望效⽤最⼤化的⾏为

- 决策的⼀般原则

- 经常作为理性的定义不确定的游戏算法

- ......

if state is a chance node then

return average of EXPECTIMINIMAX-VALUE of SUCCESSORS(state)

随机的两个玩家

- TDGammon采⽤depth-2搜索+很好的eval函数+强化学习：世界冠军的⽔平

- 评价函数应该是棋局的期望效⽤值的正线性变换

不完全信息的游戏

- 例如，纸牌游戏，对⼿的初始牌未知，通常我们对每⼀次出牌计算⼀次概率值，就像游戏开始时有⼀个⼤骰⼦⼀样。

- 策略：在评价⼀个有未知牌的给定⾏动过程时，⾸先计算出每副可能牌的出牌⾏动的极⼩极⼤值，然后再⽤每副牌的概率来计算得到对所有发牌情况的期望值。

正确的分析

- ⾏动的价值是在所有的实际状态的平均值的直觉是错误的。

- 局部可观测性，⾏动的价值取决于信息的状态或agent所在的信度状态。

- 可以⽣成和搜索⼀棵信息状态树

计算机玩德克萨斯扑克总结

- 游戏是⾮常有趣的⼯作

- 完美是不可能实现的，必须近似

- 游戏的最好模型是搜索问题

- 博弈搜索树表⽰电脑/对⼿的轮流移动

- 评价函数估计给定每个玩家的板的配置质量、

- 极⼤极⼩算法选择最佳移动的假设是对⼿总是选择最好的移动

- α-β是可以避免搜索树的很⼤⼀部分来深化搜索深度的算法—消除⽆关的⼦树以提⾼效率 搜索总结

- ⽆信息的搜索策略

- 深度优先搜索(BFS)，⼀致代价搜索，深度优先搜索(DFS)，深度受限搜索，迭代加深的深度优先搜索

- 有信息的搜索策略

- 最佳优先搜索：贪婪、A*

- 局部搜索：爬⼭、模拟退⽕等

- 约束满⾜问题

- 回溯=深度优先搜索的给每个节点分配⼀个变量

- 增强：变量的顺序和值选择启发式，向前检查，约束传播