758-问题求解基本原理.ppt

问题求解基本原理
博弈:被认为高智能行为游戏;
不断为AI研究提出新课题,推动AI研究的发展。
搜索技术( 三)
博弈搜索
基于博弈搜索的搜索策略
博弈问题及博弈树概念
博弈搜索控制策略
博弈搜索算法及其应用实例
博弈树的α- β剪枝
博弈问题及博弈树概念
博弈问题:
对抗的双方参加博弈,取胜的因素不仅取决于一方的如意算盘,还需充分考虑对方的应付策略,(一字棋、国际象棋、打扑克、中国象棋、围棋)。
双人完备信息:
对垒的双方轮流走步,对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步,而且还能估计出对方未来可能走的棋步。
博弈问题及博弈树概念
博弈问题描述:
棋局描述;
棋局走步规则。
博弈搜索过程:
搜索棋局走步规则,隐含生成一棵特殊的与或树
博弈问题求解:
博弈问题及博弈树概念
与或节点分层交替出现的与或树
从甲的立场出发
或节点
与节点
或节点
完全取胜解图
甲走步
博弈问题及博弈树概念
判断走步的极小-极大原则:
考虑对方走步时(与节点):假定对手不会犯错误,他总是选择对自己最有利,对我方最不利的棋步走。因此,我方不能采取任何冒险行动,视对手将走出的棋局为极小值;
考虑我方走步时(或节点):应在对方造成的最坏的局势中尽可能地选择最好的棋着走,视自己可能走出的棋局为极大值。
基于博弈搜索的搜索策略
博弈问题及博弈树
博弈搜索控制策略
博弈搜索算法及其应用实例
博弈树的α- β剪枝
完整的博弈搜索策略(盲目搜索策略)
有界深度博弈搜索策略
完整的博弈搜索策略
核心思想:
从博弈的初始格局开始,轮番考虑自己与对方可能的所有走步,生成出棋局的各个格局,直到达到分出胜负输赢的终止格局为止,此搜索过程产生的一棵完整的博弈树。
完整的博弈搜索策略
博弈问题实例:
有一堆数目为N的钱币,甲、乙二人轮流分堆。要求每人每次挑选其中某一堆钱币,将其分成数目不等的两小堆。分堆过程持续,直至其中一人无法再将任一堆钱币分成数目不等的两堆时,则认输。
博弈问题描述:
分堆格局(状态): (x1,x2,…,xn,M), 其中,
xi: 第 i 堆钱币的个数;
M: 当前走步人编号-(MAX, MIN)
走步规则:
IF (x1,x2,…,xn,M) ∧(xi = Y+Z) ∧(Y ≠ Z)
THEN (x1,x2,…,xi-1, Y, Z, xi+1, …, xn,  M)
完整的博弈搜索策略
站在MAX立场
与节点
或节点
与节点
完全取胜的完备策略